圖的各種操作C語言實驗報告.docx

圖論李一鵬 PB12001076 數(shù)學系 第五組1. 實驗題目：最小生成樹和最短路徑2. 實驗?zāi)康模菏煜D的鄰接表儲存，深優(yōu)廣優(yōu)，最小生成樹和最短路徑求解思想。3. 實驗內(nèi)容：令狐沖要到松山少林寺救任盈盈，但左冷禪在山上設(shè)下n個陣營。兩個陣營之間可能有道路相通，也可能沒有。而每兩個道路相通陣營i和j之間設(shè)有Wij個小兵來埋伏令狐沖。藍鳳凰被劇透了這一信息并順利拿到了標有陣營、道路和小兵數(shù)目的地圖，然后告訴了令狐沖。令狐沖救人心切，希望藍鳳凰能幫他找出一條小兵數(shù)目最少的路通往少林寺。到了少林寺后，令狐沖記恨于左冷禪，就想搗毀所有陣營，卻不想浪費時間在虐沒經(jīng)驗值的1級小兵上。此時左冷禪的小兵都重新按原來的陣勢埋伏在原來位置。請大家?guī)蛶兔?，設(shè)計一個滿足令狐沖兩個計劃的程序吧。4. 算法分析：最短路徑有Dijkstra和Floyd兩種算法，由于本實驗并不要求求出任意兩個結(jié)點的最短路徑，只要求從一個結(jié)點到另外結(jié)點的最短路徑，故采用Dijkstra算法：每次選擇一個未訪問的離起點最近的結(jié)點，訪問該結(jié)點并用其更新到其他結(jié)點的路徑。動態(tài)方程：si=min(si,sk+dki);用adjvex來記錄該結(jié)點的到起點的最短路徑中經(jīng)過的第一個結(jié)點。最小生成樹有Prim和Kruskal兩種算法，由于本實驗采用鄰接表儲存故使用Prim算法：每次選擇一個離已訪問點集最近的結(jié)點，訪問并加入已訪問點集。用adjvex來記錄父結(jié)點。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()/創(chuàng)建鄰接表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+;/頭結(jié)點不動的頭插法p=new1;p-v=c;p-weight=d;p-next=ab-next;ab-next=p;ab-weight+;/頭結(jié)點的weight用于記錄結(jié)點度數(shù)scanf(%d,&c);void deep(int n)/深度優(yōu)先搜索node *p;if(visitedn)return;/visited用于記錄當前結(jié)點是否已被訪問printf(%dt,n);visitedn=1;for(p=an-next;p;p=p-next)deep(p-v);void breadth()/廣度優(yōu)先搜索int open1100;/隊列char opened100;/用于記錄當前結(jié)點是否曾入隊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)/用找到的結(jié)點k更新n到其他未被訪問的結(jié)點的路程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+)/找出離已訪問結(jié)點集合最近的結(jié)點kif(lcj&lcj!=-1)if(lcjnext;p;p=p-next)/把k加入已訪問結(jié)點集并更新lcif(lcp-v)if(lcp-v=-1)adp-v=k;lcp-v=p-weight;/ad記錄父結(jié)點，lc記錄其余結(jié)點的到已訪問結(jié)點集的最短路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