习题

1.对于一个无向图，如果采用邻接表进行存储，如何判断两个顶点 v _i 和 v _j 之间是否有边相连？在邻接表中，如何判断一个顶点的度是多少？

2.在图1-28所示的无向图中，找出所有的连通图，对于非连通图给出其连通分量。

3.对于图1-29给定的有向图：

（1）求出各顶点的入度和出度。

（2）从顶点 v ₁ 到顶点 v ₃ 的3条不同的基本路径。

4.对于图1-30给出的有向图：

（1）画出邻接矩阵。

（2）画出邻接表。

5.请分别按Prim算法和Kruskal算法求出图1-31无向网的最小生成树。

6.对图1-32中给定的有向图，试给出一种拓扑序列。

7.对图1-33中给定的有向图，试用Dijkstra算法求顶点 v ₀ 到顶点 v ₃ 的最短路径。