實(shí)驗(yàn)五 圖(to student)

1、實(shí)驗(yàn)五 圖一、實(shí)驗(yàn)?zāi)康?. 掌握圖的基本存儲(chǔ)方法； 2. 掌握有關(guān)圖的操作算法并用高級(jí)語言實(shí)現(xiàn)； 3. 熟練掌握圖的兩種搜索路徑的遍歷方法。二、實(shí)驗(yàn)內(nèi)容假設(shè)以一個(gè)帶權(quán)有向圖表示某一區(qū)域的公交線路網(wǎng)，圖中頂點(diǎn)代表一些區(qū)域中的重要場所，弧代表已有的公交線路，弧上的權(quán)表示該線路上的票價(jià)（或搭乘所需時(shí)間），試設(shè)計(jì)一個(gè)交通指南系統(tǒng)，指導(dǎo)前來咨詢者以最低的票價(jià)或最少的時(shí)間從區(qū)域中的某一場所到達(dá)另一場所。三、實(shí)驗(yàn)步驟1. 定義結(jié)點(diǎn)結(jié)構(gòu)，定義圖結(jié)構(gòu)。2.存儲(chǔ)圖信息；3. 定義求任意兩點(diǎn)最短路徑函數(shù)；4. 寫出主函數(shù)。四、實(shí)現(xiàn)提示typedef struct node int no; float wgt; st

2、ruct node *next; edgenode; typedef struct char vtx; edgenode *link; vexnode; typedef vexnode Graphn; void Floyd(Graph G, float Ann, int pnn) int i, j, k; for (i=0; in; i+) for(j=0;jn;j+) Aij=Gij; Pij=-1; for (k=0; kn; k+) for (i=0; in; i+) for (j=0; jn; j+) if(Aik +AkjAij) Pij=k; Aij=Aik+Akj; 五、思考與提

3、高（直接將答案寫在小題后面）1. 判斷兩點(diǎn)是否可達(dá)。2.如何對程序進(jìn)行修改，找一條人最少的公交線路？3.練習(xí)圖的拓?fù)渑判蛄?、調(diào)試以下參考程序代碼，并將運(yùn)行效果截圖1.圖的建立與遍歷#include #include #include #include #define MAX_VERTEX_NUM 20 /圖的最大頂點(diǎn)數(shù)#define MAXQSIZE 30 /隊(duì)列的最大容量 enum BOOL False,True;typedef struct ArcNodeint adjvex; /該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc; /指向下一條弧的指針ArcNode;

4、 /弧結(jié)點(diǎn)typedef structArcNode* AdjListMAX_VERTEX_NUM; /指向第一條依附該頂點(diǎn)的弧的指針 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)和弧數(shù) int GraphKind; /圖的種類，0-無向圖，1-有向圖Graph; typedef struct /隊(duì)列結(jié)構(gòu)int elemMAXQSIZE; /數(shù)據(jù)域 int front; /隊(duì)頭指針 int rear; /隊(duì)尾指針SqQueue; BOOL visitedMAX_VERTEX_NUM; /全局變量訪問標(biāo)志數(shù)組void CreateGraph(Graph &); /生成圖的鄰接表void

