8.1对于无向图8.29，试给出

（1）图中每个顶点的度；

（2）该图的邻接矩阵；

（3）该图的邻接表与邻接多重表；

（4）该图的连通分量。

8.2给定有向图8.30，试给出

（1）顶点D的入度与出度；

（2）该图的出边表与入边表；

（3）该图的强连通分量。

8.3请回答下列关于图的一些问题

（1）有n个顶点的有向强连通图最多有多少条边？最少有多少条边？

（2）表示一个有500个顶点，500条边的有向图的邻接矩阵有多少个非零元素？

（3）G是一个非连通的无向图，共有28条边，则该图至少有多少个顶点？

8.4图8.31是某个无向图的邻接表，请

（1）画出此图；

（2）写出从顶点A开始的DFS遍历结果。

（3）写出从顶点A开始的BFS遍历结果。

8.5证明，用Prim算法能正确地生成一棵最小生成树。

8.6证明，用Kruskal算法能正确地生成一棵最小生成树。

8.7对图8.32所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。

8.8对于图8.33给出的有向网，用Dijkstra方法求从顶点A到图中其它顶点的最短路径，并写出执行算法过程中距离向量d与路径向量p的状态变化情况。

8.9试写出图8.34所示的AOV网的4个不同的拓扑序列。

8.10 计算图8.35所示的AOE网中各顶点所表示的事件的发生时间ve（j），vl（j），各边所表示的活动的开始时间e（i），l（i），并找出其关键路径。

8.11 无向图采用邻接表作为存储结构，试写出以下算法

（1）求一个顶点的度；

（2）往图中插入一个顶点；

（3）往图中插入一条边；

（4）删去图中某顶点；

（5）删去图中某条边。

8.12 设有向图采用邻接表的存储结构（出边表），试写出求图中一个顶点的入度的算法。

8.13 设计一个算法，不利用拓扑排序判断有向图中是否存在环。。

8.14 编写一个非递归深度优先遍历图的函数。

8.15 编写两个函数分别计算AOE网中所有活动的最早开始时间与最晚允许开始时间。