算法与数据结构课程设计报告系（院）：计算机科学学院专业班级：教技1001姓名：李##学号： ******### 指导教师：***设计时间：2012.6.16 - 2012.6.24设计地点：4号楼2号机房目录一、设计方案 (1)二、实现过程以及代码 (2)三、测试 (20)四、结论和分析 (23)五、难点和收获 (23)一、 设计方案1.程序设计基本过程：拿到课程设计任务书，按照要求，需要设计有向图、有向网、无向图 、无向网四种图，以及邻接矩阵、邻接表两种数据存储结构，三层以上的显示菜单。

图的操作中又包含了有关线性表、栈和队列的基本操作。

由于显示菜单已给出，剩下的任务就是把函数写入其中。

2.程序流程图：预定义 定义结构体 定义变量 各种函数3.程序设计的原理：图的操作都是以两种存储结构为基础的：邻接矩阵存储结构和邻接表存储结构，如有向图，有向网，无向图，无向网的创建，其他的操作都是在四种图创建后才开始进行的。

所以，首先必须理解两种存储结构的定义。

图的邻接矩阵存储结构即图的数组表示法。

用两个数组分别存储数据元素（如顶点）的信息和数据元素之间的关系（如边或弧）的信息。

用邻接矩阵存储结构的图具有以下几点特征：（一）：顶点数：vexnum ，边（弧）数：arcnum ，图的种类：kind ；（二）：邻接矩阵：arcs(1顶点关系类型:adj 2相关信息:*info)；（三）：顶点向量（顶点名）：vexs[]；其优点是以二维数组表示有n 个顶点的图时，需存放n 个顶点的信息和n*n 条弧的信息存储量。

借助邻接矩阵容易判定任意两个顶点之间是否有边或弧相连，并容易求出各个顶点的度。

缺点是时间复杂度是O （n*n ）,例如，构造一个具有n 个顶点和e 条边的无向网的时间复杂度为O （n*n+e*n ）。

图的邻接表存储结构是图的一种链式存储结构。

对图中的每个顶点建立一个单链表，每个结点由三个域组成，邻接点域adjvex （弧尾在邻接表链表中的位序），链域nextarc （下一条弧），数据域info(权值)。

还要建立一个邻接表链表，用以存放顶点的data 和后继指针firstarc,表头结点以顺序结构的形式存储，便于随机访问任一顶点的单链表。

邻接表存储结构的优点在于其时间复杂度小。

树的深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。

从图中的某个顶点出发，访问此顶点，然后依次从该顶点出发深度优先搜索遍历图，直至图中所有与该顶点有关的路径都被访问到；此时图中若还有顶点未被访问到，则另选图中的一个未被访问的顶点作为起始点，重述上述过程，直至所有顶点都被访问到。

广度优先搜索遍历类似于树的按层次遍历的过程。

以某个顶点为起始顶点，由近至远，依次访问和该顶点有路径相通的且路径长度为1，2，3，······的顶点。

当图中所有顶点都被访问到后，就完成了图的广度优先搜索遍历。

求无向网的最小生成树问题有两种算法：Prima算法和Kruskal算法。

Prima算法是从网中的某个顶点出发，选择与该顶点有路径的所有顶点中路径最小的一条路径，从该最小路径的另一顶点出发，重复上述过程，直至图中所有顶点都被访问完成。

Kruskal算法是从网中找出所有路径最小的一条路径，记下已访问该路径的两个顶点，再次从图中找出剩下路径中的最小路径，重复上述过程，直至所有顶点都被访问完成，按访问的顺序依次输出各顶点，即构造了一棵最小生成树。

由某个集合上的一个偏序得到该集合的一个全序的操作就叫做拓扑排序。

拓扑排序的过程：（1）在有向图中选择一个没有前驱的顶点并输出；（2）在图中删除该顶点和所有以它为尾的弧。

重复上述两步，直至全部顶点均已输出，就得到了一个拓扑有序序列。

求关键路径的算法如下：(1)输入e条弧，建立AOE网的存储结构；(2)从源点v0出发,令ve[0]=0，按拓扑有序求其余各顶点的最早发生时间。

如果得到的拓扑有序序列中的顶点个数小于网中的顶点数，则说明网中存在环，不能求关键路径，算法终止；否则执行第三步。

