实验报告图的操作

1、实验 7： 图的操作算法一、实验目的1. 熟悉各种图的存储结构。 2. 掌握图的各种搜索路径的遍历方法。 二、实验内容1. 设计一个有向图和一个无向图，任选一种存储结构， 完成有向图和无向图的DFS（深度优先遍历）和BFS（广度优先遍历）的操作。 算法： #include #include #include #include #define MAXV 10#define INF 980708 using namespace std; typedef int InfoType;/邻接矩阵typedef structint no;InfoType info;VertexType;/顶点类型type

2、def structint edgesMAXVMAXV; int n,e;VertexType vexsMAXV; MatGraph;/完整的图邻接矩阵类型/邻接表typedef struct ANodeint adjvex;struct ANode *nextarc; int weight; ArcNode;/边结点类型typedef struct VnodeInfoType info;ArcNode *firstarc; VNode;/邻接表的头结点类型typedef structVNode adjlistMAXV; int n,e; AdjGraph;/完整的图邻接表类型typedef

3、structInfoType dataMAXV; int front,rear;SqQueue; /队列/初始化队列void InitQueue(SqQueue *&q)q=(SqQueue*)malloc(sizeof(SqQueue); q-front=q-rear=-1;/判断队列是否为空bool QueueEmpty(SqQueue *q)return(q-front=q-rear);/进队列bool enQueue(SqQueue *&q,InfoType e)if(q-rear=MAXV)return false; q-rear+;q-dataq-rear=e; return tr

4、ue;/出队列bool deQueue(SqQueue *&q,InfoType &e)if(q-front=q-rear)return false; q-front=(q-front+1)%MAXV; e=q-dataq-front;return true;/创建邻接表void CreateAdj(AdjGraph *& G,int AMAXVMAXV,int n,int e)int i,j;ArcNode *p;G=(AdjGraph*)malloc(sizeof(AdjGraph);for(i=0;iadjlisti.firstarc=NULL; for(i=0;i=0;j-)if(Ai

5、j!=0&Aij!=INF)p=(ArcNode*)malloc(sizeof(ArcNode); p-adjvex=j;p-nextarc=G-adjlisti.firstarc; G-adjlisti.firstarc=p;G-n=n;G-e=e;/输出邻接表void DispAdj(AdjGraph *G)cout邻接表存储：endl; int i;ArcNode *p;for(i=0;in;i+)p=G-adjlisti.firstarc; printf(%3d:,i);printf(%3d -,i); while(p!=NULL)printf(%3d -,p-adjvex); p=p

6、-nextarc;coutendl;/DFS 深度优先遍历int visitedMAXV=0;void DFS(AdjGraph *G,int v)ArcNode *p; visitedv=1; coutadjlistv.firstarc; while(p!=NULL)if(visitedp-adjvex=0) DFS(G,p-adjvex);p=p-nextarc;/BFS 广度优先遍历void BFS(AdjGraph *G,int v)int w,i;ArcNode *p; SqQueue *qu;InitQueue(qu);int visited1MAXV; for(int i=0;i

7、n;i+)visited1i=0; printf(%2d,v);visited1v=1;enQueue(qu,v);while(!QueueEmpty(qu)deQueue(qu,w);p=G-adjlistw.firstarc; while(p!=NULL)if(visited1p-adjvex=0)printf(%2d,p-adjvex); visited1p-adjvex=1;enQueue(qu,p-adjvex);p=p-nextarc;coutendl;/销毁邻接表void DestroyAdj(AdjGraph *&G)int i;ArcNode *pre,*p; for(i=0

8、;in;i+)pre=G-adjlisti.firstarc; if(pre!=NULL)p=pre-nextarc; while(p!=NULL)free(pre);pre=p;p=p-nextarc;free(pre);free(G);/创建邻接矩阵voidCreatMat(MatGraph *&G,int n,int e)int i,i1,j,j1,num1,num2;G=(MatGraph*)malloc(sizeof(MatGraph);/邻接矩阵初始化for(i=0;in;i+)for(j=0;jedgesij=0;/顶点信息cout请输入顶点编号endl; for(i=0;iG-

9、vexsi.no;/边信息for(i=0;ie;i+)cout请输入起始端点编号和终止端点编号i1j1;for(j=0;jvexsj.no=i1) num1=j;if(G-vexsj.no=j1) num2=j;G-edgesnum1num2=1;G-n=n;G-e=e;/输出邻接矩阵voidDispMat(MatGraph *G)cout邻接矩阵存储：endl; couttt;for(int i=0;in;i+)coutvexsi.not; coutendl;for(int i=0;in;i+)couttvexsi.not;for(int j=0;jn;j+)coutedgesijt; co

10、utendl;int main()int n,e,v,v1;MatGraph *G; AdjGraph *p;cout请输入顶点个数n;cout请输入边的个数e;CreatMat(G,n,e); DispMat(G);CreateAdj(p,G-edges,n,e); DispAdj(p);coutv;DFS(p,v);coutendl;coutv1;BFS(p,v1);cout销毁图endl;DestroyAdj(p);测试数据： 有向图：12无向图：43513425运行结果：存在问题：无2. 求两点之间最短路径。算法设计： /求两点之间最短路径。#include#include #incl

11、ude #include #define INF 32767#define MAXV 100 using namespace std; typedef char InfoType;/以下定义邻接矩阵类型typedef structint no;/顶点编号InfoType info;/顶点其他信息 VertexType;/顶点类型typedef structint edgesMAXVMAXV;/邻接矩阵数组int n,e;/顶点数，边数VertexType vexsMAXV;/存放顶点信息 MatGraph;/完整的图邻接矩阵类型void CreateMat(MatGraph &g,int AM

12、AXVMAXV,int n,int e) /创建图的邻接矩阵int i,j;g.n=n; g.e=e;for (i=0;ig.n;i+)for (j=0;jg.n;j+)g.edgesij=Aij;void DispMat(MatGraph g)/输出邻接矩阵 gint i,j;for (i=0;ig.n;i+)for (j=0;jg.n;j+)if (g.edgesij!=INF)printf(%4d,g.edgesij);elseprintf(%4s,);coutendl;void Dispath(MatGraph g,int dist,int path,int S,int v)/输出从顶

13、点 v 出发的所有最短路径int i,j,k;int apathMAXV,d;/存放一条最短路径(逆向)及其顶点个数for (i=0;ig.n;i+)/循环输出从顶点 v 到 i 的路径if (Si=1 & i!=v)cout从顶点v到顶点i的路径长度为:disti路径为:; d=0; apathd=i;/添加路径上的终点k=pathi;if (k=-1)/没有路径的情况cout无路径endl;else/存在路径时输出该路径while (k!=v)d+; apathd=k; k=pathk;d+; apathd=v;/添加路径上的起点cout=0;j-) /再输出其他顶点cout,apathj

14、;coutendl;void Dijkstra(MatGraph g,int v)/Dijkstra 算法int distMAXV,pathMAXV;int SMAXV;/Si=1 表示顶点 i 在 S 中, Si=0 表示顶点 i 在 U 中int Mindis,i,j,u; for (i=0;ig.n;i+)disti=g.edgesvi;/距离初始化Si=0;/S置空if (g.edgesviINF)/路径初始化pathi=v;/顶点 v 到顶点 i 有边时，置顶点 i 的前一个顶点为 velsepathi=-1;/顶点 v 到顶点 i 没边时，置顶点 i 的前一个顶点为-1Sv=1;p

15、athv=0;/源点编号 v 放入 S 中for (i=0;ig.n-1;i+)/循环直到所有顶点的最短路径都求出Mindis=INF;/Mindis 置最大长度初值for (j=0;jg.n;j+)/选取不在 S 中（即 U 中）且具有最小最短路径长度的顶点 u if (Sj=0 & distjMindis)u=j;Mindis=distj;Su=1;/顶点 u 加入 S 中for (j=0;jg.n;j+)/修改不在 S 中（即 U 中）的顶点的最短路径if (Sj=0)if (g.edgesujINF & distu+g.edgesujdistj)distj=distu+g.edgesu

16、j; pathj=u;Dispath(g,dist,path,S,v); /输出最短路径int main()MatGraph g;int AMAXVMAXV= 0 , 4 ,INF,INF,INF, 0 , 1 ,INF, 4 ,INF, 0 , 2 , 3 ,INF,INF, 0;int n=4, e=8;CreateMat(g,A,n,e);/建立教程中图 8.35 的邻接矩阵cout图 G 的邻接矩阵:endl;DispMat(g);/输出邻接矩阵int v;cout输入一顶点：v;cout从v顶点出发的最短路径如下:endl; Dijkstra(g,v);测试数据：图：0 413413

17、22运行结果：存在问题：无3、实现一个有向图的拓扑排序。 算法设计： #include #include #include #include #define MAXV 10#define INF 980708 using namespace std; typedef int InfoType;/邻接矩阵typedef structint no;InfoType info;VertexType;/顶点类型typedef structint edgesMAXVMAXV; int n,e;VertexType vexsMAXV; MatGraph;/完整的图邻接矩阵类型/邻接表typedef str

18、uct ANodeint adjvex;struct ANode *nextarc; int weight; ArcNode;/边结点类型typedef struct VnodeInfoType info;int count; ArcNode *firstarc; VNode;/邻接表的头结点类型typedef structVNode adjlistMAXV;int n,e; AdjGraph;/完整的图邻接表类型/创建邻接表void CreateAdj(AdjGraph *& G,int AMAXVMAXV,int n,int e)int i,j; ArcNode *p;G=(AdjGrap

19、h*)malloc(sizeof(AdjGraph); for(i=0;iadjlisti.firstarc=NULL; for(i=0;i=0;j-) if(Aij!=0&Aij!=INF)p=(ArcNode*)malloc(sizeof(ArcNode);p-adjvex=j;p-nextarc=G-adjlisti.firstarc; G-adjlisti.firstarc=p;G-n=n;G-e=e;/输出邻接表void DispAdj(AdjGraph *G)cout邻接表存储：endl; int i;ArcNode *p;for(i=0;in;i+)p=G-adjlisti.fi

20、rstarc;printf(%3d:,i);printf(%3d -,i); while(p!=NULL)printf(%3d -,p-adjvex); p=p-nextarc;coutendl;/销毁邻接表void DestroyAdj(AdjGraph *&G)int i;ArcNode *pre,*p; for(i=0;in;i+)pre=G-adjlisti.firstarc; if(pre!=NULL)p=pre-nextarc;while(p!=NULL)free(pre); pre=p;p=p-nextarc;free(pre);free(G);/创建邻接矩阵voidCreatM

21、at(MatGraph *&G,int n,int e)int i,i1,j,j1,num1,num2;G=(MatGraph*)malloc(sizeof(MatGraph);/邻接矩阵初始化for(i=0;in;i+)for(j=0;jedgesij=0;/顶点信息cout请输入顶点编号endl; for(i=0;iG-vexsi.no;/边信息for(i=0;ie;i+)cout请输入起始端点编号和终止端点编号i1j1;for(j=0;jvexsj.no=i1)num1=j;if(G-vexsj.no=j1) num2=j;G-edgesnum1num2=1;G-n=n;G-e=e;/拓

22、扑排序算法void TopSort(AdjGraph *G)/拓扑排序算法int i,j;int StMAXV,top=-1;/栈St的指针为top ArcNode *p;for (i=0;in;i+)/入度置初值0 G-adjlisti.count=0;for (i=0;in;i+)/求所有顶点的入度 p=G-adjlisti.firstarc; while (p!=NULL)G-adjlistp-adjvex.count+; p=p-nextarc;for (i=0;in;i+)/将入度为0的顶点进栈if (G-adjlisti.count=0)top+; Sttop=i;while (top-1)/栈不空循环 i=Sttop;top-;/出栈一个