数据结构与算法分析b_课件chapter9

1、Chapter 9GraphsDefinition of graphs and some terminologyGraph representations Some algorithms9.1 Definition and terminologies1.Definition of graphs: Graph=(V, E)V: nonempty finite vertice setE: edge setUndirected Graph:If the tuple denoting an edge is unordered, then(v1,v2) and (v2,v1) are the same

2、edge.9.1 Definition and terminologiesDirected graph:If the tuple denoting an edge is ordered, then and are different edges. v1:始点v2:终点9.1 Definition and terminologiesExample:V1V(G1)=V1,V2,V3,V4E(G1)=(V1,V2),(V1,V3),(V1,V4),(V2,V3),VV23(V ,V ),(V ,V )2434V4G1V2V3V(G2)=V1,V2,V3E(G2)=,V1G29.1 Definitio

3、n and terminologiesWe will not discuss graphs of the following types多重图9.1 Definition and terminologies2.Complete graphIn an undirected graph with n nodes,thenumberof edges =n*(n-1)/2. If “=“ is satisfied,then it is called a complete undirect graph.V1V3V2V49.1 Definition and terminologiesIn a direct

4、ed graph with n nodes, the number of edges =n*(n-1). If “=“ is satisfied, then it is called a complete directed graph.9.1 Definition and terminologies3.degree dv of vertex v, TD(v):is the number of edges incident on vertex v.In a directed graph :in-degree of vertex v is the number of edges incident

5、to v, ID(v).out-degree of vertex v is the number of edgesincident from the v, OD(v).9.1 Definition and terminologiesTD(v)=ID(v)+OD(v)v2v3ID(v2)=1v1TD(v )=32OD(v )=22Generally,if there are n vertices and e edges in a graph, thene=(SnTD(v )/2ii=19.1 Definition and terminologies4. SubgraphGraph G=(V,E)

6、,G=(V,E), if VV, EE,and the vertices incident on the edges in E are in V, then G is the subgraph of G.For example:12111343439.1 Definition and terminologiesAnother example:V1V1V1V3V2V3V2V49.1 Definition and terminologies5.path.A sequence of vertices P=i1,i2,ik is an i1 to ik path in the graph of gra

7、ph G=(V,E) iff the edge(ij,ij+1)is in E for every j, 1=jk.6. Simple path and cycleA Simple path is a pathin which all verticesexcept possibly the first and last , are different.A Simple cycle is a simple path with the same start and end vertex.9.1 Definition and terminologiesAn example of a cycle9.1

8、 Definition and terminologies7.Connected graph & Connected componentIn a undirected graph, if there is a path from vertex v1 to v2, then v1 and v2 are connected.In a undirected graph ,if two arbitrary vertices are connected, then the graph is a connected graph.9.1 Definition and terminologiesExample

9、s :Non-connected graphMaximum connected subgraph(极大连通子图) is called connected component .9.1 Definition and terminologies8. Strong connected graph and strongly connected componentA digraph is strongly connected iff it contains a directed path from i to j and from j to i for every pair of distinct ver

10、tices i and j.The maximum strong connected subgraph (极大强连通子图) of a non-strongly connected graph is called strongly connected conponent (强连通分量).9.1 Definition and terminologies9. NetworkWhenweights and costs are assigned to edges, theresulting data object is called weighted graph and weighted digraph

11、.The term network refers to weightedconnectedgraph and weighted connected digraph.9.1 Definition and terminologiesExample of a networkV1V23118V545610V32V49.1 Definition and terminologies10. Spanning treeA spanning tree of a connected graph is its minimumconnected subgraph(极小连通子图).spanning tree has n

12、-1 edges.For example:An n-vertex112323449.2 ADT Graph and DigraphAbstractDataType Graphinstancesa set V of vertices and a set E of edges operationsCreate(n):create an undirected graph with n vertices and no edges Exist(i,j): return true if edge(i,j)exists; false otherwise Edges():return the number o

13、f edges in the graphVertices():return the number of vertices in the graph Add(i,j): add the edge(i,j) to the graph Delete(i,j):delete the edge (i,j)Degree(i): return the degree of vertex i InDegree(i): synonym for degree OutDegree(i): synonym for degree9.3 Representation of graphs and digraphs1.Adja

14、cency MatrixG=(V,E), V=V1,V2,Vnthen the adjacency matrix of graph G:if ,E or (i,j)Eotherwise10A(i,j)=9.3 Representation of graphs and digraphsFor example:graph0111101111001100V1 V4A(i,j)=V2V31) Adjacency matrix of graph is a symmetric matrix2) SA(i,j)= SA(j,i)=di (degree of vertex i)nnj=1j=19.3 Repr

