《数据结构图的遍历与连通性参考用》由会员分享，可在线阅读，更多相关《数据结构图的遍历与连通性参考用（30页珍藏版）》请在装配图网上搜索。
1、7.2 图的存储结构 图的数组 (邻接矩阵 )存储表示 图的邻接表存储表示 有向图的十字链表存储表示 无向图的邻接多重表存储表示 邻接矩阵 是用于描述图中顶点之间关系 (即弧或边 的权 )的矩阵。 邻接表 类似树的孩子链表。即对图中的每个顶点 vi 建立一个单链表，表中结点表示依附于该顶点 vi的 边或弧。 邻接点域 链域 数据域 数据域 链域 表结点 表头结点 V1 V3 V2 V4 例： 4 3 2 1 2 1 1 1 3 4 4 2 3.有向图的十字链表存储表示 两种结点结构： 尾域 tailvex 头域 headvex 链域 hlink 链域 tlink 信息域 info 数据域 da
2、ta 链域 firstin 链域 firstout 顶点结点 弧结点 v1 v2 v3 v4 0 1 2 3 1 0 / 2 0 v3 v1 v4 v2 / 0 3 / 1 3 / / 2 3 0 2 / / 3 2 例： data firstin firstout tailvex headvex hlink tlink / 标志域 边顶点 i 边顶点 j 链域 i 链域 j 信息域 数据域 边链域 4.无向图的邻接多重表存储表示 边结点 顶点结点 1 3 4 2 例： 1 2 3 4 1 2 1 3 2 4 第 7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4
3、 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 7.3 图的遍历 从图中某一顶点出发访遍图中其余顶点，且使 每一个顶点仅被访问一次。这一过程就叫做 图的 遍历 。 通常有两条遍历图的路径： 深度优先搜索 广度优先搜索 1.深度优先搜索 (DFS) 基本思想： 从图中某顶点 V0出发，访问此顶点，然后依次 从 V0的各个未被访问的邻接点出发 深度优先搜索 遍 历图，直至图中所有和 V0有路径相通的顶点都被访 问到； 若此时图中尚有顶点未被访问，则另选图中一 个未曾被访问的顶点作起始点； 重复上述过程，直至图中所有顶点都被访问到 为止。 例： 从顶点 v1出发， DFS下图。 顶点
4、访问序列为： v1,v2,v4,v8,v5,v3,v6,v7 v1 v6 v2 v5 v3 v8 v4 v7 图的 DFS算法一般描述 int visitedMAXVEX; /访问标志数组 void DFSgraph(Graph G, Visit() /对图 G作深度优先遍历 for( v=0; vG.vexnum; +v ) visitedv=FALSE; /访问标志数组初始化 for( v=0; v=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G,w); /对 v的尚未访问的邻接顶点 w递归调用 DFS 用邻接表实现图的深度优先搜索 v1 v6 v2
5、 v5 v3 v8 v4 v7 v9 v10 1 2 3 4 5 6 7 8 2 8 2 8 3 7 3 6 4 5 2 3 1 6 7 1 4 5 9 10 9 / 10 / 分析： 在遍历图时，对图中每个顶点至多调用一次 DFS函数，因为一旦某个顶点被标志成已被访问， 就不再从它出发进行搜索。 因此，遍历图的过程实质上是对每个顶点查 找其邻接点的过程。其耗费的时间则取决于所采 用的存储结构。 2.广度优先搜索 (BFS) 基本思想： 从图中某个顶点 V0出发，并在访问此顶点后依 次访问 V0的所有未被访问过的邻接点，之后按这些 顶点被访问的先后次序依次访问它们的邻接点，直 至图中所有和 V
6、0有路径相通的顶点都被访问到； 若此时图中尚有顶点未被访问，则另选图中一 个未曾被访问的顶点作起始点； 重复上述过程，直至图中所有顶点都被访问到 为止。 例： 从顶点 v1出发， BFS下图。 顶点访问序列为： v1,v2,v3,v4,v5,v6,v7,v8 v1 v6 v2 v5 v3 v8 v4 v7 用邻接表实现图的广度优先搜索 1 2 3 4 5 6 7 8 2 8 2 8 3 7 3 6 4 5 2 3 1 6 7 1 4 5 v1 v6 v2 v5 v3 v8 v4 v7 BFS非递归 算法 void BFSTraverse(Graph G, Status (*Visit)(int
7、 v) /使用辅助队列 Q和访问标志数组 visitedv for (v=0; vG.vexnum; +v) visitedv = FALSE; InitQueue(Q); / 置空的辅助队列 Q for ( v=0; v=0;w=NextAdjVex(G,u,w)） if ( ! visitedw) /w为 u的尚未访问的邻接顶点 visitedw = TRUE; Visit(w); EnQueue(Q, w); /if /while if / BFSTraverse 分析： 每个顶点至多进一次队列。遍历图的过程实 质上是通过边或弧找邻接点的过程，因此广度优 先搜索遍历图的时间复杂度和深度优
8、先搜索遍历 相同，两者不同之处仅仅在于对顶点访问的顺序 不同。 第 7章 图 7.1 图的定义和术语 7.2 图的存储结构 7.3 图的遍历 7.4 图的连通性问题 7.5 有向无环图及其应用 7.6 最短路径 7.4 图的连通性问题 1） 无向图的 连通分量和 生成树 2） 最小生成树 3）普里姆算法 4）克鲁斯卡尔算法 1.无向图的 连通分量和 生成树 基本概念 连通分量的顶点集 ：即从该连通分量的某一 顶点出发进行搜索所得到的顶点访问序列； 生成树 ： 某连通分量的极小连通子图 ； 生成森林 ：非连通图的各个连通分量的极小 连通子图构成的集合 。 设 E(G)为连通子图 G中所有边的集合
9、，则从图 中任一顶点出发遍历图时，必定将 E(G)分成两个 集合 T(G)和 B(G)，其中 T(G)是遍历过程中历经的 边的集合。显然， T(G)和图 G中所有顶点一起构 成连通图 G的极小连通子图，按照 7.1节的定义， 它是连通图的一棵生成树，并且称由深度优先搜 索得到的为 深度优先生成树 ；由广度优先搜索得 到的为 广度优先生成树 。 例：求下图的深度优先生成树和广度优先生成树。 v1 v6 v2 v5 v3 v8 v4 v7 对非连通图，每个连通分量中的顶点集和遍 历时走过的边一起构成若干棵生成树，这些连通 分量的生成树组成非连通图的 生成森林 。 例： 生成非连通图的深度优先生成森
10、林的算法 void DFSForest (Graph G， CSTree /是其它生成树的根 (前一棵的根的 “ 兄弟 ” ) q = p; /q指示当前生成树的根 DFSTree(G,v,p); /建立以 p为根的生成树 /DFSForest void DFSTree (Graph G， int v， CSTree w=0; w=NextAdjVex(G, v, w) if(!visitedw) p=(CSTree)malloc(sizeof(CSNode); /分配孩子结点 *p=GetVex(G,w)， NULL， NULL； if(first) /w是 v的第一个未被访问的邻接顶点 T
11、 lchild=p； first=FALSE； /是根的左孩子结点 else /w是 v的其它未被访问的邻接顶点 q nextsibling =p； /是上一邻接顶点的右兄弟结点 q = p； DFSTree(G, w, q)； /从第 w个顶点出发深度优先遍历图 G，建立子生成树 q /if /DFSTree 1.理解并掌握图的深度优先搜索和广度优先搜索 两种遍历算法及其性能分析；以及两种遍历所使 用的辅助数据结构（栈或队列）在遍历过程中所 起的作用，能够确定两种遍历所得到的顶点访问 序列以及利用图的两种遍历设计算法解决简单的 应用问题。 2.理解并掌握生成树的概念，能画出给定的图深 度优先和广度优先生成树或生成森林； 作业 P49： 7.21 小结
数据结构图的遍历与连通性参考用