5、DFSTraverse(Graph); /深度優(yōu)先搜索遍歷圖void DFS(Graph,int); void BFSTraverse(Graph); /廣度優(yōu)先搜索遍歷圖void Initial(SqQueue &); /初始化一個(gè)隊(duì)列BOOL QueueEmpty(SqQueue); /判斷隊(duì)列是否空BOOL EnQueue(SqQueue &,int); /將一個(gè)元素入隊(duì)列BOOL DeQueue(SqQueue &,int &); /將一個(gè)元素出隊(duì)列int FirstAdjVex(Graph,int); /求圖中某一頂點(diǎn)的第一個(gè)鄰接頂點(diǎn)int NextAdjVex(Graph,int,

6、int); /求某一頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)void main()Graph G; /采用鄰接表結(jié)構(gòu)的圖 char j=y;printf(本程序?qū)⒀菔旧梢粋€(gè)圖，并對它進(jìn)行遍歷.n); printf(首先輸入要生成的圖的種類.n); printf(0-無向圖, 1-有向圖n); printf(之后輸入圖的頂點(diǎn)數(shù)和弧數(shù)。n格式：頂點(diǎn)數(shù)，弧數(shù)；例如:4,3n); printf(接著輸入各邊(弧尾，弧頭).n例如:n1,2n1,3n2,4n); printf(程序會(huì)生成一個(gè)圖，并對它進(jìn)行深度和廣度遍歷.n); printf(深度遍歷:1-2-4-3n廣度遍歷:1-2-3-4n);while(j!=N&j

7、!=n) printf(請輸入要生成的圖的種類(0/1):); scanf(%d,&G.GraphKind); /輸入圖的種類 printf(請輸入頂點(diǎn)數(shù)和弧數(shù)：); scanf(%d,%d,&G.vexnum,&G.arcnum); /輸入圖的頂點(diǎn)數(shù)和弧數(shù) CreateGraph(G); /生成鄰接表結(jié)構(gòu)的圖 DFSTraverse(G); /深度優(yōu)先搜索遍歷圖 BFSTraverse(G); /廣度優(yōu)先搜索遍歷圖 printf(圖遍歷完畢，繼續(xù)進(jìn)行嗎?(Y/N); scanf( %c,&j); void CreateGraph(Graph &G)/構(gòu)造鄰接表結(jié)構(gòu)的圖G int i; int

8、 start,end; ArcNode *s; for(i=1;i=G.vexnum;i+) G.AdjListi=NULL; /初始化指針數(shù)組 for(i=1;inextarc=G.AdjListstart; /插入到鄰接表中 s-adjvex=end; G.AdjListstart=s; if(G.GraphKind=0) /若是無向圖，再插入到終點(diǎn)的弧鏈中 s=(ArcNode *)malloc(sizeof(ArcNode);s-nextarc=G.AdjListend;s-adjvex=start;G.AdjListend=s; void DFSTraverse(Graph G)/深

9、度優(yōu)先遍歷圖G int i; printf(DFSTraverse:); for(i=1;i=G.vexnum;i+) visitedi=False; /訪問標(biāo)志數(shù)組初始化 for(i=1;i,i); for(w=FirstAdjVex(G,i);w;w=NextAdjVex(G,i,w) if(!visitedw) DFS(G,w); /對尚未訪問的鄰接頂點(diǎn)w調(diào)用DFSvoid BFSTraverse(Graph G)/按廣度優(yōu)先非遞歸的遍歷圖G，使用輔助隊(duì)列Q和訪問標(biāo)志數(shù)組visited int i,u,w; SqQueue Q; printf(BFSTreverse:); for(i=1

10、;i= G.vexnum;i+) visitedi=False; /訪問標(biāo)志數(shù)組初始化 Initial(Q); /初始化隊(duì)列 for(i=1;i,i); EnQueue(Q,i); /將序號(hào)i入隊(duì)列 while(!QueueEmpty(Q) /若隊(duì)列不空，繼續(xù) DeQueue(Q,u); /將隊(duì)頭元素出隊(duì)列并置為ufor(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w) if(!visitedw) /對u的尚未訪問的鄰接頂點(diǎn)w進(jìn)行訪問并入隊(duì)列 visitedw=True; printf(%d-,w); EnQueue(Q,w); printf(bb n);int

11、 FirstAdjVex(Graph G,int v)/在圖G中尋找第v個(gè)頂點(diǎn)的第一個(gè)鄰接頂點(diǎn) if(!G.AdjListv) return 0; else return(G.AdjListv-adjvex);int NextAdjVex(Graph G,int v,int u)/在圖G中尋找第v個(gè)頂點(diǎn)的相對于u的下一個(gè)鄰接頂點(diǎn) ArcNode *p; p=G.AdjListv; while(p-adjvex!=u) p=p-nextarc; /在頂點(diǎn)v的弧鏈中找到頂點(diǎn)u if(p-nextarc=NULL) return 0; /若已是最后一個(gè)頂點(diǎn)，返回0 else return(p-nex

12、tarc-adjvex); /返回下一個(gè)鄰接頂點(diǎn)的序號(hào)void Initial(SqQueue &Q) /隊(duì)列初始化 Q.front=Q.rear=0; BOOL QueueEmpty(SqQueue Q)/判斷隊(duì)列是否已空，若空返回True,否則返回False if(Q.front=Q.rear) return True; else return False;BOOL EnQueue(SqQueue &Q,int ch)/入隊(duì)列，成功返回True，失敗返回False if(Q.rear+1)%MAXQSIZE=Q.front) return False; Q.elemQ.rear=ch; Q

13、.rear=(Q.rear+1)%MAXQSIZE; return True;BOOL DeQueue(SqQueue &Q,int &ch)/出隊(duì)列,成功返回True，并用ch返回該元素值，失敗返回False if(Q.front=Q.rear) return False; ch=Q.elemQ.front; Q.front=(Q.front+1)%MAXQSIZE; return True; /成功出隊(duì)列，返回True2.最短路徑-迪杰斯特拉算法#include #include #include #include #define INFINITY 30000 /定義一個(gè)權(quán)值的最大值#de

14、fine MAX_VERTEX_NUM 20 /圖的最大頂點(diǎn)數(shù)enum BOOL False,True;typedef structint arcsMAX_VERTEX_NUMMAX_VERTEX_NUM; /鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)和邊數(shù)Graph;void CreateGraph(Graph &); /生成圖的鄰接矩陣void ShortestPath_DiJ(Graph,int,intMAX_VERTEX_NUM,int); /用迪杰斯特拉算法求從某一源點(diǎn)到其余頂點(diǎn)的最短路徑void Print_ShortestPath(Graph,int,intM

15、AX_VERTEX_NUM,int); /顯示最短路徑void main()Graph G; /采用鄰接矩陣結(jié)構(gòu)的圖 char j=y; int u; int PMAX_VERTEX_NUMMAX_VERTEX_NUM; /存放從源點(diǎn)到各頂點(diǎn)的最短路徑 int DMAX_VERTEX_NUM; /存放從源點(diǎn)到各頂點(diǎn)的最短路徑的距離printf(本程序?qū)⒀菔纠玫辖芩固乩惴ㄇ髇從圖的一點(diǎn)到其余頂點(diǎn)的最短路徑.n); printf(首先輸入圖的頂點(diǎn)數(shù)和弧數(shù).n格式：頂點(diǎn)數(shù)，弧數(shù)；例如:5,7n); printf(然后輸入各弧和權(quán)值.n格式：弧尾，弧頭，權(quán)值；例如:n1,2,10n1,3,18n2

16、,4,5n3,2,5n4,3,2n4,5,2n5,3,2n); printf(再輸入從哪個(gè)頂點(diǎn)出發(fā)，例如:1n); printf(程序?qū)?huì)找出從1到其余頂點(diǎn)的最短路徑.n); printf(10 1-2n17 1-2-4-3n15 1-2-4n17 1-2-4-5n);while(j!=N&j!=n) CreateGraph(G); /生成鄰接矩陣結(jié)構(gòu)的圖 printf(從哪個(gè)頂點(diǎn)出發(fā):); scanf(%d,&u); /輸入迪杰斯特拉算法中的起始頂點(diǎn) ShortestPath_DiJ(G,u,P,D); /利用迪杰斯特拉算法求最短路徑 Print_ShortestPath(G,u,P,D);

