带权有向图G用邻接矩阵A存储，则顶点v.的人度等于A中()。

在以下假设下，重写Djkstra算法：（1)用邻接表表示有向带权图G，其中每个边结点有3个域：邻接顶点v

在以下假设下，重写Djkstra算法：

(1)用邻接表表示有向带权图G，其中每个边结点有3个域：邻接顶点vertex，边上的权值length和边链表的链接指针link

(2)用集合T=V(G)-S代替S(已找到最短路径的顶点集合)，利用链表来表示集合T。

试比较新算法与原来的算法，计算时间是快了还是慢了，给出定量的比较。

若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权后得到的无向图。（1)如果图

若AOE网络的每一项活动都是关键活动。令G是将该网络的边去掉方向和权后得到的无向图。

(1)如果图中有一条边处于从开始顶点到完成顶点的每一条路径上，则仅加速该边表示的活动就能减少整个工程的工期。这样的边称为桥(bridge)。证明若从连通图中删去桥，将把图分割成两个连通分量。

(2)编写一个时间复杂度为O(n+e)的使用邻接表表示的算法，判断连通图G中是否有桥，若有。输出这样的桥。

对于一个无向图（a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶

点序列和按广度优先搜索遍历得到的顶点序列。

试以邻接矩阵为存储结构实现图的基本操作:InertVex（G,v).InserAr（G,vw)、DeleteVex（G,v)和DeleteArc（G,v,w)。

试证明：对于一个无向图G=（V，E)，若G中各顶点的度均大于或等于2，则G中必有回路。

A.G中有一条从Vj到Vi的路径

B.G中有一条从Vi到Vj的路径

C.G中有弧

D.G中没有弧

证明定理15.8.

定理15.8：设u,v为n阶无向图简单图G中两个不相邻的顶点,且d(u)+d(v)≥n,则G为哈密顿图GU(u,v)为哈密顿图((u,v)是加的新边.

______ 。

A．O(n)

B．O(e)

C．O(n+e)

D．O(n*e)