71抽象数据类型图的定义

71抽象数据类型图的定义内容摘要：

T T T T a c b d g f e 访问标志 : 访问次序 : 例如 : 0 1 2 3 4 5 6 0 2 3 4 5 1 6 void DFS(Graph G, int v) { // 从顶点 v出发， 深度优先搜索遍历连通图 G visited[v] = TRUE。 VisitFunc(v)。 for(w=FirstAdjVex(G, v)。 w!=0。 w=NextAdjVex(G,v,w)) if (!visited[w]) DFS(G, w)。 // 对 v的尚未访问的邻接顶点 w // 递归调用 DFS } // DFS 首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。 非连通图的深度优先搜索遍历 a b c h d e k f g F F F F F F F F F T T T T T T T T T a c h d k f e b g 访问标志 : 访问次序 : 例如 : 0 1 2 3 4 5 6 7 8 0 2 1 3 4 5 6 7 8 void DFSTraverse(Graph G, Status (*Visit)(int v)) { // 对图 G 作深度优先遍历。 VisitFunc = Visit。 for (v=0。 v。 ++v) visited[v] = FALSE。 // 访问标志数组初始化 for (v=0。 v。 ++v) if (!visited[v]) DFS(G, v)。 // 对尚未访问的顶点调用 DFS } 二、广度优先搜索遍历图 V w1 w8 w3 w7 w6 w2 w5 w4 对连通图，从起始点 V到其余各顶点必定存在路径。 其中， Vw1, Vw2, Vw8 的路径长度为 1； Vw7, Vw3, Vw5 的 路径长度为 2； Vw6, Vw4 的路径长度为 3。 从图中的某个顶点 V0出发，并在访问此顶点之后 依次访问 V0的所有 未被访问 过的邻接点 ，之后分别从这些邻接点出发依次访问它们的邻接点，并使 “先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问 ，直至图中所有和 V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。 V w1 w8 w3 w7 w6 w2 w5 w4 F F F F F F F F F T T T T T T T T T 0 1 2 3 4 5 6 7 8 Visited Q V 访问次序 : w1 w2 w8 w4 w7 w3 w5 w6 void BFSTraverse(Graph G, Status (*Visit)(int v)){ for (v=0。 v。 ++v) visited[v] = FALSE。 //初始化访问标志 InitQueue(Q)。 // 置空的辅助队列 Q for ( v=0。 v。 ++v ) if ( !visited[v]) { // v 尚未访问 } } // BFSTraverse … … visited[u] = TRUE。 Visit(u)。 // 访问 u EnQueue(Q, v)。 // v入队列 while (!QueueEmpty(Q)) { DeQueue(Q, u)。 // 队头元素出队并置为 u for(w=FirstAdjVex(G, u)。 w!=0。 w=NextAdjVex(G,u,w)) if ( ! visited[w]) { visited[w]=TRUE。 Visit(w)。 EnQueue(Q, w)。 // 访问的顶点 w入队列 } // if } // while 连通分量 (Connected ponent) 当无向图为非连通图时 , 从图中某一顶点出发 , 利用深度优先 搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点 , 只能访问到该顶点所在的最大连通子图 (连通分量 )的所有顶点。 图的连通性问题 L E D H G A B F I C J K M 若从无向图的每一个连通分量中的一个顶点出发进行遍历 , 可求得无向图的所有连通分量。 求连通分量的算法需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的另一个连通分量。 对于非连通的无向图，所有连通分量的生成树组成了非连通图的生成森林。 E D H G I K L A B F C J M H G I K L A B F C J M E D 非连通无向图 DFS 访问序列 : ALMJBFC DE GKHI L A B F C J M H G I K L A B F C J M E D E D H G I K H G I K L A B F C J M E D (连通网的 )最小生成树 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n1条线路， 如何在最节省经费的前提下建立 这个 通讯网。 问题： 构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n1 条边（不构成回路），使“ 权值之和 ”为最小。 算法二：（克鲁斯卡尔算法） 该问题等价于： 算法一：（普里姆算法） 假设 N={V,{E})是连通网 ， TE是 N上最小生成树边的集合。 算法从 U ＝{u0}(u0∈ V)， TE={ }开始 ， 重复执行下述操作：在所有 u∈ V， v∈ VU的边 (u,v)∈ E中找一条 代价最小 的边 （ u0， v0） 并入集合 TE,同时 v0并入 U， 直至 U=V为止。 此时 TE中必有 n1条边 ， 则 T=(V,{TE})为 N的最小生成树。 普里姆算法的基本思想 : 在生成树的构造过程中，图中 n 个顶点分属两个集合： 已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集VU ，则应 在所有连通 U中顶点和 VU中顶点的边中选取权值最小的边。 一般情况下所添加的顶点应满足下列条件 : a b c d e g f 例如 : 19 5 14 18 27 16 8 21 3 12 7 所得生成树权值和 = 14+8+3+5+16+21 = 67 设置一个辅助数组， 对每个顶点 ，记录从顶点集 U到 V－ U具有 代价最小 的边： struct { VertexType adjvex。 // U集中的顶点 VRType lowcost。 // 边的权值 } closedge[MAX_VERTEX_NUM]。 adjvex lowcost a b c d e g f 19 5 14 18 27 16 8 21 3 12 7 cl o s ed g e0 1 2 3 4 5 6A dj v e xL o w c os ta a a 19。