《第6章图.ppt》由会员分享，可在线阅读，更多相关《第6章图.ppt（99页珍藏版）》请在三一文库上搜索。
1、数据结构算法 Visual C+ 6.0程序集 侯 识 忠 等编著 中国水利水电出版社,第六章 图,6、0 图的类定义和实现 /图的相关数据类型的定义graph.h /最多顶点数 const int MaxV=10; /最大权值 const int MaxValue=99; /定义邻接表中的边结点类型 struct edgenode int adjvex; /邻接点域 int weight; /权值域 edgenode* next;/指向下一个边结点的链域 ; /定义邻接表类型 typedef edgenode* adjlist; /邻接矩阵类定义 class AdjMatrix privat
2、e:,char gMaxV;/顶点信息数组 int size;/当前顶点数 int GAMaxVMaxV;/定义邻接矩阵GA int numE;/当前边数 public: /构造函数,初始化图的邻接矩阵 AdjMatrix(int n,int k2); /判断图空否 bool GraphEmpty() return size=0; /取当前顶点数 int NumV() return size; /取当前边数 int NumEdges() return numE; /取顶点i的值 char GetValue(const int i); /取弧的权 int GetWeight(const int
3、v1,const int v2); /在位置pos处插入顶点V void InsertV(const char ,/插入弧,权为weight void InsertEdge(const int v1,const int v2,int weight); /删除顶点i与顶点i相关的所有边 char DeleteVE(const int i); /删除弧 void DeleteEdge(const int v1,const int v2); /建立图的邻接矩阵 void CreateMatrix(int n, int k1,int k2); /k1为0则无向否则为有向,k2为0则无权否则为有权 /从
4、初始点vi出发深度优先搜索由邻接矩阵表示的图 void dfsMatrix(bool*,/对非连通图进行深度优先搜索 void dfsMatrix(int n,int k2); /对非连通图进行广度优先搜索 void bfsMatrix(int n,int k2); ; /图的相关运算的实现graph.cpp #include“graph.h“ /构造函数,初始化图的邻接矩阵 AdjMatrix:AdjMatrix(int n,int k2) int i,j; if(k2=0)/初始化无(有)向无权图 for(i=0;in;i+) for(j=0;jn;j+) GAij=0; else /初始
5、化无(有)向有权图 for(i=0;in;i+) for(j=0;jn;j+) if(i=j) GAij=0; else GAij=MaxValue; size=numE=0;,/建立图的邻接矩阵 void AdjMatrix:CreateMatrix(int n,int k1,int k2) /k1为0则无向否则为有向,k2为0则无权否则为有权 int i,j,k,e,w; coute; if(k1=0 ,else if(k1!=0 ,/从初始点vi出发深度优先搜索由邻接矩阵表示的图 void AdjMatrix:dfsMatrix(bool*,/访问初始点vi coutgi:i“ “; /
6、标记初始点vi已访问过 visitedi=true; /将已访问过的初始点序号i入队 q+rear=i; /当队列非空时进行循环处理 while(front!=rear) /删除队首元素,第一次执行时k的值为i front=(front+1)%MaxLength; int k=qfront; /依次搜索vk的每一个可能的邻接点 for(int j=0;jn;j+) if(k2=0) if(k!=j,else if(k!=j /由图的邻接矩阵得到图的邻接表 void AdjMatrix:graphChange(adjlist &GL,int n,int k2),int i,j; if(k2=0)
7、 for(i=0;iadjvex=j; p-next=GLi;GLi=p; coutadjvexadjvex=j;p-weight=GAij; p-next=GLi;GLi=p; coutadjvexweight“) “; coutendl; ,/由图的邻接矩阵建立图 void AdjMatrix:Creatgraph(int n,int k2) int i,j,k,m=0; if(k2=0) for(i=0;in;i+) k=i; for(j=0;jn;j+) if(GAij!=0) if(k=ij+) if(GAij!=0 & GAij!=MaxValue),if(k=i ,/在位置pos
8、处插入顶点V void AdjMatrix:InsertV(const char /删除顶点v与顶点v相关的所有边 char AdjMatrix:DeleteVE(const int v),for(int i=0;i0,GAv1v2=MaxValue; numE-; /对非连通图进行深度优先搜索 void AdjMatrix:dfsMatrix(int n,int k2) bool *vis=new boolNumV(); for(int i=0;iNumV();i+) visi=false; for(i=0;iNumV();i+) if(!visi) dfsMatrix(vis,i,n,k2
9、); delete vis; /对非连通图进行广度优先搜索 void AdjMatrix:bfsMatrix(int n,int k2) bool *vis=new boolNumV(); for(int i=0;iNumV();i+) visi=false; for(i=0;iNumV();i+) if(!visi) bfsMatrix(vis,i,n,k2); delete vis; ,/图的相关运算的测试graphM.cpp #include #include #include #include “graph.cpp“ void main() coutn; AL=new edgenode
10、*n; vis=new booln; if(!vis) cout“申请堆内存失败!n“;exit(1);,for(i=0;ik1k2; /定义邻接矩阵 AdjMatrix A(n,k2); A.CreateMatrix(n,k1,k2); coutk; cout“n输出邻接矩阵相应图的每个顶点:n“; A.Creatgraph(n,k2); cout“当前的顶点数为:“A.NumV()endl; cout“当前的边数为:“A.NumEdges()endl; cout“图的深度优先搜索顺序:n“; A.dfsMatrix(vis,k,n,k2); for(i=0;in;i+) visi=fals
11、e; cout“n图的广度优先搜索顺序:n“; A.bfsMatrix(vis,k,n,k2); cout“n输出邻接表的每个邻接点:n“; for(i=0;in;i+) visi=false; A.graphChange(AL,n,k2);,单击此处运行程序,delete vis; A.DeleteEdge(0,2); A.DeleteEdge(2,0); cout“当前的顶点数为:“A.NumV()endl; cout“当前的边数为:“A.NumEdges()endl; cout“图的深度优先搜索顺序:n“; A.dfsMatrix(n,k2); cout“n图的广度优先搜索顺序:n“;
12、A.bfsMatrix(n,k2); cin.get();cin.get(); ,6、1 图的类定义和实现,/图的相关数据类型的定义graph0.h /最多顶点数 const int MaxV=10; /最大权值 const int MaxValue=99; /定义邻接表中的边结点类型 struct edgenode int adjvex; /邻接点域 int weight; /权值域 edgenode* next;/指向下一个边结点的链域 ; struct RCW int row,col; int weight; ; /定义邻接表类型 typedef edgenode* adjlist;,/
13、邻接矩阵类定义 class AdjMatrix private: char gMaxV;/顶点信息数组 int size;/当前顶点数 int GAMaxVMaxV;/定义邻接矩阵GA int numE;/当前边数 public: /构造函数,初始化图的邻接矩阵 AdjMatrix(int n,int k2); /判断图空否 bool GraphEmpty() return size=0; /取当前顶点数 int NumV() return size; /取当前边数 int NumEdges() return numE; /取顶点i的值 char GetValue(const int i);
14、/取弧的权 int GetWeight(const int v1,const int v2);,/在位置pos处插入顶点V void InsertV(const char ,/创建图 void Creatgraph(int n,int e,RCW r); /对非连通图进行深度优先搜索 void dfsMatrix(int n,int k2); /对非连通图进行广度优先搜索 void bfsMatrix(int n,int k2); ; /图的相关运算的实现graph0.cpp #include“graph0.h“ /构造函数,初始化图的邻接矩阵 AdjMatrix:AdjMatrix(int
15、n,int k2) int i,j; if(k2=0)/初始化无(有)向无权图 for(i=0;in;i+) for(j=0;jn;j+) GAij=0; else /初始化无(有)向有权图 for(i=0;in;i+) for(j=0;jn;j+) if(i=j) GAij=0;,else GAij=MaxValue; size=numE=0; /建立图的邻接矩阵 void AdjMatrix:CreateMatrix(int n,int k1,int k2,RCW r) /k1为0则无向否则为有向,k2为0则无权否则为有权 int i,j,k,e,w; coute; if(k1=0 ,/c
16、inijw; Check(n,i,j); GAij=GAji=w; else if(k1!=0 j+),coutsetw(4)GAij; coutendl; /从初始点vi出发深度优先搜索由邻接矩阵表示的图 void AdjMatrix:dfsMatrix(bool*,/定义队首和队尾指针 int front=0,rear=0; /访问初始点vi coutgi:i“ “; /标记初始点vi已访问过 visitedi=true; /将已访问过的初始点序号i入队 q+rear=i; /当队列非空时进行循环处理 while(front!=rear) /删除队首元素,第一次执行时k的值为i front
17、=(front+1)%MaxLength; int k=qfront; /依次搜索vk的每一个可能的邻接点 for(int j=0;jn;j+) if(k2=0) if(k!=j /标记vj已访问过,rear=(rear+1)%MaxLength;/顶点序号j入队 qrear=j; else if(k!=j ,/由图的邻接矩阵得到图的邻接表 void AdjMatrix:graphChange(adjlist ,coutsize) cerr的权 int AdjMatrix:GetWeight(const int v1,const int v2) if(v1size|v2size) cerr“参
18、数v1或v2越界!n“;exit(1); return GAv1v2; ,/在位置pos处插入顶点V void AdjMatrix:InsertV(const char ,/删除顶点v与顶点v相关的所有边 char AdjMatrix:DeleteVE(const int v) for(int i=0;i0 /删除弧 void AdjMatrix:DeleteEdge(const int v1,const int v2) if(v1size|v2size|v1=v2),cerr“参数v1或v2出错!n“;exit(1); GAv1v2=MaxValue; numE-; /对非连通图进行深度优先
19、搜索 void AdjMatrix:dfsMatrix(int n,int k2) bool *vis=new boolNumV(); int i; for(i=0;iNumV();i+) visi=false; for(i=0;iNumV();i+) if(!visi) dfsMatrix(vis,i,n,k2); delete vis; /对非连通图进行广度优先搜索 void AdjMatrix:bfsMatrix(int n,int k2) bool *vis=new boolNumV(); int i; for(i=0;iNumV();i+) visi=false; for(i=0;i
20、NumV();i+) if(!visi) bfsMatrix(vis,i,n,k2); delete vis;,/图的相关运算的测试graph0M.cpp #include #include #include #include “graph0.cpp“ void main() coutn; AL=new edgenode*n;,vis=new booln; if(!vis) coutk1k2; /定义邻接矩阵 AdjMatrix A(n,k2); A.CreateMatrix(n,k1,k2,rcw); coutk; cout“n输出邻接矩阵相应图的每个顶点:n“; A.Creatgraph(
21、n,e,rcw); cout“当前的顶点数为:“A.NumV()endl; cout“当前的边数为:“A.NumEdges()endl; cout“图的深度优先搜索顺序:n“; A.dfsMatrix(vis,k,n,k2); for(i=0;in;i+) visi=false; cout“n图的广度优先搜索顺序:n“; A.bfsMatrix(vis,k,n,k2); cout“n输出邻接表的每个邻接点:n“;,单击此处运行程序,for(i=0;in;i+) visi=false; A.graphChange(AL,n,k2); delete vis; A.DeleteEdge(0,2);
22、A.DeleteEdge(2,0); cout“当前的顶点数为:“A.NumV()endl; cout“当前的边数为:“A.NumEdges()endl; cout“图的深度优先搜索顺序:n“; A.dfsMatrix(n,k2); cout“n图的广度优先搜索顺序:n“; A.bfsMatrix(n,k2); cin.get();cin.get(); ,6、2 图的类定义和实现,/图的相关数据类型的定义graph1.h /最多顶点数 const int MaxV=10; /定义邻接表中的边结点类型 struct edgenode int adjvex; /邻接点域 int weight; /
23、权值域 edgenode* next; /指向下一个边结点的链域 edgenode() edgenode(int d,int w):adjvex(d),weight(w),next(NULL) ; struct Top /顶点数组的元素类型 char data;/顶点数据 edgenode *adj;/邻接表指针 ; struct RCW int row; int col; int weight;,/邻接表的类定义 class AdjAdjoin private: Top gMaxV;/顶点数组 int size; /顶点个数 int numE; /当前边的条数 public: edgenod
24、e *GL;/定义邻接表 /构造函数 AdjAdjoin() /构造函数,初始化图的邻接表 AdjAdjoin(edgenode *gl,int n); /判断图空否 bool GraphEmpty() return size=0; /取当前顶点数 int NumV() return size; /取当前边数 int NumEdges() return numE; /取顶点i的值 char GetValue(const int i);,/取弧的权 int GetWeight(const int v1,const int v2); /在位置pos处插入顶点V void InsertV(const
25、 char ,/检查输入的边序号是否越界,若越界则重输 void Check(int n,int,cine; if(k1=0 else if(k1=0 & k2!=0) /建立无向有权图 cout“输入“e,ijw; Check(n,i,j); /向序号i的单链表的表头插入一个边结点 edgenode *p=new edgenode; p-adjvex=j; p-weight=w; p-next=GLi; GLi=p; /向序号j的单链表的表头插入一个边结点 p=new edgenode; p-adjvex=i;p-weight=w; p-next=GLj; GLj=p; else if(k1
26、!=0,Check(n,i,j); /向序号i的单链表的表头插入一个边结点 edgenode* p=new edgenode; p-adjvex=j; p-weight=1; p-next=GLi; GLi=p; else if(k1!=0 ,/从初始点vi出发深度优先搜索由邻接表GL表示的图 void AdjAdjoin:dfsAdjoin(bool*,/访问初始点vi coutadjvex; /vj为vk的一个邻接点 if(!visitedj) /若vj没有被访问过则进行处理 coutgj.data:j“ “; visitedj=true; rear=(rear+1)%MaxLength;
27、/顶点序号j入队,qrear=j; p=p-next; /使p指向vk邻接表的下一个边结点 /检查输入的边序号是否越界,若越界则重输 void AdjAdjoin:Check(int n,int /取弧的权 int AdjAdjoin:GetWeight(const int v1,const int v2),if(v1size|v2size) cerradjvexnext; if(v2!=p-adjvex) cerr不存在!n“;exit(1); return p-weight; /在位置pos处插入顶点V void AdjAdjoin:InsertV(const char if(gv1.ad
28、j=NULL) /第一次插入,gv1.adj=q; else /非第一次插入 edgenode *curr=gv1.adj,*pre=NULL; while(curr!=NULL /删除顶点v与顶点v相关的所有边 void AdjAdjoin:DeleteVE(const int v),edgenode *pre,*curr; for(int i=0;iadjvexnext; if(pre=NULL,for(i=v;inext; delete p; /释放空间 p=q; numE-; /删除弧 void AdjAdjoin:DeleteEdge(const int v1,const int v
29、2) if(v1size|v2size|v1=v2) cerradjvexnext; if(pre=NULL&curr-adjvex=v2)/要删除的结点是链表的第一结点,gv1.adj=curr-next; delete curr; numE-; else if(curr!=NULL,delete p;p=GLi; delete GL; /对非连通图进行深度优先搜索 void AdjAdjoin:dfsAdjoin(int n) bool *vis=new boolNumV(); for(int i=0;iNumV();i+) visi=false; for(i=0;iNumV();i+)
30、if(!visi) dfsAdjoin(vis,i,n); delete vis; /对非连通图进行广度优先搜索 void AdjAdjoin:bfsAdjoin(int n) bool *vis=new boolNumV(); for(int i=0;iNumV();i+) visi=false; for(i=0;iNumV();i+) if(!visi) bfsAdjoin(vis,i,n); delete vis;,void AdjAdjoin:CreatGraph(char V,int n,RCW E,int e) for(int i=0;i #include #include #in
31、clude “graph1.cpp“ void main() cout“graph1M.cpp运行结果:n“; char a=A,B,C,D,E,F,G; RCW rcw=0,1,1,0,2,1,1,3,1,1,4,1,2,5,1, 2,6,1,1,0,1,2,0,1,3,1,1,4,1,1,5,2,1,6,2,1; /定义图的点数及搜索起始点序号等,int n,k,i; /k1为0则无向否则为有向,k2为0则无权否则为有权 int k1,k2; /标记已访问过的点 bool *vis; coutn; vis=new booln; if(!vis) coutk1k2; edgenode *gl
32、=new edgenode*n; AdjAdjoin B(gl,n); B.CreatGraph(a,n,rcw,12); coutk; cout“当前的顶点数为:“B.NumV()endl; cout“当前的边数为:“B.NumEdges()endl; cout“表的深度优先搜索顺序:n“;,单击此处运行程序,B.dfsAdjoin(vis,k,n);coutendl; cout“表的广度优先搜索顺序:n“; for(i=0;in;i+) visi=false; B.bfsAdjoin(vis,k,n);coutendl; B.DeleteEdge(0,2); B.DeleteEdge(2,
33、0); cout“当前的顶点数为:“B.NumV()endl; cout“当前的边数为:“B.NumEdges()endl; cout“表的深度优先搜索顺序:n“; B.dfsAdjoin(n);coutendl; cout“表的广度优先搜索顺序:n“; for(i=0;in;i+) visi=false; B.bfsAdjoin(n);coutendl; B.DeleteAdjoin(n); cin.get();cin.get(); ,6、3 利用普里姆算法求出用邻接矩阵表示的图的最小生成树,/利用普里姆算法求出用邻接 /矩阵表示的图的最小生成树 /图的相关数据类型的定义graph2.h /
34、最多顶点数 const int MaxV=10; /最大权值 const int MaxValue=99; /定义边集数组中的元素类型 struct edge int fromvex; /起点域 int endvex; /终点域 int weight; /权域 ; struct RCW int row,col; int weight; ;,/类定义 class adjMList private: int numE;/当前边数 int GAMaxVMaxV;/定义邻接矩阵 public: /构造函数,初始化图的邻接矩阵与边集数组 adjMList(edge GE,int n,int e); /建
35、立无向带权图的邻接矩阵 void CreateMatrix(int n,int ,/检查输入的边序号是否越界,若越界则重输 void Check(int n, int,cout0,cout=n |j=n) coutij; /根据图的邻接矩阵生成图的边集数组 void adjMList:ChangeEdgeSet(edge GE,int n,int e) /假定只考虑无向图的情况 int i,j,k=0; for(i=0; in; i+) for(j=i+1; jn; j+),if(GAij!=0 ,/利用普里姆算法从顶点v0出发求出用邻接矩阵GA表示 /的图的最小生成树,最小生成树的边集存于数
36、组CT中 void adjMList:Prim(edge CT,int n) int i,j, k, min, t, m, w; /给CT赋初值，对应为v0依次到其余各顶点的边 for(i=0; in-1; i+) CTi.fromvex=0; CTi.endvex=i+1; CTi.weight=GA0i+1; /进行n-1次循环，每次求出最小生成树中的第k条边 for(k=1; kn; k+) /从CTk-1CTn-2中查找最短边CTm min=MaxValue; m=k-1; for(j=k-1; jn-1; j+) if(CTj.weightmin) min=CTj.weight; m
37、=j; /把最短边对调到第k-1下标位置 edge temp=CTk-1;,CTk-1=CTm; CTm=temp; /把新并入最小生成树T中的顶点序号赋给j j=CTk-1.endvex; /修改有关边，使T中到T外的每一个顶点各保持 /一条到目前为止最短的边 for(i=k; i #include #include #include “graph2.cpp“ void main() cout“graph2M.cpp运行结果:n“;,单击此处运行程序,RCW rcw20=0,1,50,1,0,50,0,2,60,2,0,60, 1,3,65,3,1,65,1,4,40,4,1,40,2,3,
38、52, 3,2,52,2,6,45,6,2,45,3,4,50,4,3,50, 3,5,30,5,3,30,3,6,42,6,3,42,4,5,70,5,4,70; int n,k;/定义图的点数及边数等 coutn; coutk; static edge AE30,BE30;/定义边集数组 adjMList A(AE,n,k); A.CreateMatrix(n,k,rcw); cout“输出边集数组中的每条边:n“; A.ChangeEdgeSet(AE,n,k); A.OutputEdgeSet(AE,k); cout“输出按升序排列的图的边集数组:n“; A.SortEdgeSet(A
39、E,k); A.OutputEdgeSet(AE,k); A.Prim(BE,n); cout“输出最小生成树的边集数组:n“; A.OutputEdgeSet(BE,k); cin.get();cin.get();,6、4 利用克鲁斯卡尔方法求边集数组所示图的最小生成树,/利用克鲁斯卡尔方法求边集 /数组所示图的最小生成树 /图的相关数据类型的定义graph3.h /最多顶点数 const int MaxV=10; /最大权值 const int MaxValue=99; /定义邻接表中的边结点类型 struct edgenode int adjvex; /邻接点域 int weight;
40、/权值域 edgenode* next; /指向下一个边结点的链域 ; /定义邻接表类型 typedef edgenode* adjlist;,/定义边集数组中的元素类型 struct edge int fromvex; /起点域 int endvex; /终点域 int weight; /权域 ; struct RCW int row,col; int weight; ; /类定义 class adjMList private: int numE;/当前边数 int GAMaxVMaxV;/定义邻接矩阵 public: /构造函数,初始化图的邻接矩阵与边集数组 adjMList(edge G
41、E,int n,int e); /初始化图的邻接表 void InitGAdjoin(adjlist,/删除图的邻接表 void DeleteAdjoin(adjlist GL,int n); /建立带权图的邻接矩阵 void CreateMatrix(int n,int i+),for(j=0; jnext; delete p;p=GLi; delete GL;,/输出边集数组中的每条边 void adjMList:OutputEdgeSet(edge ge,int e) int i,k=0; cout0)k+; cout0,do i=rk.row;j=rk.col;w=rk.weight;
42、 /cinijw; Check(n,i,j); if(k=e-1) break; GAij=GAji=w;k+; while(1); numE=e=k; cout=n |j=n) coutij;,/根据图的邻接矩阵生成图的边集数组 void adjMList:ChangeEdgeSet(edge GE,int n,int e) /假定只考虑无向图的情况 int i,j,k=0; for(i=0; i=0; j-) if(x.weightGEj.weight) GEj+1=GEj; else break; GEj+1=x; edgenode* p;,/定义邻接表s作为集合使用,其中 /每一个单链
43、表si用来表示一个集合 adjlist s; /初始化邻接表s InitGAdjoin(s,n); /初始化s集合,使每一个顶点分属于不同的集合 for(i=0; iadjvex=i;p-next=NULL; si=p; int k=1; /k表示待获取的最小生成树中的边数,初值为1 int d=0; /d表示GE中待扫描边元素的下标位置,初值为0 /m1和m2用来分别记录一条边的两个顶点所在集合的序号 int m1,m2; /进行n-1次循环,得到最小生成树中的n-1条边 while(kn) /求边GEd的两个顶点所在集合的序号m1和m2 for(i=0; in; i+) p=si; whi
44、le(p!=NULL) ,/图的相关运算的测试graph3M.cpp #include #include #include #include “graph3.cpp“ void main() coutn; coutk; adjMList B(AE,n,k); B.CreateMatrix(n,k,rcw); /由图的邻接矩阵生成图的边集数组 B.ChangeEdgeSet(AE,n,k); cout“输出邻接矩阵生成图的边集数组:n“;,单击此处运行程序,B.OutputEdgeSet(AE,k); cout“输出最小生成树的边集数组:n“; B.Kruskal(AE,BE,n); B.Out
45、putEdgeSet(BE,k); cin.get();cin.get();,6、5 狄克斯特拉算法、从一个顶点到其余各顶点的最短路径,/最短路径(狄克斯特拉算法)PshortP.h /从一个顶点到其余各顶点的最短路径 void PShortPath(AdjMatrix j+),if(sj=0 /最短路径算法PshortPM.cpp #include #include,#include #include “graph0.cpp“ #include “PshortP.h“ /狄克斯特拉算法测试 void main() cout“PShortPM.cpp运行结果:n“; int n=6,e=9,k
46、2=1; RCW rcw=0,2,5,0,3,30,1,0,2,1,4,8, 2,1,15,2,5,7,4,3,4,5,3,10,5,4,18; AdjMatrix g(n,k2); g.Creatgraph(n,e,rcw); int m=g.NumV(); int *dist=new intm; int *path=new intm; int v0=0; PShortPath(g,v0,dist,path); cout“从顶点“g.GetValue(v0) “到其他各顶点的最短距离为:n“; for(int i=0;im;i+) cout“到顶点“g.GetValue(i),单击此处运行程序,“的最短距离为:“distiendl; cout“从顶点“g.GetValue(v0) “到其他各顶点的最短路径的前一顶点为:n“; for(i=0;im;i+) if(pathi!=-1) co