15、esentation of graphs and digraphsDigraph0101010100000000010001010V2V1A(i,j)=V3V5V4nSA(i,j)= dioutj=1nSA(j,i)=diinj=19.3 Representation of graphs and digraphsRepresentation of networks, replace 1 with weights, others with W(i,j)if i!=j and ,E or(i,j)EA(i,j)=otherwise9.3 Representation of graphs and d

16、igraphsFor example:398615434A(i,j)=23942581261data 01除以上的邻接矩阵外，还要一个记录各顶点信息的表， 一个当前的边数V0V1其类说明 ：2V2const int MaxNumEdges=50/ 最大边数Maxsconst int MaxNumVertices=10 /最大顶点数template class Graph private:V3 .n-1SeqList VerticesList(MaxNumVertices) /顶点表DistType Edge MaxNumVertices MaxNumVertices /邻接矩阵int Curr

17、entEdges;/当前边数int FindVertex (Seqlist &L; const NameType &Vertex)return L.Find(Vertex);int GetVertexPos (const NameTyoe &Vertex)return FindVertex(VerticesList);/ 给出了顶点Vertex在图中的位置public:Graph (const int sz=MaxNumEdges);int GraphEmpty() const return VerticesList.IsEmpty();int GraphFull() constreturn

18、VerticesList.IsFull() |CurrentEdges=MaxNumEdges;int NumberofVertices() return VerticesList.last; int NumberofEdges() return CurrentEdges; NameType Getvalue(const int i)return i=0 & iVerticesList.last ? VerticesList.datai : DistType Getweight (const int v1,const int v2);NULL;int GetFirstNeighbor(cons

19、t int v);int GetNextNeighbor(const int v1,const int v2);void InsertVertex(const NameType & Vertex);void InsertEdge(const int v1,const int v2, DistType weight); void removeVertex(const int v);void removeEdge(cosnt int v1,const int v2);ConstructortemplateGraph : Graph(int sz)for (int i=0;isz;i+)for (i

20、nt j=0; jsz; j+) Edge ij=0; currentEdge=0;求顶点V的第一个邻接顶点的位置templateint Graph : GetFirstNeighbor(int v)if (v!=-1)for( int col=0; col0 & Edgevcolmax)return col;return -1;9.3 Representation of graphs and digraphs2. Linked-adjacency Listsreduce the storage requirement if the number of edges in the graph i

21、s small.hdest linkV1V41234V2V3201201304130249.3 Representation of graphs and digraphsDigraph:hdest cost link6123V1V243211hV31232201111403302613032016311024关于邻接表的声明const int Defaultsize=10;template class Graph;template struct Edge/边的定义friend class Graph ;int dest;/边的另一顶点在顶点表中的位置边的三个数据成员DistType cost;

22、/边上的权/下一条边的链指针Edge *link;Edge() Edge(int D,DistType C):dest(D),cost(C),link(NULL) int operate != (const Edge &E) constreturn dest != E.dest; template struct Vertex friend class Edge;friend class Graph;NameType data; Edge *adj;/顶点名字/出边表头指针Node Table:dest cost linkdataadj图的类定义template class Graphpriva