(3)从汇点vn出发，令vl[n-1]=ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]；(4)根据各顶点的和值，求每条弧的最早开始时间e(s)和最迟开始时间e(s)，若某条弧满足条件e(s)=l(s)，则为关键活动。

从某个源点到其余各顶点的最短路径问题：若从v到vi有弧，则D[i]为弧上的权值，否则D[i]为无穷大。

显然，长度为D[j]=Min{D[i]|vi属于V}的路径就是从v出发的长度最短的一条路径。

二、实现过程以及代码当电脑运行程序的时候，界面会出现一个提示菜单：请输入你要进行操作的图类型的编码：1：有向图，2：有向网，3：无向图，4：无向网，请输入选择。

操作者根据自己的需要可输入相应的编码来进行操作。

如选择3，则将进入关于无向图的操作。

根据课设指导书要求，无向图有四个基本操作：构建邻接矩阵，构建邻接表，对已构建的邻接表进行深度遍历，对已构建的邻接表进行广度遍历，输出所有操作的结果。

第一步操作就是构建，程序会提示你进行下一步操作，然后再根据各操作提示从外部输入顶点和弧的相关信息。

其他三个图的操作基本与本图的操作时一致的。

代码：#include <stdio.h>#include<stdlib.h>#include<limits.h>#define ERROR 0#define OK 1#define INFINITY INT_MAX#define MAX_VERTEX_NUM 21#define STACK_INIT_SIZE 100#define STACKINCREAMENT 10typedef enum{DG,DN,UDG,UDN}GraphKind;typedef struct ArcCell {int adj;//infotype *info;}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct{char vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;GraphKind kind;}MGraph; //邻接矩阵typedef struct ArcNode{int adjvex;int quan;struct ArcNode *nextarc;}ArcNode,*AList;typedef struct VNode {char data;AList firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList vertices;int vexnum,arcnum;GraphKind kind;}ALGraph; //邻接表typedef struct QNode{char data;struct QNode *next;}QNode,*QueuePre;typedef struct{QueuePre front;QueuePre rear;}LinkQueue; //队列typedef struct {int *base;int *top;int stacksize;}SqStack; //栈typedef struct {char adjvex;int lowcost;}closedges[MAX_VERTEX_NUM]; //求最小生成树中的辅助数组int option;int visited[MAX_VERTEX_NUM]; //顶点访问标记数组int indegree[MAX_VERTEX_NUM]; //顶点入度记录数组int ve[MAX_VERTEX_NUM]; //顶点权值记录数组int SetGraphKind(MGraph &G,int option){switch(option){case 1: G.kind=DG;break;case 2: G.kind=DN;break;case 3: G.kind=UDG;break;case 4: G.kind=UDN;break;default: return ERROR;}return OK;} //邻接矩阵类型设置int SetGraphKind(ALGraph &G,int option){switch(option){case 1: G.kind=DG;break;case 2: G.kind=DN;break;case 3: G.kind=UDG;break;case 4: G.kind=UDN;break;default: return ERROR;}return OK;} //邻接表类型设置int LocateVex(MGraph G,char v){int m;for(m=1;m<=G.vexnum;m++){if(G.vexs[m]==v) return m;}return ERROR;} //邻接矩阵顶点定位int LocateVex(ALGraph G,char v){int m;for(m=1;m<=G.vexnum;m++){if(G.vertices[m].data==v) return m;}printf("您输入的顶点不存在");return ERROR;} //邻接表顶点定位int InitQueue(LinkQueue &Q){Q.front=Q.rear=(QueuePre)malloc(sizeof(QNode));if(!Q.front) return ERROR;Q.front->next=NULL;return OK;} //队列创建int EnQueue(LinkQueue &Q,int e){QueuePre p;p=(QueuePre)malloc(sizeof(QNode));if(!p) return OK;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;return OK;} //元素入队列int DeQueue(LinkQueue &Q,int &e){QueuePre p;if(Q.front==Q.rear) return ERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p) Q.rear=Q.front;free(p);return OK;} //元素出队列int QueueEmpty(LinkQueue Q){if(Q.front==Q.rear)return OK;return ERROR;} //判断队列是否为空int InitStack(SqStack &S){S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S.base) return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;} //栈创建int Push(SqStack &S,int e){if(S.top-S.base>=S.stacksize){S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREAMENT)*sizeof(int));if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREAMENT;}*S.top++=e;return OK;} //元素入栈int Pop(SqStack &S,int &e){if(S.top==S.base) return ERROR;e=*--S.top;return OK;} //元素出栈int StackEmpty(SqStack S){if(S.top==S.base) return OK;return ERROR;} //判断栈是否为空int CreatGraph(MGraph &G){int i,j,k,w;char x,y;if(!SetGraphKind(G,option)) {printf("对图类型的设置失败");return ERROR;}printf("邻接矩阵：请输入定点的个数、弧的个数：");scanf("%d %d",&G.vexnum,&G.arcnum);if(G.vexnum>20){printf("您输入的顶点个数超过最大值");return ERROR;}printf("请输入%d个顶点\n",G.vexnum);for(i=1;i<=G.vexnum;++i) {fflush(stdin); scanf("%c",&G.vexs[i]);}if(G.kind==DG||G.kind==UDG){for(i=1;i<=G.vexnum;i++)for(j=1;j<=G.vexnum;j++)G.arcs[i][j].adj=0;if(G.kind==DG){printf("请输入有向图的两个相邻的顶点<x,y>（如果互相邻接则<x,y>也要输入）：\n");for(k=1;k<=G.arcnum;k++){fflush(stdin);scanf("%c%c",&x,&y);i=LocateVex(G,x);j=LocateVex(G,y);G.arcs[i][j].adj=1;}}else{printf("请输入无向图的两个相邻的顶点（x,y）：\n");for(k=1;k<=G.arcnum;k++){fflush(stdin);scanf("%c%c",&x,&y);i=LocateVex(G,x); j=LocateVex(G,y);G.arcs[i][j].adj=1; G.arcs[j][i].adj=G.arcs[i][j].adj;}}}else{for(i=1;i<=G.vexnum;i++)for(j=1;j<=G.vexnum;j++)G.arcs[i][j].adj=INT_MAX;if(G.kind==DN){printf("请输入有向网的两个相邻的顶点<x,y>以及相应的权值w（如果互相邻接则<y,x>也要输入）：\n");for(k=1;k<=G.arcnum;k++){fflush(stdin);scanf("%c%c %d",&x,&y,&w);i=LocateVex(G,x); j=LocateVex(G,y);G.arcs[i][j].adj=w;}}else{printf("请输入无向网的两个相邻的顶点（x,y）以及相应的权值w：\n");for(k=1;k<=G.arcnum;k++){fflush(stdin);scanf("%c%c %d",&x,&y,&w);i=LocateVex(G,x); j=LocateVex(G,y);G.arcs[i][j].adj=w; G.arcs[j][i].adj=G.arcs[i][j].adj;}}}return OK;} //创建邻接矩阵int CreatAList(ALGraph &G){int i,j,m,n,key[MAX_VERTEX_NUM]; char x,y,w;AList p,q;SetGraphKind(G,option);printf("邻接表：请输入顶点的个数和弧的个数：");scanf("%d %d",&G.vexnum ,&G.arcnum);if(G.vexnum>20){printf("您输入的顶点个数超过最大值");return ERROR;}printf("请输入个顶点：\n");for(i=1;i<=G.vexnum;i++){fflush(stdin);scanf("%c",&G.vertices[i].data);G.vertices[i].firstarc=NULL;key[i]=0;}if(G.kind==DG){printf("请输入弧（如AB,其中AB与BA是不同的弧）：\n");for(j=1;j<=G.arcnum;j++){fflush(stdin);scanf("%c%c",&x,&y);m=LocateVex(G,x);n=LocateVex(G,y);p=G.vertices[m].firstarc;q=(AList)malloc(sizeof(ArcNode));if(!q) return ERROR;q->nextarc=NULL;q->adjvex=n;while(key[m]&&p->nextarc){p=p->nextarc;key[m]++;}if(!key[m]){G.vertices[m].firstarc=q;key[m]++;}else p->nextarc=q;}}if(G.kind==UDG){printf("请输入弧（如AB,其中AB与BA是不同的弧）：\n");for(j=1;j<=2*G.arcnum;j++){fflush(stdin);scanf("%c%c",&x,&y);m=LocateVex(G,x);n=LocateVex(G,y);p=G.vertices[m].firstarc;q=(AList)malloc(sizeof(ArcNode));if(!q) return ERROR;q->nextarc=NULL;q->adjvex=n;while(key[m]&&p->nextarc){p=p->nextarc;key[m]++;}if(!key[m]){G.vertices[m].firstarc=q;key[m]++;}else p->nextarc=q;}}if(G.kind==DN){printf("请输入依次输入弧以及这条弧的权值（如AB 8,其中AB与BA是不同的弧）：\n");for(j=1;j<=G.arcnum;j++){fflush(stdin);scanf("%c%c %d",&x,&y,&w);m=LocateVex(G,x);n=LocateVex(G,y);p=G.vertices[m].firstarc;q=(AList)malloc(sizeof(ArcNode));if(!q) return ERROR;q->nextarc=NULL;q->quan=w;q->adjvex=n;while(key[m]&&p->nextarc){p=p->nextarc;key[m]++;}if(!key[m]){G.vertices[m].firstarc=q;key[m]++;}else p->nextarc=q ;}}if(G.kind==UDN){printf("请输入依次输入弧以及这条弧的权值（如AB 8,其中AB与BA是不同的弧）：\n");for(j=1;j<=2*G.arcnum;j++){fflush(stdin);scanf("%c%c %d",&x,&y,&w);m=LocateVex(G,x);n=LocateVex(G,y);p=G.vertices[m].firstarc;q=(AList)malloc(sizeof(ArcNode));if(!q) return ERROR;q->nextarc=NULL;q->quan=w;q->adjvex=n;while(key[m]&&p->nextarc){p=p->nextarc;key[m]++;}if(!key[m]){G.vertices[m].firstarc=q;key[m]++;}else p->nextarc=q ;}}return OK;} //创建邻接表int FirstAdjVex(ALGraph G,int v){if(G.vertices[v].firstarc)return G.vertices[v].firstarc->adjvex;return 0;}int NextAdjVex(ALGraph G,int v,int w){AList s;s=G.vertices[v].firstarc;while(s->adjvex!=w)s=s->nextarc;if(s->nextarc)return s->nextarc->adjvex;return 0;}void DFS(ALGraph G,int v){int w;visited[v]=1; printf("%c ",G.vertices[v]);for(w=FirstAdjVex(G,v);w>=1;w=NextAdjVex(G,v,w)){ if(!visited[w]) DFS(G,w);}}void DFSTraverse(ALGraph G){int v;visited[0]=1;for(v=1;v<=G.vexnum;v++) visited[v]=0;for(v=1;v<=G.vexnum;v++)if(!visited[v]) DFS(G,v);} //图的深度遍历void BFSTraverse(ALGraph G){int v,w,u;LinkQueue Q;for(v=1;v<=G.vexnum;v++) visited[v]=0;visited[0]=1;InitQueue(Q);for(v=1;v<=G.vexnum;v++)if(!visited[v]){visited[v]=1;printf("%c ",G.vertices[v]);EnQueue(Q,v);while(!QueueEmpty(Q)){DeQueue(Q,u);for(w=FirstAdjVex(G,u);w>=1;w=NextAdjVex(G,u,w)){if(!visited[w]){visited[w]=1;printf("%c ",G.vertices[w]);EnQueue(Q,w);}else break;}}}} //图的广度遍历void FindInDegree(ALGraph G,int in[]){int i,j,k;AList p;for(k=1;k<=G.vexnum;k++) in[k]=0;for(i=1;i<=G.vexnum;i++){p=G.vertices[i].firstarc;while(p){j=p->adjvex;in[j]++;p=p->nextarc;}}} //计算各顶点入度int TopologicalSort(ALGraph G){int i,k,count;AList p;SqStack S;FindInDegree(G,indegree);InitStack(S);for(i=1;i<=G.vexnum;i++)if(!indegree[i]) Push(S,i);count=0;if(StackEmpty(S)) printf("此有向图不符合条件！");while(!StackEmpty(S)){Pop(S,i);printf("%c ",G.vertices[i].data);++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;if(!(--indegree[k])) Push(S,k);}}if(count<=G.vexnum) return ERROR;else return OK;} //拓扑排序int Minimum(MGraph G,closedges m){int i,j,min=INFINITY;for(i=1;i<=G.vexnum;i++){if(m[i].lowcost){if(m[i].lowcost<min){min=m[i].lowcost;j=i;}}}return j;}void MinSpanTree_PRIM(MGraph G,char u){int i,j,k;closedges closedge;k=LocateVex(G,u);for(j=1;j<=G.vexnum;j++)if(j!=k) {closedge[j].adjvex=u;closedge[j].lowcost=G.arcs[k][j].adj;}closedge[k].lowcost=0;for(i=2;i<=G.vexnum;i++){k=Minimum(G,closedge);printf("%c%c ",closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost=0;for(j=1;j<=G.vexnum;j++)if(G.arcs[k][j].adj<closedge[j].lowcost){closedge[j].adjvex=G.vexs[k];closedge[j].lowcost=G.arcs[k][j].adj;}}} //求最小生成树int TopologicalOrder(ALGraph G,SqStack &T){int i,j,k,count; SqStack S; AList p;FindInDegree(G,indegree);InitStack(S);for(i=1;i<=G.vexnum;i++)if(!indegree[i]) Push(S,i);InitStack(T);count=1;for(i=1;i<=G.vexnum;i++) ve[i]=0;while(!StackEmpty(S)){Pop(S,j);Push(T,j);++count;for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;if(--indegree[k]==0) Push(S,k);if(ve[j]+p->quan>ve[k]) ve[k]=ve[j]+p->quan;}}if(count<=G.vexnum) return ERROR;else return OK;}int CriticalPath(ALGraph G){int i,j,k,ee,el,dut,v1[MAX_VERTEX_NUM]; SqStack T; AList p; char tag;if(!TopologicalOrder(G,T)) return ERROR;for(i=1;i<=G.vexnum;i++){v1[i]=ve[G.vexnum];}while(!StackEmpty(T))for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=p->quan;if(v1[k]-dut<v1[j]) v1[j]=v1[k]-dut;}for(j=1;j<=G.vexnum;j++)for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=p->quan;ee=ve[j];el=v1[k]-dut;tag=(ee==el)?'*':' ';printf("%d %d %d %d %d %c\n",j,k,dut,ee,el,tag);}return OK;} //求关键路径void DG_(MGraph G1,ALGraph G2){int i,j,k,m,key;AList s;printf("**************************\n");printf("你选择了对有向图的基本操作及应用：\n1创建邻接矩阵\n2创建邻接表\n3拓扑结构\n4退出\n");printf("**************************\n");for(k=0;;){key=0;printf("请选择：");scanf("%d",&m);switch(m){case 1: CreatGraph(G1);printf("有向图的邻接矩阵：\n");for(i=1;i<=G1.vexnum;i++){for(j=1;j<=G1.vexnum;j++){printf(" %d",G1.arcs[i][j].adj);}printf("\n");}break;case 2: CreatAList(G2);printf("有向图的邻接表：\n");for(i=1;i<=G2.vexnum;i++){printf("%c:",G2.vertices[i]);s=G2.vertices[i].firstarc;while(s){j=s->adjvex;fflush(stdin);printf("<%c ",G2.vertices[i]);printf("%c> ",G2.vertices[j]);s=s->nextarc;}printf("\n");}break;case 3:printf("有向图的拓扑排序：\n");TopologicalSort(G2);break;case 4:key=1;break;}printf("\n");if(key) break;}printf("\n\n");} //DGvoid UDG_(MGraph G1,ALGraph G2){int i,j,k,m,key;AList s;printf("**************************\n");printf("你选择了对有向网的基本操作及应用：\n1创建邻接矩阵\n2创建邻接表\n3关键路径\n4退出\n");printf("**************************\n");for(k=0;;){key=0;printf("请选择：");scanf("%d",&m);switch(m){case 1: CreatGraph(G1); printf("有向网的邻接矩阵：\n");for(i=1;i<=G1.vexnum;i++){for(j=1;j<=G1.vexnum;j++){if(G1.arcs[i][j].adj==INT_MAX)printf(" #");else printf(" %d",G1.arcs[i][j].adj);}printf("\n");}break;case 2: CreatAList(G2); printf("有向网的邻接表：\n");for(i=1;i<=G2.vexnum;i++){printf("%c:",G2.vertices[i]);s=G2.vertices[i].firstarc;while(s){j=s->adjvex;fflush(stdin);printf("<%c ",G2.vertices[i]);printf("%c> ",G2.vertices[j]);printf(" %d ",s->quan);s=s->nextarc;}printf("\n");}break;case 3: printf("有向网关键路径：\n");CriticalPath(G2);break;case 4: key=1;break;}printf("\n");if(key) break;}printf("\n\n");} //DNvoid DN_(MGraph G1,ALGraph G2){int i,j,k,m,key;AList s;printf("**************************\n");printf("你选择了对无向图的基本操作及应用：\n1创建邻接矩阵\n2创建邻接表\n3深度遍历\n4广度遍历\n5退出\n");printf("**************************\n");for(k=0;;){key=0;printf("请选择：");scanf("%d",&m);switch(m){case 1:CreatGraph(G1); printf("无向图的邻接矩阵：\n");for(i=1;i<=G1.vexnum;i++){for(j=1;j<=G1.vexnum;j++){printf(" %d",G1.arcs[i][j].adj);}printf("\n");}break;case 2: CreatAList(G2); printf("无向图的邻接表：\n");for(i=1;i<=G2.vexnum;i++){printf("%c:",G2.vertices[i]);s=G2.vertices[i].firstarc;while(s){j=s->adjvex;fflush(stdin);printf("(%c ",G2.vertices[i]);printf("%c) ",G2.vertices[j]);s=s->nextarc;}printf("\n");}break;case 3: printf("无向图的深度优先遍历：\n");DFSTraverse(G2);printf("\n");break;case 4: printf("无向图的广度优先遍历：\n");BFSTraverse(G2);break;case 5: key=1;break;}printf("\n");if(key) break;}printf("\n\n");} //UDGvoid UDN_(MGraph G1,ALGraph G2){int i,j,m,k,key;AList s;char u;printf("**********************************\n");printf("你选择了对无向网的基本操作及应用：\n1创建邻接矩阵\n2创建邻接表\n3最小生成树\n4退出\n");printf("**********************************\n");for(k=0;;){key=0;printf("请选择：");scanf("%d",&m);switch(m){case 1: CreatGraph(G1); printf("无向网的邻接矩阵：\n");for(i=1;i<=G1.vexnum;i++){for(j=1;j<=G1.vexnum;j++){if(G1.arcs[i][j].adj==INT_MAX)printf(" #");else printf(" %d",G1.arcs[i][j].adj);}printf("\n");}break;case 2: CreatAList(G2); printf("无向网的邻接表：\n");for(i=1;i<=G2.vexnum;i++){printf("%c:",G2.vertices[i]);s=G2.vertices[i].firstarc;while(s){j=s->adjvex;fflush(stdin);printf("(%c ",G2.vertices[i]);printf("%c)",G2.vertices[j]);printf(" %d ",s->quan);s=s->nextarc;}printf("\n");}break;case 3: printf("请输入第一个顶点：");fflush(stdin);scanf("%c",&u);printf("无向网的最小生成树：\n");MinSpanTree_PRIM(G1,u);break;case 4: key=1;break;}printf("\n");if(key) break;}printf("\n\n");} //UDNvoid main(){MGraph G1;ALGraph G2;int i,n;for(i=0;;){n=0;printf("\n");printf("**************图的基本操作及应用***************\n1：有向图的基本操作及应用\n2：无向图的基本操作及应用\n3：有向网的基本操作及应用\n4：无向网的基本操作及应用\n5: 退出\n");printf("********************************\n");printf("请选择：");scanf("%d",&option);printf("\n\n");switch(option){case 1: DG_(G1,G2);break;case 2: DN_(G1,G2);break;case 3: UDG_(G1,G2);break;case 4: UDN_(G1,G2);break;case 5: n=1;break;default: printf("你输入的编码有误！"); break;}if(n) break;printf("\n\n");}}三、测试菜单有向图内部菜单有向图邻接矩阵有向图邻接表以及拓扑结构无向网的基本操作无向网邻接矩阵及最小生成树四、结论和分析整个程序最关键和最基本的是对图四种类型的邻接矩阵和邻接表的创建。