第八章-图-C++数据结构-教学课件.ppt

1、(vertex)：。class Graph public:Graph();void InsertVertex(const Type&vertex);void InsertEdge (const int v1,const int v2,int weight);void RemoveVertex(const int v);void RemoveEdge(const int v1,const int v2);int IsEmpty();Type GetWeight(const int v1,const int v2);int GetFirstNeighbor(const int v);int Get

2、NextNeighbor(const int v1,const int v2);,),(,.否则否则如果如果01AEjiEjijiEdge或者 ),(,),(.jijiEjiEjijijiWjiEdge=!0=A对角线但是否则,或且如果const int MaxEdges=50;const int MaxVertices=10;template class Graph private:SeqList VerticesList(MaxVertices);DistType EdgeMaxVerticesMaxVertices;int CurrentEdges;int FindVertex(SeqL

3、ist&L;const NameType&vertex)return L.Find(vertex);int GetVertexPos(Const NameType&vertex)return FindVertex(VerticesList,vertex);public:Graph(const int sz=MaxNumEdges);int GraphEmpty()const return VerticesList.IsEmpty();int GraphFull()const return VerticesList.IsFull()|CurrentEdges=MaxEdges;int Numbe

4、rOfVertices()return VerticesList.last;int NumberOfEdges()return CurrentEdges;NameType GetValue(const int i)return i=0&i VerticesList.last?VerticesList.datai:NULL;int GetWeight(const int v1,const int v2);int GetFirstNeighbor(const int v);int GetNextNeighbor(const int v1,const int v2);void InsertVerte

5、x(const NameType&vertex);void InsertEdge (const int v1,const int v2,DistType weight);void RemoveVertex(const int v);void RemoveEdge(const int v1,const int v2);template Graph:Graph(const int sz)/构造函数构造函数 for(int i=0;i sz;i+)for(int j=0;j sz;j+)Edgeij=0;CurrentEdges=0;template DistType Graph:GetWeight

6、(const int v1,const int v2)/给出以顶点给出以顶点 v1 和和 v2 为两端点的边上的权值为两端点的边上的权值 if(v1!=-1&v2!=-1)return Edgev1v2;else return 0;template int Graph:GetFirstNeighbor(const int v)/给出顶点位置为给出顶点位置为 v 的第一个邻接顶点的位置的第一个邻接顶点的位置 if(v!=-1)for(int col=0;col 0)return col;return-1;template int Graph:GetNextNeighbor(const int v

7、1,const int v2)/给出顶点给出顶点v1的某邻接顶点的某邻接顶点v2的下一个邻接顶点的下一个邻接顶点 if(v1!=-1&v2!=-1)for(int col=v2+1;col 0)return col;return-1;const int DefaultSize=10;template class Graph;template struct Edge int dest;DistType cost;Edge*link;Edge()Edge(int D,DistType C):dest(D),cost(C),link(NULL)int operator!=(const Edge&E)

8、const return dest!=E.dest;template struct Vertex NemeType data;Edge*adj;template class Graph friend class vertex;friend class Edge;private:Vertex*NodeTable;int NumVertices;int MaxVertices;int NumEdges;int GetVertexPos(const Type&vertex);public:Graph(int sz);Graph();int GraphEmpty()const return NumVe

9、rtices=0;int GraphFull()const return NumVertices=MaxVertices|NumEdges=MaxEdges;NameType GetValue(const int i)return i=0&i NumVertices?NodeTablei.data:NULL;int NumberOfVertices()return NumVertices;int NumberOfEdges()return NumEdges;void InsertVertex(const NameType&vertex);void RemoveVertex(const int

10、v);void InsertEdge(const int v1,const int v2,const DistType weight);void RemoveEdge(const int v1,const int v2);DistType GetWeight(const int v1,const int v2);int GetFirstNeighbor(const int v);int GetNextNeighbor(const int v1,const int v2);template Graph:Graph(const int sz=DefaultSize):NumVertices(0),

11、MaxVertices(sz),NumEdges(0)int n,e,k,j;NameType name,tail,head;DistType weight;NodeTable=/创建顶点表创建顶点表 new VertexMaxVertices;cin n;/输入顶点个数输入顶点个数 for(int i=0;i name;InserVertex(name);cin e;/输入边条数输入边条数 for(i=0;i tail head weight;k=GetVertexPos(tail);j=GetVertexPos(head);InsertEdge(k,j,weight);template G

12、raph:Graph()for(int i=0;i NumVertices;i+)Edge*p=NodeTablei.adj;while(p!=NULL)/逐条边释放逐条边释放 NodeTablei.adj=plink;delete p;p=NodeTablei.adj;delete NodeTable;/释放顶点表释放顶点表template int Graph:GetVertexPos(Const NameType&vertex)/根据顶点名根据顶点名vertex查找该顶点在邻接表中的位置查找该顶点在邻接表中的位置 for(int i=0;i NumVertices;i+)if(NodeTa

13、blei.data=vertex)return i;return-1;template int Graph:GetFirstNeighbor(const int v)/查找顶点查找顶点 v 的第一个邻接顶点在邻接表中的位置的第一个邻接顶点在邻接表中的位置 if(v!=-1)/若顶点存在若顶点存在 Edge*p=NodeTablev.adj;if(p!=NULL)return pdest;return-1;/若顶点不存在若顶点不存在template int Graph:GetNextNeighbor(const int v1,const int v2)/查找顶点查找顶点 v1 在邻接顶点在邻接顶

14、点 v2 后下一个邻接顶点后下一个邻接顶点 if(v1!=-1)Edge*p=NodeTablev1.adj;while(p!=NULL)if(pdest=v2&plink!=NULL)return plinkdest;/返回下一个邻接顶点在邻接表中的位置返回下一个邻接顶点在邻接表中的位置 else p=plink;return-1;/没有查到下一个邻接顶点返回没有查到下一个邻接顶点返回-1template DistType Graph:GetWeight(const int v1,const int v2)/取两端点为取两端点为 v1 和和 v2 的边上的权值的边上的权值 if(v1!=-1

15、&v2!=-1)Edge*p=NodeTablev1.adj;while(p!=NULL)if(pdest=v2)return pcost;else p=plink;return 0;mark vertex1 vertex2 path1 path2 data Firstout mark vertex1 vertex2 path1 path2 data Firstin Firstoutviod Graph:DFS(const int v,int visited )cout GetValue(v);/访问顶点访问顶点 v visitedv=1;/顶点顶点 v 作访问标记作访问标记 int w=Ge

16、tFirstNeighbor(v);/取取 v 的第一个邻接顶点的第一个邻接顶点 w while(w!=-1)/若邻接顶点若邻接顶点 w 存在存在 if(!visitedw)DFS(w,visited);/若若顶点顶点 w 未访问过未访问过,递归访问顶点递归访问顶点 w w=GetNextNeighbor(v,w);/取顶点取顶点 v 的排在的排在 w 后面的下一个邻接顶点后面的下一个邻接顶点 void Graph:DFS()visited=new Boolean n;/创建数组创建数组 visited for(int i=0;i n;i+)visited i=0;/访问标记数组访问标记数组

17、visited 初始化初始化 DFS(0);delete visited;/释放释放 visited void Graph:BFS(const int v)visited=new intNumCertices;/创建创建 visited for(int i=0;i NumVertices;i+)visitedi=0;/visited 初始化初始化 cout GetValue(v);visitedv=1;Queue q;q.EnQueue(v);/访问访问 v,进队列进队列 while(!q.IsEmpty()/队空搜索结束队空搜索结束 v=q.DeQueue();/不空不空,出队列出队列 in

18、t w=GetFirstNeighbor(v);/取顶点取顶点 v 的的第一个邻接顶点第一个邻接顶点 w while(w!=-1)/若邻接顶点若邻接顶点 w 存在存在 if(!visitedw)/若该邻接顶点未访问过若该邻接顶点未访问过 cout GetValue(w);/访问访问 visitedw=1;q.EnQueue(w);/进队进队 w=GetNextNeighbor(v,w);/取顶点取顶点 v 的排在的排在 w 后面的下一邻接顶点后面的下一邻接顶点 /重复检测重复检测 v 的所有邻接顶点的所有邻接顶点 delete visited;void Graph:Components()vi

19、sited=new intNumCertices;/创建创建visited for(int i=0;i NumVertices;i+)visitedi=0;/visited 初始化初始化 for(i=0;i NumVertices;i+)if(!visitedi)/检测所有顶点是否访问过检测所有顶点是否访问过 DFS(i,visited);/从未访问的顶点出发访问从未访问的顶点出发访问 OutputNewComponent();/输出一个连通分量输出一个连通分量 delete visited;/释放释放visitedlowu=min dfnu,min loww|w 是是 u 的一个子女的一个子

20、女,min dfnx|(u,x)是一条回边是一条回边 计算计算dfn与与low的算法的算法(1)void Graph:DfnLow(const int x)/公有函数：从顶点公有函数：从顶点x开始深度优先搜索开始深度优先搜索 int num=1;/num是访问计数器是访问计数器 dfn=new intNumVertices;low=new intNumVertices;/dfn是深度优先数是深度优先数,low是最小祖先访问顺序号是最小祖先访问顺序号 for(int i=0;i NumVertices;i+)dfni=lowi=0;/给予访问计数器给予访问计数器num及及dfnu,lowu初值初

21、值 DfnLow(x,-1);/从根从根x开始开始 delete dfn;delete low;计算计算dfn与与low的算法的算法(2)void Graph:DfnLow(const int u,const int v)/私有函数：从顶点私有函数：从顶点 u 开始深度优先搜索计算开始深度优先搜索计算dfn/和和low。在产生的生成树中。在产生的生成树中 v 是是 u 的双亲。的双亲。dfnu=lowu=num+;int w=GetFirstNeighbor(u);while(w!=-1)/对对u所有邻接顶点所有邻接顶点w循环循环 if(dfnw=0)/未访问过未访问过,w是是u的孩子的孩子

22、DfnLow(w,u);/从从w递归深度优先搜索递归深度优先搜索 lowu=min2(lowu,loww);/子女子女w的的loww先求出先求出,再求再求lowu else if(w!=v)/w访问过且访问过且w不是不是v，是回边是回边 lowu=min2(lowu,dfnw);/根据回边另一顶点根据回边另一顶点w调整调整lowu w=GetNextNeighbor(u,w);/找顶点找顶点u在在w后面的下一个邻接顶点后面的下一个邻接顶点 void Graph:Biconnected()/公有函数：从顶点公有函数：从顶点0开始深度优先搜索开始深度优先搜索 int num=1;/访问计数器访问计

23、数器num dfn=new intNumVertices;/dfn是深度优先数是深度优先数 low=new intNumVertices;/low是最小祖先号是最小祖先号 for(int i=0;i NumVertices;i+)dfni=lowi=0;DfnLow(0,-1);/从顶点从顶点 0 开始开始 delete dfn;delete low;void Graph:Biconnected(const int u,const int v)/私有函数：计算私有函数：计算dfn与与low,根据其重连通分量输根据其重连通分量输/出出Graph的边。在产生的生成树中的边。在产生的生成树中,v 是

24、是 u 的双亲的双亲/结点结点,S 是一个初始为空的栈，应声明为图的数是一个初始为空的栈，应声明为图的数/据成员。据成员。int x,y,w;dfnu=lowu=num+;w=GetFirstNeighbor(u);/找顶点找顶点u的第一个邻接顶点的第一个邻接顶点w while(w!=-1)if(v!=w&dfnw=dfnu)/无回边无回边,原来的重连通分量结束原来的重连通分量结束 cout “新重连通分量新重连通分量:”end1;do (x,y)=S.Pop();cout x ,y endl;while(x,y)与与(u,w)不是同一条边不是同一条边);/输出该重连通分量的各边输出该重连通分

25、量的各边 else if(w!=v)/有回边有回边,计算计算 lowu=min2(lowu,dfnw);/根据回边另一顶点根据回边另一顶点w调整调整lowu w=GetNextNeighbor(u,w);/找顶点找顶点u的邻接顶点的邻接顶点w的下一个邻接顶点的下一个邻接顶点 tail head cost 边的两个顶点位置边的两个顶点位置 边的权值边的权值const int MAXINT=机器可表示的机器可表示的,问题中不可能出现的大数问题中不可能出现的大数class MinSpanTree;class MSTEdgeNode/生成树边结点类定义生成树边结点类定义friend class Min

26、SpanTree;private:int tail,head;/生成树各边的两顶点生成树各边的两顶点 int cost;/生成树各边的代价生成树各边的代价;class MinSpanTree /生成树的类定义生成树的类定义public:MinSpanTree(int sz=MaxEdges-1):MaxSize(sz),n(0)edgevalue=new MSTEdgeNodeMaxSize;int Insert(MSTEdgeNode&item);/将将item加到最小生成树中加到最小生成树中protected:MSTEdgeNode*edgevalue;/边值数组边值数组 int MaxS

27、ize,n;/最大边数最大边数,当前边数当前边数;void Graph:Kruskal(MinSpanTree&T)MSTEdgeNode e;/边结点辅助单元边结点辅助单元 MinHeap H(CurrentEdges);int NumVertices=VerticesList.last;/顶点个数顶点个数 UFSets F(NumVertices);/并查集并查集F 并初始化并初始化 for(int u=0;u NumVertices;u+)/邻接矩阵邻接矩阵 for(int v=i+1;v NumVertices;v+)if(Edgeuv!=MAXINT)/检出所有边检出所有边 e.ta

28、il=u;e.head=v;e.cost=w;H.Insert(e);/插入最小堆插入最小堆 int count=1;/最小生成树加入边数的计数最小生成树加入边数的计数 while(count NumVertices)/e=H.RemoveMin();/从堆中退出一条边从堆中退出一条边 u=F.Find(e.tail);/检测两端点的根检测两端点的根v=F.Find(e.head);if(u!=v)/根不同根不同,不在同一连通分量上不在同一连通分量上 F.Union(u,v);/合并合并 T.Insert(e);/该边存入最小生成树该边存入最小生成树 T 中中 count+;继续重复得：继续重

29、复得：顶点顶点5加入生成树顶点集合：加入生成树顶点集合：v=5v=4(0,5,10),(5,4,25),(4,3,22),(3,2,12),(2,1,16),(1,6,14)void Graph:Prim(MinSpanTree&T)int NumVertices=VerticesList.last;/图中顶点数图中顶点数 lowcost=new intNumVertices;nearvex=new intNumVertices;for(int i=1;i NumVertices;i+)lowcosti=Edge0i;/顶点顶点0到各边的代价到各边的代价 nearvexi=0;/及最短带权路径

30、及最短带权路径 nearvex0=-1;/顶点顶点0加到生成树顶点集合加到生成树顶点集合 int count=0;/生成树边值数组存放指针生成树边值数组存放指针 MSTEdgeNode e;/最小生成树结点辅助单元最小生成树结点辅助单元 for(i=1;i NumVertices;i+)/循环循环n-1次次,加入加入n-1条边条边 int min=MAXINT;int v=0;for(int j=0;j NumVertices;j+)if(nearvexj!=-1&lowcostj min)v=j;min=lowcostj;/求生成树外顶点到生成树内顶点具有最小求生成树外顶点到生成树内顶点具有

31、最小 /权值的边权值的边,v是是当前具最小权值的边的位置当前具最小权值的边的位置 if(v)/v=0表示再也找不到要求的顶点了表示再也找不到要求的顶点了 count+;/向生成树边值数组内存放向生成树边值数组内存放 e.tail=nearvexv;e.head=v;e.cost=lowcostv;T.Insert(e);/选出的边加入生成树选出的边加入生成树 nearvexv=-1;/作该边已加入生成树标记作该边已加入生成树标记 for(j=1;j NumVertices;j+)if(nearvexj!=-1&/j不在生成树中不在生成树中 Edgevj lowcostj)/需要修改需要修改 l

32、owcostj=Edgevj;nearvexj=v;源 点 终 点 最 短 路 径路 径 长 度 v0 v1(v0,v1)10 v2(v0,v1,v2)(v0,v3,v2)60 50 v3(v0,v3)30 v4(v0,v4)(v0,v3,v4)(v0,v3,v2,v4)100 90 60const int NumVertices=6;/图中最大顶点个数图中最大顶点个数class Graph /图的类定义图的类定义 private:int EdgeNumVerticesNumVertices;/邻接矩阵邻接矩阵 int distNumVertices;/最短路径长度数组最短路径长度数组 int

33、 pathNumVertices;/最短路径数组最短路径数组 int SNumVertices;/最短路径顶点集最短路径顶点集public:void ShortestPath(const int,const int);int choose(const int);void Graph:ShortestPath(const int n,const int v)/Graph是一个具有是一个具有n个顶点的带权有向图个顶点的带权有向图,各边上各边上/的权值由的权值由Edgeij给出。本算法建立起一个数给出。本算法建立起一个数/组组:distj,0 j n,是当前求到的从顶点是当前求到的从顶点v到顶点到顶

34、点/j的最短路径长度的最短路径长度,同时用数组同时用数组pathj,0 j n,存存/放求到的最短路径。放求到的最短路径。for(int i=0;i n;i+)disti=Edgevi;/dist数组初始化数组初始化 Si=0;if(i!=v&disti MAXINT)pathi=v;else pathi=-1;/path数组初始化数组初始化 Sv=1;distv=0;/顶点顶点v加入顶点集合加入顶点集合 /选择当前不在集合选择当前不在集合S中具有最短路径的顶点中具有最短路径的顶点u for(i=0;i n-1;i+)int min=MAXINT;int u=v;for(int j=0;j n

35、;j+)if(!Sj&distj min)u=j;min=distj;Su=1;/将顶点将顶点u加入集合加入集合S for(int w=0;w n;w+)/修改修改 if(!Sw&Edgeuw MAXINT&distu+Edgeuw distw)distw=distu+Edgeuw;pathw=u;选 取 顶点1 顶点2 顶点3 顶点4 终 点 S1 d1 p1 S2 d2 p2 S3 d3 p3 S4 d4 p4 0 0 10 0 0 0 0 30 0 0 100 0 1 1 10 0 0 60 1 0 30 0 0 100 0 3 1 10 0 0 50 3 1 30 0 0 90 3 2

36、 1 10 0 1 50 3 1 30 0 0 60 2 4 1 10 0 1 50 3 1 30 0 1 60 2 如何从表中读取源点如何从表中读取源点0到终到终点点v的最短路径？举顶点的最短路径？举顶点4为例为例 path4=2 path2=3 path3=0，反过来排列，反过来排列，得到路径得到路径0,3,2,4，这就是源，这就是源点点0到终点到终点4的最短路径的最短路径。n源点源点0到终点到终点2的最短路径应是的最短路径应是0,1,2，其长度，其长度为为2，它小于算法中计算出来的，它小于算法中计算出来的dist2的值。的值。选取 顶 点0 顶 点1 顶 点2 顶点 S0 d0 p0 S

37、1 d1 p1 S2 d2 p2 0 1 0 -1 1 0 7 0 0 5 0 2 1 0 -1 1 0 7 0 1 5 0 1 1 0 -1 1 1 7 0 1 5 0 k d k0 d k1 d k2 d k3 d k4 d k5 dk6 1 0 6 5 5 2 0 3 3 5 5 4 3 0 1 3 5 2 4 7 4 0 1 3 5 0 4 5 5 0 1 3 5 0 4 3 6 0 1 3 5 0 4 3void Graph:BellmanFord(const int n,const int v)for(int i=0;i n;i+)disti=Edgevi;if(i!=v&dist

38、i MAXINT)pathi=v;else pathi=-1;for(int k=2;k n;k+)for(int u=0;u n;u+)if(u!=v)for(i=0;i 0&Edgeiu disti+Edgeiu)distu=disti+Edgeiu;pathu=i;void Graph:AllLengths(const int n)for(int i=0;i n;i+)/矩阵矩阵a与与path初始化初始化 for(int j=0;j n;j+)aij=Edgeij;if(i j&aij MAXINT)pathij=i;/i 到到 j 有路径有路径 else pathij=0;/i 到到

39、j 无路径无路径 for(int k=0;k n;k+)/产生产生a(k)及及path(k)for(i=0;i n;i+)for(j=0;j n;j+)if(aik+akj aij)aij=aik+akj;pathij=pathkj;/缩短路径长度缩短路径长度,绕过绕过 k 到到 j A(-1)A(0)A(1)A(2)A(3)0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 4 0 1 4 0 1 10 3 0 1 10 3 0 1 9 3 1 0 9 2 0 9 2 0 9 2 12 0 9 2 11 0 8 2 2 3 5 0 8 3 4 0 7

40、3 4 0 6 3 4 0 6 3 4 0 6 3 6 0 6 0 6 0 9 10 6 0 9 10 6 0 Path(-1)Path(0)Path(1)Path(2)Path(3)0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 3 1 1 0 0 1 1 0 0 1 1 0 0 1 1 2 0 1 1 2 0 3 1 2 2 2 0 2 2 0 0 0 2 0 0 1 2 0 0 1 2 0 0 1 3 0 0 3 0 0 0 3 0 0 0 3 0 2 0 3 0 2 0 3 0学

41、生课程学习工程图学生课程学习工程图 class Graph /friend class Vertex;friend class Edge;private:Vertex*NodeTable;int*count;int n;public:Graph(const int vertices=0):n(vertices)NodeTable=new vertexn;count=new intn;void TopologicalOrder();void Graph:TopologicalSort()int top=-1;/入度为零的顶点栈初始化入度为零的顶点栈初始化 for(int i=0;i n;i+)/

42、入度为零顶点进栈入度为零顶点进栈 if(counti=0)counti=top;top=i;for(i=0;i n;i+)/期望输出期望输出n个顶点个顶点 if(top=-1)/中途栈空中途栈空,转出转出 cout “网络中有回路网络中有回路(有向环有向环)endl;return;else /继续拓扑排序继续拓扑排序 int j=top;top=counttop;/退栈退栈 cout j endl;/输出输出 Edge*l=NodeTablej.adj;while(l)/扫描该顶点的出边表扫描该顶点的出边表 int k=ldest;/另一顶点另一顶点 if(-countk=0)/该顶点入度减一

43、该顶点入度减一 countk=top;top=k;/减至零减至零 l=llink;,),(ijjVVdurjVemaxiVe,),(jijVVdurjVlminiVl事件事件 Vei Vli V0 0 0 V1 6 6 V2 4 6 V3 5 8 V4 7 7 V5 7 10 V6 16 16 V7 14 14 V8 18 18 边边 活动活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e 0 0 0 6 4 5 7 7 7 16 14 l 0 2 3 6 6 8 7 7 10 16 14l-e 0 2 3 0 2 3 0 0 3 0 0关键关键 是是 是是 是是

44、是是 是是 是是void graph:CriticalPath()/在此算法中需要对邻接表中单链表的结点加以在此算法中需要对邻接表中单链表的结点加以/修改修改,在各结点中增加一个在各结点中增加一个int域域 cost,记录该结记录该结/点所表示的边上的权值点所表示的边上的权值。int i,j;int p,k;int e,l;Ve=new intn;Vl=new intn;for(i=0;i n;i+)Vei=0;for(i=0;i n;i+)Edge*p=NodeTablei.adj;while(p!=NULL)k=pdest;if(Vei+pcost Vek)Vek=Vei+pcost;p=plink;for(i=0;i n;i+)Vli=Ven-1;for(i=n-2;i;i-)p=NodeTablei.adj;while(p!=NULL)k=pdest;if(Vlk-pcost Vli)Vli=Vlk-pcost;p=plink;for(i=0;i n;i+)p=NodeTablei.adj;while(p!=NULL)k=pdest;e=Vei;l=Vlk-pcost;if(l=e)cout i ,k”“是关键活动是关键活动”endl;p=plink;