23、te:Vertex *NodeTable; /顶点表int NumVertices;int MaxNumVertices; int NumEdges;/当前顶点 数/最大顶点个数/当前边数图的私有数据成员int GetVertexpos(const Type &Vertex); public:Graph(int sz);Graph();int GraphEmpty() const return NumVertices= =0; int GraphFull() constreturn NumVertices= =MaxNumVertices;int NumberOfVertices() retu

24、rn NumVertices; int NumberOfEdges() return NumEdges; NameType GetValue(const int i)return i=0 & iNumVertices ? NodeTablei.data: NULL; void InsertVertex(const NameType &Vertex);void RemoveVertex(int v);void InsertEdge(int v1,int v2,DistType weight); void RemoveEdge(int v1,int v2);DistType Getweight(i

25、nt v1,int v2); int GetFristNeighbor(int v);int GetNextNeighbor(int v1,int v2);1）Constructortemplate Graph :Graph(int sz=Defaultsize) :NumVertices(0),MaxNumVertices(sz),NumEdge(0)int NumVertices, NumEdges, k, j; NameType name,tail,head; DistType weight;NodeTable=newVertexMaxNumVerticescinNumVertices;

26、/输入顶点数for( int i=0; iname; InsertVertex(name);cinNumEdges; /输入边数for( i=0; itailheadweight; k=GetVertexpos(tail); j=GetVertexpos(head); InsertEdge(k,j,weight);int Graph : GetVertexpos(const NameType &Vertex)for( int i=0; iNumVertices; i+)if (NodeTablei.data= =Vertex) return i;return 1;2) 给出顶点V的第一个邻接顶

27、点的位置templateint Graph:GetFirstNeighbor(int v)if (v!=-1)Edge *p=NodeTablev.adj; if (p!=NULL) return pdest ;return 1templateint Graph:GetNextNeighbor(int v1,int v2)if (v1!=-1)Edge *p=NodeTablev1.adj;while (p!=NULL)if(pdest=v2 & plink!=NULL) return plinkdest;else p=plink;return 1;3. 邻接多重表 (adjacency mu

28、ltilist)在无向图中, 如果边数为m, 则在邻接表表示中需2m个单位来存储. 为了克服这一缺点, 采用邻接多重表, 每条边用一个结点表示.vertex2path2V1e3V2vertex1path1dataFirstoute1e4e5e2e1e2e5e4e3V3V40121032302V1V2V3V4对有向图而言，需用邻接表和逆邻接表，如果把这两个表结合起来用有向图的邻接多重表(也称为十字链表)来表示一个有向图.markv1v2p1p2e6AEe5data Firstin Firstoute2DABe4e1BCCe3DE4034032312019.4 图的遍历与连通性图的遍历 (Grap

29、h Traversal):从图中某一顶点出发访问图中其余顶点,且使每个顶点 仅被访问一次.遍历二叉树: 前序, 中序, 后序.遍历树:深度优先遍历 (先根,后根)广度优先遍历遍历森林:深度优先遍历 (先根,中根,后根)广度优先遍历遍历图:深度优先遍历 DFS (Depth First Search)广度优先遍历 BFS (Breadth First Search)1.深度优先搜索 (depth-first-search)思想:从图中某个顶点V0出发,访问它,然后选择一个V0 邻接到的未被访问的一个邻接点V1出发深度优先遍历图,当遇到一个所有邻接于它的结点都被访问过了的结点U时,回退到前一次刚被

30、访问过的拥有未被访问的邻接点W,再从W出发深度遍历,直到连通图中的所有顶点都被访问过为止.以有向图为例:v1V1V2V4V8V5V3V6V7v2v3v1v4v5v6v7v2v3v8v4v5v6v7v8深度优先生成树递归方法实现算法中用一个辅助数组visited :0:未访问1:访问过了假设图为连通图主过程:templatevoid Graph : DFS( )int *visited=new intNumVertices;for ( int i=0; iNumVertices; i+) visitedi=0;DFS(0,visited);delete visited;/从顶点0开始深度优先搜索

31、子过程：template void Graph : DFS(int v, visited)coutGetValue(v); visitedv=1;int w=GetFirstNeighbor(v); while (w!=-1)用图的抽象数据类型来实现if(!visitedw) DFS(w,visited); w=GetNextNeighbor(v,w);算法分析：用邻接表表示 O(n+e)用邻接矩阵表示 O(n2)Javavoid dfs( Vertex v )v.visited = true;for each w adjacent if( !w.visited )dfs( w );/伪代码t

32、o v2. 广度优先遍历 （breadth search）思想：从图中某顶点V0出发，在访问了V0之后依次访问v0的各个未曾访问过的邻接点，然后分别从这些邻接点出发广度优先遍历图，直至图中所有顶点都被访问到为止.例子V1V2V3V4V 5V6V7V8v1v1v2v3v2v3v4v5v6v7v4v5v6v7v8v8广度优先生成树算法同样需要一个辅助数组visited 表示顶点是否被访问过.还需要一个队列,记正在访问的这一层和上一层的顶点. 算法显然是非递归的.templatevoid Graph : BFS(int v)int* visited=new intNumVertices;for (i

33、nt i=0; iNumVertices; i+) visitedi=0; coutGetValue(v);visitedv=1; queue q; q.EnQueue(v); while(!q.IsEmpty()v=q.DeQueue();int w=GetFirstNeighbor(v); while (w!=-1)if(!visitedw)coutGetValue(w);visitedw=1; q.EnQueue(w);w=GetNextNeighbor(v,w);delete visited;算法分析： 每个顶点进队列一次且只进一次，算法中循环语句至多执行n次。从具体图的存储结构来看：

34、1) 如果用邻接表：循环总时间代价为d0+d1+dn-1=O(e) 其中di是顶点i的度2) 如果用邻接矩阵: 对每个被访问过的顶点，循环检测矩阵中n个元素，时间代价为 O(n2)3. 连通分量以上讨论的是对一个无向的连通图或一个强连通图的有向图进行遍历，得到一棵深度优先或广度优先生成树.但当无向图(以无向图为例)为非连通图时，从图的某一顶点出发进行遍历(深度，广度)只能访问到该顶点所在的最大连通子图(即连通分量)的所有顶点.例子：AHKBECDILMNFGJOH,I,J非连通无向图K,L,O,M,NA,B,F,G,E,C,DAHKBECDILMNFGJO非连通图的连通分量下面是利用深度优先搜