17、 /顯示最短路徑 printf(最短路徑演示完畢，繼續(xù)進(jìn)行嗎?(Y/N); scanf( %c,&j); void CreateGraph(Graph &G)/構(gòu)造鄰接矩陣結(jié)構(gòu)的圖G int i,j; int start,end,weight; printf(請輸入圖的頂點(diǎn)數(shù)和弧數(shù)(頂點(diǎn)數(shù)，弧數(shù)):); scanf(%d,%d,&G.vexnum,&G.arcnum); /輸入圖的頂點(diǎn)數(shù)和邊數(shù) for(i=1;i=G.vexnum;i+) for(j=1;j=G.vexnum;j+) G.arcsij=INFINITY; /初始化鄰接矩陣 printf(輸入各弧和權(quán)值，格式：弧尾，弧頭，權(quán)值n

18、); for(i=1;i=G.arcnum;i+) scanf(%d,%d,%d,&start,&end,&weight); /輸入邊的起點(diǎn)和終點(diǎn)及權(quán)值 G.arcsstartend=weight; void ShortestPath_DiJ(Graph G,int v0,int PMAX_VERTEX_NUM,int D)/用迪杰斯特拉算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑Pv及其帶權(quán)路徑長度Dv /若Pv00,表明從源點(diǎn)出發(fā)存在一條到頂點(diǎn)v的最短路徑，該路徑存放在Pv中 /finalv為True則表明已經(jīng)找到從v0到v的最短路徑 int i,j,w,v; int min; BOOL

19、 finalMAX_VERTEX_NUM; for(v=1;v=G.vexnum;v+) /初始化 finalv=False; Dv=G.arcsv0v; for(i=0;i=G.vexnum;i+) Pvi=0; /設(shè)空路徑 /if(DvINFINITY) Pv0=v0; /若從v0到v有直達(dá)路徑 Dv0=0; finalv0=True; /初始時(shí)，v0屬于S集 /開始主循環(huán)，每次求得v0到某個(gè)頂點(diǎn)v的最短路徑，并加v到S集 for(i=1;i=G.vexnum;i+) /尋找其余G.vexnum-1個(gè)頂點(diǎn) v=0; min=INFINITY; for(w=1;w=G.vexnum;w+)

20、/尋找當(dāng)前離v0最近的頂點(diǎn)v if(!finalw)&(Dwmin) v=w;min=Dw; if(!v) break; /若v=0表明所有與v0有通路的頂點(diǎn)均已找到了最短路徑，退出主循環(huán) finalv=True; /將v加入S集 for(j=0;Pvj!=0;j+) ; Pvj=v; /將路徑Pv延伸到頂點(diǎn)v for(w=1;w=G.vexnum;w+) /更新當(dāng)前最短路徑及距離 if(!finalw&(min+G.arcsvwDw) Dw=min+G.arcsvw; for(j=0;Pvj!=0;j+) Pwj=Pvj; void Print_ShortestPath(Graph G,in

21、t v0,int PMAX_VERTEX_NUM,int D)/顯示從頂點(diǎn)u到其余頂點(diǎn)的最短路徑及距離 int v,j; printf(The shortest path from Vertex %d to the other Vertex:n); for(v=1;v,v0); for(j=0;Pvj!=0;j+) printf(%d-,Pvj); printf(bb n); 3.最短路徑-弗洛依德算法#include #include #include #include #define INFINITY 10000 /定義權(quán)值的最大值 #define MAX_NUM 20 /圖的最大頂點(diǎn)數(shù)e

22、num BOOL False,True;typedef structint arcsMAX_NUMMAX_NUM; /鄰接矩陣 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)和邊數(shù)Graph;void CreateGraph(Graph &); /生成圖的鄰接矩陣void ShortestPath_Floyd(Graph,BOOLMAX_NUMMAX_NUM,intMAX_NUM); /用弗洛依德算法求每對頂點(diǎn)之間的最短路徑void Print_ShortestPath(Graph,BOOLMAX_NUMMAX_NUM,intMAX_NUM); /顯示用弗洛依德算法所求得的最短路徑voi

23、d Print_OnePath(int,int,int,BOOLMAX_NUMMAX_NUM); /顯示一對頂點(diǎn)之間的最短路徑void main()Graph G; /采用鄰接矩陣結(jié)構(gòu)的圖 char j=y; int u; BOOL PMAX_NUMMAX_NUMMAX_NUM; /存放每對頂點(diǎn)的最短路徑 int DMAX_NUMMAX_NUM; /存放每對頂點(diǎn)的最短路徑的距離printf(本程序演示弗洛依德算法求圖的每一對頂點(diǎn)之間的最短路徑。n); printf(首先輸入圖的頂點(diǎn)和弧的數(shù)目。n例如：3,5n); printf(接著輸入弧(i,j)和其權(quán)值。n例如：n1,2,4n2,1,6n1

24、,3,11n3,1,3n2,3,2n); printf(程序?qū)?huì)顯示出每對頂點(diǎn)之間的最短路徑值和所經(jīng)過的路徑：n); printf(4 1-2n6 1-2-3n5 2-3-1n2 2-3n3 3-1n7 3-1-2n);while(j!=N&j!=n) CreateGraph(G); /生成鄰接矩陣結(jié)構(gòu)的圖 ShortestPath_Floyd(G,P,D); /利用弗洛依德算法求最短路徑 Print_ShortestPath(G,P,D); /顯示每對頂點(diǎn)之間的最短路徑 printf(繼續(xù)執(zhí)行嗎?(Y/N); scanf( %c,&j); printf(程序運(yùn)行結(jié)束，按任意鍵退出窗口!);

25、getch();void CreateGraph(Graph &G)/構(gòu)造鄰接矩陣結(jié)構(gòu)的圖G int i,j; int start,end,weight; printf(請輸入頂點(diǎn)和弧的數(shù)目，格式：頂點(diǎn)數(shù)，弧數(shù)n); scanf(%d,%d,&G.vexnum,&G.arcnum); /輸入圖的頂點(diǎn)數(shù)和邊數(shù) for(i=1;i=G.vexnum;i+) for(j=1;j=G.vexnum;j+) G.arcsij=INFINITY; /初始化鄰接矩陣 printf(請輸入各條弧和其權(quán)值，格式：弧尾，弧頭，權(quán)值：n); for(i=1;i=G.arcnum;i+) scanf(%d,%d,%d,&start,&end,&weight); /輸入邊的起點(diǎn)和終點(diǎn)及權(quán)值 G.arcsstartend=weight; void ShortestPath_Floyd(Graph G,BOOL PMAX_NUMMAX_NUM,int DMAX_NUM)/用弗洛依德算法求有向網(wǎng)G的每對頂點(diǎn)v和w之間的最短路徑Pvw /及其帶權(quán)路徑長度Dvw, /若Pvwu為True,表明u是從v到w當(dāng)前求得最短路徑上的頂