图图的存储表示图的遍历无向图的连通分量和生成树最短路径(编辑修改稿)

图图的存储表示图的遍历无向图的连通分量和生成树最短路径(编辑修改稿)内容摘要：

template class T SeqListTamp。 GraphT::DFS( ) { int *visited=new int[graphsize]。 for(int i=0。 igraphsize。 i++) visited[i]=0。 SeqListT *L=new SeqListT。 *L=DFS(0,visited)。 delete[]visited。 return *L。 } template class T SeqListTamp。 GraphT::DFS(const int v, int *visited) { SeqListT*L。 T vertex=(v)。 L=new SeqListT。 visited[v]=1。 LInsert(vertex)。 int w=GetFirstNeighbor(v) while(w!=1) {if(!visited[w])DFS(w,visited)。 w=GetNextNeihbor(v,w)。 } return *L； } SeqListT L。 //输出顶点 StackT S。 //存储待算顶点 //深度优先搜索 2 不用 递归 用 栈 D B C A E I F H F B A S L AF HE B IE B AFH D B AFHIE C AFHIEDB AFHIEDBC template class T SeqListT amp。 GraphT::DepthFirstSearch(const Tamp。 beginVertex) { StackT S。 SeqListT *L, adjL。 SeqListIteratorT iteradjL(adjL)。 T vertex。 L = new SeqListT。 (beginVertex)。 //深度优先搜索 2 不用 递归 用 栈 while (!( )) {vertex = ( )。 if (!FindVertex(*L,vertex)) { (*L).Insert(vertex)。 adjL = GetNeighbors(vertex)。 (adjL)。 for(( )。 !( )。 ( )) if (!FindVertex(*L,( ))) (( ))。 } } return *L。 // return list } D B C A E I F H 广度优先搜索 用 队列 ABFCHEDI QueueT Q。 SeqListT L,adjL。 BF A Q L AB FCH ABF CHE ABFC HED ABFCH EDI ABFCHEDI template class T SeqList T amp。 Graph T ::BreadthFirstSearch( const T amp。 beginVertex) { Queue T Q。 SeqList T *L, adjL。 SeqListIterator T iteradjL(adjL)。 T vertex。 L = new SeqList T。 (beginVertex)。 // initialize the queue while (!( )) { vertex = ( )。 if (!FindVertex(*L,vertex)) { (*L).Insert(vertex)。 adjL = GetNeighbors(vertex)。 (adjL)。 for(( )。 !( )。 ( )) { if (!FindVertex(*L,( ))) (( ))。 } } } return *L。 } 四、无向图的连通分量和生成树 一个图中互相连通的点的极大子集叫 连通分量。 从一点出发，深度优先或广度优先搜索到的子图就是 连通分量。 从连通图的任意一点出发，深度优先搜索到的子图也就是图的生成树，也叫 深度优先生成树 ；广度优先搜索到的生成树，也叫广度优先生成树 ； 非连通图遍历得到的是 生成森林： 从一点出发深度优先搜索并标记，得到一棵树，再继续得到另一棵树，直到取遍所有顶点。 template class T void PrintList(SeqListT amp。 L) { SeqListIteratorT liter(L)。 for (( )。 !( )。 ( )) cout ( )。 } template class T int PathConnect (GraphT amp。 G, T v, T w) { SeqListT L。 // find vertices connected to v L = (v)。 // is w is in the list, return TRUE if ((w)) return 1。 else return 0。 } template class T void UConnectedComponent (GraphT amp。 G) { VertexIteratorT viter(G)。 SeqListT markedList, L。 for (( )。 !( )。 ( )) { if (!(( ))) { ( )。 L = (( ))。 SeqListIteratorT liter(L)。 for(( )。 !( )。 ( )) (( ))。 PrintList(L)。 cout endl。 } } } 强连通分量：彼此强连通的顶点的子集 A C B D I E G F H ABC D EFG H I 做法：从一点 v0出发作深度优先搜索，得到一个顶点序列 L。 检查 L上的点到 v0， 是否也连通，所有连通的点组成一个强连通分量。 重复着一过程，直到取遍所有顶点。 template class T void ConnectedComponent (GraphT amp。 G) { VertexIteratorT viter(G)。 SeqListT markedList, scList, L。 for (( )。 !( )。 ( )) { if (!(( ))) { ( )。 L = (( ))。 SeqListIteratorT liter(L)。 for (( )。 !( )。 ( )) if (PathConnect(G,( ),( ))) { (( ))。 (( ))。 } PrintList(scList)。 cout endl。 } } } 最小生成树 Minimumcost Spanning Tree 带权连通图（网络）中权值总和最小的生成树叫 最小生成树 例 连接所有 n个点的通讯网络的最短线路。 Prim 普里姆算法 设 G=V,E, 1. 令 U={v0}, T={ }. 2. 对任意 u∈ U, v∈ VU, (u,v)∈ E, 找到权最小的边 (u1,v1), 令 U=U∪ {v1}, T=T∪ {(u1,v1)} 3. 重复 2，直至 U=V. 得到 T就是最小生成树。 T中共有 n1条边 D B C A E F H 10 28 25 22 12 16 18 14 24 D B C A E F H 10 28 25 22 12 16 18 14 24 C B E A F D 6 5 3 6 4 5 2 1 5 6 C B E A F D 6 5 3 6 4 5 2 1 5 6 U={A}, T={(A,C)} U={A,C}, T={(A,C),(C,F)} U={A,C,F}, T={(A,C),(C,F),(D,F)} U={A,C,F,D}, T={(A,C),(C,F),(D,F),(B,C)} U={A,C,F,D,B}, T={(A,C),(C,F),(D,F),(B,C),(B,E)} U={A,C,F,D,B,E} C B E A F D 6 5 3 6 4 5 2 1 5 6 A B C D E F U T 0 A 6 A 1 A 5 A (A,C) C 5 0 C 6 C 4 C (C,F) C 5 F 2 C 6 0 F (D,F) 0 D (B,C) 0 B 3 B (B,E) 0 E 定义数组 closeEdge[n] 纪录每点到 U的最短距离 (点，距离 ) U中点距离为 0， 每加入一个新点， 数组更新一次 templateclass T struct MiniCostEdgeInfo { T adjvex。 int lowcost。 }。 template class T int operator(MiniCostEdgeInfoT a, MiniCostEdgeInfoT b) { return。 } template class T int minimum(MiniCostEdgeInfoT *a,int n) { for(int i=0。 in。 i++) if(a[i].lowcost!=0) break。 int min=i。 for(i=min+1。 in。 i++) if(a[i].lowcost!=0amp。 amp。 a[i]a[min]) min=i。 return min。 } templateclass T T GetVertex(GraphT G,int pos) { int i, n=( )。 if(pos0||pos=n) {cerrThere are not so many vertices!。 return 0。 } VertexIteratorT liter(G)。 i = 0。 while(!( ) amp。 amp。 i != pos) { i++。 ( )。 } return ( )。 } templateclass T void MiniSpanTreePrim(Graph T G) { int j,k,l,n=( )。 MiniCostEdgeInfo T * closeEdge。 closeEdge =new MiniCostEdgeInfo T [n]。 T s,w, v=GetVertex(G,0)。 closeEdge[0].lowcost=0。 //起始点 v0加进 U for(int i=。