35、索求非连通图的连通分量算法实际上只要加一个循环语句就行了.Templatevoid Graph : components()int* visited=new intNumVertices;for (int i=1; iNumVertices; i+) visitedi=0; for (i=0; iNumVertices; i+)if (!visitedi) DFS(i,visited); outputNewComponent();delete visited;9.5最小生成树1.生成树的有关概念生成树的定义设G=（V，E）是一个连通的无向图（或是强连通有向图） 从图G中的任一顶点出发作遍历图的

36、操作，把遍历走过的 边的集合记为TE（G），显然 G=（V，TE）是G之子图， G被称为G的生成树（spanning tree），也称为一个连通图.n个结点的生成树有n-1条边。生成树的代价：TE（G）上诸边的代价之和 生成树不唯一 最小代价生成树（minimun-cost spanning tree）问题的提出：如何找到一个网络的最小生成树，即各边权的总和为最小的生成树实际例子：6个城市已固定，现从一个城市发出信息到每一个城市如何选择或铺设通信线路，使花费（造价）最低。前提：每条边有代价如果用广度优先，则11=19565 565 1122344233634456566最小代价生成树1=154

37、122353456两个算法：Prim,Kruskal.它们都采用了逐步求解（Grandy)的策略。Grandy策略：设：连通网络N=V,E, V中有n个顶点。1) 先构造n个顶点，0条边的森林F=T0,T1,.,Tn-12) 每次向F中加入一条边。该边是一端在F的某棵树Ti上而另一端不在Ti上的所有边中具有最小权值的边。这样使F中两棵树合并为一棵，树的棵数-13)重复n-1次T0T1Tn-1最小生成树的类声明：const int MAXINT=机器可表示的，问题中不可能出现的大数class MinSpanTree; class MSTEdgeNodefriend class MinSpanTr

