图的各种操作C语言实验报告.docx

图论李一鹏 PB12001076 数学系 第五组1. 实验题目：最小生成树和最短路径2. 实验目的：熟悉图的邻接表储存，深优广优，最小生成树和最短路径求解思想。3. 实验内容：令狐冲要到松山少林寺救任盈盈，但左冷禅在山上设下n个阵营。两个阵营之间可能有道路相通，也可能没有。而每两个道路相通阵营i和j之间设有Wij个小兵来埋伏令狐冲。蓝凤凰被剧透了这一信息并顺利拿到了标有阵营、道路和小兵数目的地图，然后告诉了令狐冲。令狐冲救人心切，希望蓝凤凰能帮他找出一条小兵数目最少的路通往少林寺。到了少林寺后，令狐冲记恨于左冷禅，就想捣毁所有阵营，却不想浪费时间在虐没经验值的1级小兵上。此时左冷禅的小兵都重新按原来的阵势埋伏在原来位置。请大家帮帮忙，设计一个满足令狐冲两个计划的程序吧。4. 算法分析：最短路径有Dijkstra和Floyd两种算法，由于本实验并不要求求出任意两个结点的最短路径，只要求从一个结点到另外结点的最短路径，故采用Dijkstra算法：每次选择一个未访问的离起点最近的结点，访问该结点并用其更新到其他结点的路径。动态方程：si=min(si,sk+dki);用adjvex来记录该结点的到起点的最短路径中经过的第一个结点。最小生成树有Prim和Kruskal两种算法，由于本实验采用邻接表储存故使用Prim算法：每次选择一个离已访问点集最近的结点，访问并加入已访问点集。用adjvex来记录父结点。5. 程序清单：#include#include#define new1 (node*)malloc(sizeof(node)typedef struct graphnodeint v,weight;struct graphnode *next;node;node *a100;int m;char visited100;void create()/创建邻接表int b,c,d,i;node *p;printf(Input your number of node:n);scanf(%d,&m);for(i=0;iweight=0;ai-next=0;printf(Input your edges and end with -1:nTwo nodes and the weightn);scanf(%d,&c);while(c!=-1)scanf(%d%d,&b,&d);p=new1;p-v=b;p-weight=d;p-next=ac-next;ac-next=p;ac-weight+;/头结点不动的头插法p=new1;p-v=c;p-weight=d;p-next=ab-next;ab-next=p;ab-weight+;/头结点的weight用于记录结点度数scanf(%d,&c);void deep(int n)/深度优先搜索node *p;if(visitedn)return;/visited用于记录当前结点是否已被访问printf(%dt,n);visitedn=1;for(p=an-next;p;p=p-next)deep(p-v);void breadth()/广度优先搜索int open1100;/队列char opened100;/用于记录当前结点是否曾入队int i,front,rear,n;node *p;front=rear=0;for(i=0;im;i+)openedi=0;for(i=0;im;i+)/适用于连通或非连通图if(openedi) continue;open1+rear=i;/入队openedi=1;while(frontnext;p;p=p-next)if(!openedp-v)open1+rear=p-v;/入队openedp-v=1;shortload(int s,int load,int n)/用Dijkstra算法求最短路径int i,j,k,min,finished;node *p;for(i=0;inext;p;p=p-next)sp-v=p-weight;loadp-v=n;visitedn=1;for(i=1;im;i+)min=32767;finished=1;for(j=0;jm;j+)if(!visitedj&sj!=-1) if(sjnext;p;p=p-next)/用找到的结点k更新n到其他未被访问的结点的路程if(!visitedp-v)if(sp-v=-1)sp-v=sk+p-weight;loadp-v=k;else if(sp-vsk+p-weight)sp-v=sk+p-weight;loadp-v=k;void mintree()int i,j,k,min,ad100,sum,lc100;node *p;for(i=0;inext;p;p=p-next)adp-v=0;lcp-v=p-weight;for(i=1;im;i+)min=32767;for(j=1;jm;j+)/找出离已访问结点集合最近的结点kif(lcj&lcj!=-1)if(lcjnext;p;p=p-next)/把k加入已访问结点集并更新lcif(lcp-v)if(lcp-v=-1)adp-v=k;lcp-v=p-weight;/ad记录父结点，lc记录其余结点的到已访问结点集的最短路else if(lcp-vp-weight)lcp-v=p-weight;adp-v=k;printf(%dn,sum);printf(Here is the tree:n);/输出树for(i=0;im;i+)printf(%dtsons:t,i);for(j=1;jm;j+)if(adj=i)printf(%dt,j);putchar(10);main()int s100,load100;int i,v1,v2,k,sum2;create();for(i=0;im;i+)visitedi=0;printf(Here is the depth first search:n);for(i=0;im;i+)if(!visitedi)deep(i);/适用于连通或非连通图putchar(10);printf(Here is the breadth first search:n);breadth();putchar(10);printf(Now we can find the short load between two nodes.n);printf(Input the two nodes you want to find.n);printf(We will begin in the first node and end in the second node.n); scanf(%d%d,&v1,&v2);shortload(s,load,v1);k=v2;sum2=0;printf(Here is the lowest cost load of every node to v1:n);for(i=0;im;i+)printf(%dt%dn,i,si);printf(Here is the load:n);while(k!=v1)printf(%dt,k);k=loadk;printf(%dn,v1);printf(Here is the lowest cost:n);printf(%dn,sv2);printf(Here is the lowest sum weight of th