1、数据结构课程设计图的实现数据结构课程设计图的基本操作与实现#include using namespace std;typedef char VertexType;#include Graph.h#include UDGraph.h#include UNGraph.h#include DGraph.h#include DNGraph.hvoid ShowMainMenu()coutn;cout *图的基本操作及应用*n;cout * 1 无向图的基本操作及应用 *n;cout * 2 无向网的基本操作及应用 *n;cout * 3 有向图的基本操作及应用 *n;cout * 4 有向网的基本操
2、作及应用 *n;cout * 5 退出 *n;cout *n;void UDG()MGraph MG;ALGraph ALG;int n;docoutn;cout *无向图的基本操作及应用*n;cout * 1 创建无向图的邻接矩阵 *n;cout * 2 创建无向图的邻接表 *n;cout * 3 无向图的深度优先遍历 *n;cout * 4 无向图的广度优先遍历 *n;cout * 5 退出 *n;coutn;switch(n)case 1:CreatUDG_M(MG);break;case 2:CreatUDG_ALG(ALG);dispgraph(ALG);break;case 3:C
3、reatUDG_ALG(ALG); dfstraverse(ALG);break;case 4:CreatUDG_M(MG);BFSTraver(MG);break;default:if (n!=5)cout错误，重新输入n;while(n!=5);void UDN() MGraph MG;ALGraph ALG;int n;docoutn;cout *无向网的基本操作及应用*n;cout * 1 创建无向网的邻接矩阵 *n;cout * 2 创建无向网的邻接表 *n;cout * 3 prim算法求最小生成树 *n;cout * 4 kraskal算法求最小生成树 *n;cout * 5 退
4、出 *n;coutn;switch(n)case 1:CreateUDN_M(MG);break;case 2: CreateUDN(ALG);dispUDN(&ALG);break;case 3:CreateUDN_M(MG);prim(MG);break;case 4:CreateUDN_M(MG);Kruskal(MG);break;default:if (n!=5)cout错误，重新输入n;while(n!=5);void DG() MGraph MG;ALGraph ALG;int n;docoutn;cout *有向图的基本操作及应用*n; cout * 1 创建有向图的邻接矩阵
5、*n;cout * 2 创建有向图的邻接表 *n; cout * 3 拓扑排序 *n;cout * 4 退出 *n; coutn;switch(n)case 1:CreatDG_M(MG);break;case 2: CreatDG_ALG(ALG);dispgraph(ALG);break;case 3:CreatDG_ALG(ALG);TopologicalSort(ALG);break;default:if (n!=4)cout错误，重新输入n;while(n!=4);void DN() MGraph MG;ALGraph ALG;int n; PathMatrix p1; ShortP
6、athTable d1; dist2 d; path2 p;docoutn;cout *有向网的基本操作及应用*n; cout * 1 创建有向网的邻接矩阵 *n;cout * 2 创建有向网的邻接表 *n; cout * 3 关键路径 *n;cout * 4 单源顶点最短路径问题 *n;cout * 5 每对顶点最短路径问题 *n;cout * 6 退出 *n; coutn;switch(n)case 1: CreateDNG_M(MG);break;case 2: CreateDN(ALG);dispDN(&ALG);break;case 3:CreateDN(ALG);CriticalP
7、ath(ALG);break;case 4: CreateDNG_M(MG); ShortestPath(MG,1,p1,d1);break;case 5: CreateDNG_M(MG);Floyd(MG,p,d);break;default:if (n!=6)coutn;switch(n)case 1:UDG();break;case 2: UDN();break;case 3:DG();break;case 4:DN();break;default:if (n!=5)cout错误，重新输入n;while(n!=5);/Graph.h(图的定义）#define MAXVEX 30#defi
8、ne MAXCOST 1000typedef int InfoType;typedef structVertexType vexsMAXVEX; int arcsMAXVEXMAXVEX; int vexnum,arcnum;MGraph;typedef struct arcnodeint adjvex;/邻接点序号int w;/边或狐上的权InfoType *info;struct arcnode *next;ArcNode;typedef struct vnode VertexType data; /顶点信息int indegree;ArcNode *firstarc; /指向下一个边结点
9、Vnode,AdjListMAXVEX;typedef structAdjList vertices;int vexnum,arcnum;ALGraph;/UDGraph.h（无向图的基本操作及应用）void CreatUDG_M(MGraph &G) int i,j,c; coutG.vexnum;cinG.arcnum; cout请输入结点信息，如“1 2 3 .endl;for(i=1;iG.vexsi;for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)G.arcsij=0;for(c=1;c起点序号,终点序号:,c);cinij; G.arcsij
10、=1; G.arcsji=1;cout创建的邻接矩阵为：endl;for(int i=1;i=G.vexnum;i+)for(int j=1;j=G.vexnum;j+)coutG.arcsij ;coutendl;cout邻接矩阵创建完毕endl;/void CreatUDG_ALG(ALGraph &G) int i,s,d; ArcNode *p,*q;coutG.vexnum;cinG.arcnum;cout请输入结点信息，如“1 2 3 .endl; for (i=1;iG.verticesi.data; G.verticesi.firstarc=NULL; for (i=1;i起点
11、序号,终点序号:,i); cinsd; p=(ArcNode *)malloc(sizeof(ArcNode); q=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=d; q-adjvex=s; p-next=G.verticess.firstarc; /p插入顶点s的邻接表中 G.verticess.firstarc=p; q-next=G.verticesd.firstarc; /q插入顶点d的邻接表中 G.verticesd.firstarc=q; void dispgraph(ALGraph G) int i; ArcNode *p; print
12、f(图的邻接表表示如下:n); for (i=1;i,i,G.verticesi.data); p=G.verticesi.firstarc; while (p!=NULL)printf(%d,p-adjvex);p=p-next;printf(n);/int visit20;void dfs(ALGraph G,int v)/从顶点v出发深度优先搜索 visitv=1;coutadjvex!=1)dfs(G,p-adjvex);p=p-next;/whilevoid dfstraverse(ALGraph G)/对一个图进行深度优先搜索 int v;for(v=1;v=G.vexnum;v+
13、)if(!visitv) dfs(G,1);/#include CirQueue.hint FirstAdjVex(MGraph G,int vex)int w,i;for(i=1;i=G.vexnum;i+)if(G.arcsvexi=1&visiti=0)w=i;break;else w=0;return w;/获取下一个未被访问的邻接节点int NextAdjVex(MGraph G,int vex,int w)int i;for(i=w;i=G.vexnum;i+) /从w开始if(G.arcsvexi=1&visiti=0)w=i;break;else w=0;return w;vo
14、id BFSTraver(MGraph G)Queue q;InitQueue(&q);int i,w,u;for(i=1;i=G.vexnum;i+)visiti=0;for(i=1;i=G.vexnum;i+)/确保所有的节点被访问到的一个循环if(visiti=0)visiti=1;couti0)if(visitw=0)visitw=1;couti;EnQueue(&q,w);w=NextAdjVex(G,u,w);/UNGraph.h（无向网的基本操作及应用）void CreateUDN_M(MGraph &G)int i,j,k,n;cout请输入顶点数和边数G.vexnum;cin
15、G.arcnum;cout输入顶点endl;for(i=1;iG.vexsi;for(i=1;i=G.vexnum;i+)for(j=1;j=G.vexnum;j+)G.arcsij=999;cout输入边的起点到终点的序号及权值endl;for(k=1;kijn;G.arcsij=n;G.arcsji=G.arcsij;cout创建的邻接矩阵为：endl;for(int i=1;i=G.vexnum;i+)for(int j=1;j=G.vexnum;j+)coutG.arcsij ;coutendl;cout邻接矩阵创建完毕endl;/建立无向网的邻接矩阵存储结构/void CreateU
16、DN(ALGraph &G) / 邻接表建立无向网 int i,s,d,w1; ArcNode *p,*q;cout输入节点数和边数G.vexnumG.arcnum;cout输入顶点，如“1 2 3.”endl;for(i=1;iG.verticesi.data; / 输入顶点 G.verticesi.firstarc=NULL; / 首先初始化为NULL cout输入边的起点到终点的序号及权值endl;for(i=1;isdw1; / 输入一条边依附的起点序号和终点序号 p =(ArcNode *)malloc(sizeof(ArcNode); q =(ArcNode *)malloc(si
17、zeof(ArcNode); p-info=(InfoType *)malloc(sizeof(InfoType); q-info=(InfoType *)malloc(sizeof(InfoType); p-adjvex = d; / 保存该弧所指向的顶点位置 q-adjvex = s; / 保存该弧所指向的顶点位置 *(p-info) = w1; / 保存权值到一个结点里 *(q-info) = w1; /保存权值到一个结点里 p-next=G.verticess.firstarc; G.verticess.firstarc=p; q-next=G.verticesd.firstarc;
18、G.verticesd.firstarc=q; void dispUDN(ALGraph *G) /* 打印无向网每个结点的单链表 */int i, j;cout起点 权值 终点endl;for(i = 1 ; i vexnum ; i+) while(G-verticesi.firstarc-next) coutverticesi.dataverticesi.firstarc-adjvex;coutverticesi.firstarc-info) verticesj.dataverticesi.firstarc = G-verticesi.firstarc-next; coutverticesi.datavertic