38、ee; private :int tail ,head; int cost;边的结构:tailheadcostclass MinSpanTree public :MinSpanTree(int SZ=NumVertices-1):MaxSize(SZ),n(0)edgevalue=new MSTEdgeNodeMaxSize; protected:MSTEdgeNode* edgevalue; int MaxSize, n;/边值数组/数组的最大元素个数和/当前个数；Kruskal算法1)把无向图中的所有边排序1 2212236789101281039（1,2)(3,5)(3,4)(4,5)(

39、2,3)(2,5)(1,4)(1,3)634572)一开始的最小生成树为T(V,TE)TE=即由 n个不同的连通分量组成3)在E中选一条代价最小的边（u,v)加入T，一定要满足（u,v) 不和TE中已有的边构成回路，E-(u,v),TE=TE (u,v)E4)一直到TE中加满n-1条边为止。1 2231 221233345454521 221283333664545图用邻接矩阵表示，edge(边的信息）图的顶点信息在顶点表 Verticelist中边的条数为CurrentEdges取最小的边以及判别是否构成回路，利用最小堆（MinHeap)和并查集（DisjointSets)克鲁斯卡尔算法vo

40、id Graph:Kruskal(MinSpanTree&T) MSTEdgeNode e; MinHeapH(currentEdges); int NumVertices=VerticesList.Last , u , v ;Ufsets F(NumVertices);/建立n个单元素的连通分量for(u=0;uNumVertices;u+)for (v=u+1;vNumVertices;v+) if(Edgeuv!=MAXINT) e.tail=u;e.head=v;e.cost=Edgeuv; H.insert(e);int count=1;/生成树边计数while(countNumVe

41、rtices) H.RemoveMin(e);u=F.Find(e.tail); v=F.Find(e.head);if(u!=v)F.union(u,v);T.Insert(e);count+;java(伪代码）public void kruskal( )int edgesAccepted;DisjSet s;priorityQueue h;Vertex u, v ;SetTypeuset, vset;Edge e;h = readGraphIntoHeapArray( ); h.buildHeap( ) ;s = new DisjSet( NUM_VERTICES );edgesAccep

42、ted = 0 ;while( edgesAccepted NUM_VERTICES 1 )e = h.deleteMin( ) ; uset = s. find( u ); vset = s.find( v );if( uset != vset )/Edge e = (u, v)edgesAccepted+;s.union( uset, vset );算法分析：1)建立e条边的最小堆。每插入一条边，执行一次fiterup( ) 算og2e所以，总的建堆时间为O(elog2e)检测邻接矩阵O(n2)2)构造最小生成树时：e次出堆操作：每一次出堆，执行一次filterdown(),总时间为O(e

43、log2e) 2e次find操作：O(elog2n)n-1次union操作：O(n)所以，总的计算时间为O(elog2e+elog2n+n2+n)3. Prim算法设：原图的顶点集合V(有n 个）生成树的顶点集合 U(最后也有n个），一开始为空TE集合为步骤：1) U=1任何起始顶点，TE=2) 每次生成（选择）一条边。这条边是所有边(u,v) 中代价（权）最小的边，uU,v V-UTE=TE+(u,v); U=U+v3) 当UV用一开始的例子：165 55 12423634656UV-UUV-U2345624561318条中找最小15条中找最小1665 55 55 15 122424233663344665566UV-U2UV-U211364435568条中找最小19条中找最小1665 55 15 122424233663344665566UV-U136455条中找最小115 15 12422343634324S=1565665最小生成树不是唯一的.为什么?算法分析:具体实现：1) 图采用邻接矩阵2) 设置了两个辅助数组：改进了实现效率.Lowcost:存放生成树顶点集合内顶点到生成树外 各顶点的边上的当前最小权值；near