《《算法与数据结构》 项目实训7.docx》由会员分享，可在线阅读，更多相关《《算法与数据结构》 项目实训7.docx（14页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图的应用一、主界面#include #include #include #include graph.h#define INF 32767 /INF 表示8#define MaxSize 100/*将邻接矩阵g转换成邻接表G*/void MatToList(MGraph g,ALGraph *&G)(int i,j,n=g.n;/n 为顶点数ArcNode *p;G=(ALGraph *)malloc(sizeof(ALGraph);for (i=0;iadjlisti.firstarc=N U LL;for (i=0;i=O;j-)if(g.edgesij!=0)邻接矩阵的当前元素不为0(p
2、=(ArcNode *)malloc(sizeof(ArcNode); 创建一个结点*pp-adjvex=j;p-info=g.edgesij;p-nextarc=G-adjlisti.firstarc; 将*p 链到链表后G-adjlisti.firstarc=p;)G-n=n;G-e=g.e;/*将邻接表G转换成邻接矩阵g*/int w;边的权值 Edge;void InsertSort(Edge E,int n) 对E0.n-l按递增有序进行直接插入排序 (int i,j;Edge temp;for (i=l;i=0 & temp.wEj.w)EU+I=EU；)Ej+I=temp;)vo
3、id Kruskal(MGraph g)(int i,j,ul,vl,snl,sn2,k;int vsetMAXV;Edge EMaxSize;k=0;for (i=0;ig.n;i+)for (j=O;jg,n;j+)/将关键字大于Ei.w的记录后移在j+1处插入Ei/将关键字大于Ei.w的记录后移在j+1处插入Ei/将关键字大于Ei.w的记录后移在j+1处插入Ei/存放所有边E数组的下标从0开始计由g产生的边集Eif (g.edgesij!=O & g.edgesfij!=INF)Ek .u=i;Ek .v=j ;Ek. w=g.edgesi j;InsertSort(E,g,e);Ins
4、ertSort(E,g,e);/采用直接插入排序对E数组按权值递增排序k+;for (i=0;ig,n;i+)vseti=i;k=l;j=0;while (kg.n)(ul=Ej.u;vl=Ej.v;for (i=0;ig,n;i+)vseti=i;k=l;j=0;while (kg.n)(ul=Ej.u;vl=Ej.v;for (i=0;ig,n;i+)vseti=i;k=l;j=0;while (kg.n)(ul=Ej.u;vl=Ej.v;初始化辅助数组/k表示当前构造生成树的第儿条边,初值为1E中边的下标,初值为0生成的边数小于n时循环取一条边的头尾顶点snl=vsetful;sn2=v
5、setvl;/分别得到两个顶点所属的集合编号if (snl!=sn2)if (snl!=sn2)if (snl!=sn2)/两顶点属于不同的集合,该边是最小生成树的一条边printf(H (%d,%d):%dnH,u l,v l,Ej.w);k+;生成边数增1for (i=0;ixi11 r 十,；、,、.、,、,：、.,、.卜；、.、.、.、,.、.、.、；、4、.、,；、,；、；、；、.、.、.；、.、,、1、.；、；、.、.、；、,；、,；、；、 * printf(nttt 最小生成树n“);printf(Hnn);printf（tttl.利用Prim算法构造最小生成树n）;printf
6、(ttt2.利用Kruskal算法构造最小生成树n);printf(tttO.退出 n”)；printf(Ht 请选择(02):n)scanf(%d,&m);switch(m)Prim(g,O);break;Kruskal(g);break;case 0:printf(M(*A_A*)再见！ nM);break;default:printf（您输入的有误!n）;四、最短路径/Dijkstra最短路径*/前向递归查找路径上的顶点找到了起点则返回找顶点k的前一个顶点输出顶点kvoid Ppath(int path,int i,int v)(int k;k=pathi;if (k=v) return
7、;Ppath(path,k,v);printf(H%d,n,k);void Dispath(int dist,int path,int s,int n,int v)int i;for (i=0;in;i+)printfC1从1到%1的最短路径长度为:dt路径为：v,i,disti);输出路径上的起点Ppath(path,i,v);输出路径上的中间点输出路径上的终点elseprintf(从%d 到1 不存在路径n”,v,i);void Dijkstra(MGraph g,int v) int distMAXV,pathMAXV;int sMAXV;for (i=0;ig.n;i+)disti=g
8、.edgesvi;disti=g.edgesvi;disti=g.edgesvi;距离初始化si=0;si=0;si=0;s口置空if(g.edgesviINF)if(g.edgesviINF)if(g.edgesviINF)/路径初始化pathi=v;elsepathi=l;sv=l;pathv=O;sv=l;pathv=O;源点编号v放入s中fbr (i=0;ig.n;i+)循环直到所有顶点的最短路径都求出mindis=INF;/mindis置最小长度初值for (j=O;jg,n;j+)选取不在s中且具有最小距离的顶点if (sj=O & distjmindis)u二j；mindis=d
9、istj;su=l;顶点u加入s中for (j=O;jg.n;j+)/修改不在s中的顶点的距离if (sj=O)if (g.edgesfujINF & distu+g.edgesfujdistj)distj=distu+g.edgesuj;pathj=u;)Dispath(dist,path,s,g.n,v);)五、拓扑排序/*拓扑排序*/void TopSort(ALGraph *G)(int ij;int StMAXV,top=-l;ArcNode *p;for (i=0;in;i+)G-adjlisti.count=0;for (i=0;in;i+)输出最短路径栈St的指针为t叩入度置初
10、值0求所有顶点的入度p=G-adj listi|.firstarc;while (p!=NULL)(G-adjlistp-adjvex.count+;p=p-nextarc;for (i=0;in;i+)if (G-adjlisti.count=0) (top+;SttopJ=i;)while (top-1)(i=Sttop;top-;printf(%d ”,i);p=G-adj listi .firstarc;while (p!=NULL) (j=p-adjvex;G-adjlistj.count-;if (G-adjlistj.count=0) (top+;Sttop=j;)入度为0的顶点
11、进栈栈不为空时循环出栈输出顶点找第一个相邻顶点入度为。的相邻顶点进栈p=p-nextarc;/找下一个相邻顶点void ListToMat(ALGraph *G,MGraph &g) int i,n=G-n;Arc Node *p;for (i=0;ivn;i+)(p=G-adjlisti.firstarc;while (p!=NULL)(g.edgesip-adjvexj=p-infd; p=p-nextarc;)g.n=n;g.e=G-e;)/*输出邻接矩阵g*/void DispMat(MGraph g)(int i,j;for (i=0;ig.n;i+)(for (j=O;jg,n;j
12、+)if(g.edgesij=INF)printf(%3s,nH);elseprintfC，%3d,g.edgesij)； printf(n);/*输出邻接表G*/int i;Arc Node *p;for (i=0;in;i+)(p=G-adjlisti.firstarc;printf(%3d: ,i);while (p!=NULL)(printf(n%3dn,p-adjvex);p=p-nextarc;)printf(n);/*主函数*/void main()(int i,j,m,v;MGraph g,gl;ALGraph *G;int AMAXV 6=0,1,0,0,0,0),0,0,1
13、,0,0,0),0,0,0,1,0,0),0,0,0,0,0。,(0,1,0,0,0,11，0,0,0,1,0,0)；g.n=6;g.e=10;for (i=0;ig.n;i+)for (j=O;jg,n;j+)g.edgesij=Afifj;printf(Hnn);while(m!=O) system(”cls”); 主菜单* tr/ 11 -一! !* * ,!*!*! ! ，*!*1* *11 丁丁, T-j* *j j *7* * *j* *j* *j* *j* *j *7* *7* *7* *j* *j* *j* *j j* *j* *7* * *7* *T* *T* *T* *j*
14、 *j* *7* *T* *T* *j* *j* *7* *j* *7* *7* * *7*j *7* *j* *7* *7* *7* *7*1 printf(ttt 图的应用n);printf(Hn);4。, 11 a kJ* V，*1*1* *1* *1 *1 *1* *1* *1* kJ* *1* 7, kJ* kJ* kJ* kJ* .J*1 *1* *1* *A* kJ*1 *1 *t* kJ* kJ* kJ*1* kJ* kJ*! r 才,、t 、；、,.、.、； ；、 j、 ：、； ； .、.、，j、 、 j、； ；一j、卜；、：、卜；、1 printf（”tttl.将图G转化为
15、邻接表n”）;printf（”ttt3.构造图G的最小生成树n） printf(ttt4.S G 的最短路径n”);printf(ttt5.S G 拓扑排序n)printf(Ht 请选择(0-5):n);scanf(d”,&m);switch(m)(case 1:MatToList(g,G);printf(H有向图G的邻接矩阵:n)；DispMat(g);G=(ALGraph *)malloc(sizeof(ALGraph);printf(H图G的邻接矩阵转换成邻接表:n”);MatToList(g,G);DispAdj(G);break;case 2: system(ncls);Traver
16、singG(G,g); 遍历图break;case 3: system(clsn);MCSTree(G,g);break;case 4: Dijkstra(g,O);break;case 5: G=(ALGraph *)malloc(sizeof(ALGraph);MatToList(g,G);printf(n有向图G的邻接表:n”)；DispAdj(G);printf(nnn);printf(拓扑序列TopSort(G);printf(nnn);break;case 0:printf(n(*A八*)再见！ nn);break;default:printf(您输入的有误!n“);)system
17、(pause);)printf(HnH);二、图的遍历广度优先遍历定义循环队列并初始化定义存放结点的访问标志的数组/访问标志数组初始化输出被访问顶点的编号/置已访问标记v进队若队列不空时循环出队并赋给w找与顶点W邻接的第一个顶点/若当前邻接顶点未被访问访问相邻顶点置该顶点已被访问的标志该顶点进队/找下一个邻接顶点/深度优先遍历void BFS(ALGraph *G,int v)(ArcNode *p;int queueMAXV ,front=0,rear=0;int visitedMAXV;int w,i;for (i=0;in;i+) visitedi=O;printf(H%2dn,v);v
18、isited v=l;rear=(rear+l )%MAXV;queue rear=v;while (front! =rear) front=(front+ 1)%MAXV;w=queuefront;p=G-adjlistw.firstarc;while (p!=NULL) if (visitedp-adjvex=O)prin tf( %2dn ,p-adj vex);visitedp-adjvex=l;rear=(rear+1 )%MAXV;queuefrear =p-adj vex;)p=p-nextarc;)printf(HnH);int visitedlMAXV;void DFS(AL
19、Graph *G,int v)ArcNode *p;visitedv=l;ArcNode *p;visitedv=l;visitedv=l;visitedv=l;printf(H%d n,v);p=G-adjlistv.firstarc;while (p!=NULL)(if (visitedp-adjvex =0)DFS(G,p-adjvex);p=p-nextarc;/置已访问标记 输出被访问顶点的编号p指向顶点v的第一条弧的弧头结点若p-adjvex顶点未访问，递归访问它/p指向顶点v的下一条弧的弧头结点/*遍历菜单*/void TraversingG(ALGr叩h *G, MGraph
20、g)(int printf(Hnn);. f f *X* QQ、 w- * t / ，*1* rj*rj%rj%rjwrjw rjw 1 printf(Httt 图的遍历n“);printf(HnH);printf( t * * * * *n ) printf(”tttl.深度优先搜索n);printf(ttt2.广度优先搜索 n“);printf(tttO.退出 n)printf(飞请选择(0-2):n”)；scanf(d”,&m);switch(m)case 1: DispMat(g);G=(ALGraph *)malloc(sizeof(ALGraph);MatToList(g,G);p
21、rintf(H 邻接表:n)DispAdj(G);for (i=O;iMAXV;i+)visitedi=O;printff深度优先序列:)；DFS(G,2);printf(HnH);break;case 2: /BFS( G, v);DispMat(g);G=(ALGraph *)malloc(sizeof(ALGraph);MatToList(g,G);printf(邻接表:n)DispAdj(G);printf(广度优先序列:)；BFS(G,2);printf(nn);break;case 0:printf(H(*A_A*)再见! n);break;default:printf(您输入的有
22、误!n);)三、最小生成树/*Prim算法构造最小生成树*/void Prim(MGraph g,int v)int lowcostMAXV;int lowcostMAXV;int lowcostMAXV;顶点i是否在U中int min;int closestMAXV,i,j,k;for (i=0;ig.n;i+)给 lowcost口和 closest置初值(lowcosti=g.cdgesvi;closesti=v;)for (i=l;ig.n;i+)找出 nl 个顶点(min=INF;for (j=O;jg.n;j+)在(V-U)中找出离U最近的顶点kif (lowcostj!=0 & lowcostjmin)(min=lowcostj;k=j;/k记录最近顶点的编号)printf(边(1,%(1)权为:dn”,closestk,k,min);lowcostfk=0;标记k已经加入Ufor (j=O;jg.n;j+)修改数组 lowcost 和 closestif (g.edgeskj!=O & g.edgeskjlowcostj)(lowcostj=g.edgeskj;closestj=k;)/*Kruskal算法构造最小生成树*/typedef struct(int v;int v;int v;/边的终止顶点