實(shí)驗(yàn)7圖的表示與遍歷

1、實(shí)驗(yàn)五 圖的表示與遍歷一、實(shí)驗(yàn)?zāi)康?、掌握?qǐng)D的鄰接矩陣和鄰接表表示2、掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先搜索方法 3、理解圖的應(yīng)用方法二、實(shí)驗(yàn)預(yù)習(xí)說明以下概念1、深度優(yōu)先搜索遍歷：從根開始一個(gè)一個(gè)搜索2、廣度優(yōu)先搜索遍歷：從根的鄰接點(diǎn)出發(fā)依次訪問3、拓?fù)渑判颍?一個(gè)無指向的點(diǎn)開始排序4、最小生成樹： 最小權(quán)的生成樹5、最短路徑： 路徑權(quán)數(shù)最小三、實(shí)驗(yàn)內(nèi)容和要求1、閱讀并運(yùn)行下面程序，根據(jù)輸入寫出運(yùn)行結(jié)果。#include#define N 20#define TRUE 1#define FALSE 0int visitedN; typedef struct /*隊(duì)列的定義*/ int dataN; i

2、nt front,rear;queue;typedef struct /*圖的鄰接矩陣*/ int vexnum,arcnum; char vexsN; int arcsNN;graph;void createGraph(graph *g); /*建立一個(gè)無向圖的鄰接矩陣*/void dfs(int i,graph *g); /*從第i個(gè)頂點(diǎn)出發(fā)深度優(yōu)先搜索*/void tdfs(graph *g); /*深度優(yōu)先搜索整個(gè)圖*/void bfs(int k,graph *g); /*從第k個(gè)頂點(diǎn)廣度優(yōu)先搜索*/void tbfs(graph *g); /*廣度優(yōu)先搜索整個(gè)圖*/void ini

3、t_visit(); /*初始化訪問標(biāo)識(shí)數(shù)組*/void createGraph(graph *g) /*建立一個(gè)無向圖的鄰接矩陣*/ int i,j; char v; g-vexnum=0; g-arcnum=0; i=0; printf(輸入頂點(diǎn)序列(以#結(jié)束)：n); while(v=getchar()!=#) g-vexsi=v; /*讀入頂點(diǎn)信息*/ i+; g-vexnum=i; /*頂點(diǎn)數(shù)目*/ for(i=0;ivexnum;i+) /*鄰接矩陣初始化*/ for(j=0;jvexnum;j+) g-arcsij=0; printf(輸入邊的信息：n); scanf(%d,%d

4、,&i,&j); /*讀入邊i,j*/ while(i!=-1) /*讀入i,j為1時(shí)結(jié)束*/ g-arcsij=1; g-arcsji=1; scanf(%d,%d,&i,&j); void dfs(int i,graph *g) /*從第i個(gè)頂點(diǎn)出發(fā)深度優(yōu)先搜索*/ int j; printf(%c,g-vexsi); visitedi=TRUE; for(j=0;jvexnum;j+) if(g-arcsij=1)&(!visitedj) dfs(j,g);void tdfs(graph *g) /*深度優(yōu)先搜索整個(gè)圖*/ int i; printf(n從頂點(diǎn)%C開始深度優(yōu)先搜索序列：,

5、g-vexs0); for(i=0;ivexnum;i+) if(visitedi!=TRUE) dfs(i,g);void bfs(int k,graph *g) /*從第k個(gè)頂點(diǎn)廣度優(yōu)先搜索*/ int i,j; queue qlist,*q; q=&qlist; q-rear=0; q-front=0; printf(%c,g-vexsk); visitedk=TRUE; q-dataq-rear=k; q-rear=(q-rear+1)%N; while(q-rear!=q-front) i=q-dataq-front; q-front=(q-front+1)%N; for(j=0;j

6、vexnum;j+) if(g-arcsij=1)&(!visitedj) printf(%c,g-vexsj); visitedj=TRUE; q-dataq-rear=j; q-rear=(q-rear+1)%N; void tbfs(graph *g) /*廣度優(yōu)先搜索整個(gè)圖*/ int i; printf(n從頂點(diǎn)%C開始廣度優(yōu)先搜索序列：,g-vexs0); for(i=0;ivexnum;i+) if(visitedi!=TRUE) bfs(i,g);void init_visit() /*初始化訪問標(biāo)識(shí)數(shù)組*/ int i; for(i=0;iN;i+) visitedi=FAL

7、SE;int main() graph ga; int i,j; createGraph(&ga); printf(無向圖的鄰接矩陣：n);for(i=0;iga.vexnum;i+) for(j=0;jga.vexnum;j+) printf(%3d,ga.arcsij); printf(n); init_visit(); tdfs(&ga); init_visit(); tbfs(&ga); return 0; 根據(jù)右圖的結(jié)構(gòu)驗(yàn)證實(shí)驗(yàn)，輸入：ABCDEFGH#ABCDEFGH012345670,10,20,51,31,42,52,63,74,7-1,-1 運(yùn)行結(jié)果：2、閱讀并運(yùn)行下面程序，

8、補(bǔ)充拓?fù)渑判蛩惴ā?include#include#define N 20typedef struct edgenode /*圖的鄰接表：鄰接鏈表結(jié)點(diǎn)*/ int adjvex; /*頂點(diǎn)序號(hào)*/ struct edgenode *next; /*下一個(gè)結(jié)點(diǎn)的指針*/edgenode;typedef struct vnode /*圖的鄰接表：鄰接表*/ char data; /*頂點(diǎn)信息*/ int ind; /*頂點(diǎn)入度*/ struct edgenode *link; /*指向鄰接鏈表指針*/vnode;void createGraph_list(vnode adjlist,int *p)

9、； /*建立有向圖的鄰接表*/void topSort(vnode g,int n)； /*拓?fù)渑判?/void createGraph_list(vnode adjlist,int *p) /*建立有向圖的鄰接表*/ int i,j,n,e; char v; edgenode *s; i=0;n=0;e=0; printf(輸入頂點(diǎn)序列(以#結(jié)束)：n); while(v=getchar()!=#) adjlisti.data=v; /*讀入頂點(diǎn)信息*/ adjlisti.link=NULL; adjlisti.ind=0; i+; n=i; *p=n; /*建立鄰接鏈表*/ printf(

10、n請(qǐng)輸入弧的信息(i=-1結(jié)束)：i,j:n); scanf(%d,%d,&i,&j); while(i!=-1) s=(struct edgenode*)malloc(sizeof(edgenode); s-adjvex=j; s-next=adjlisti.link; adjlisti.link=s; adjlistj.ind+; /*頂點(diǎn)j的入度加1*/ e+; scanf(%d,%d,&i,&j); printf(鄰接表:); for(i=0;i%d,s-adjvex); s=s-next; void topSort(vnode g,int n) /*拓?fù)渑判?/int main()

11、vnode adjlistN; int n,*p; p=&n; createGraph_list(adjlist,p); return 0; 根據(jù)輸入，輸出有向圖的拓?fù)渑判蛐蛄?。并畫出有向圖。輸入:ABCDEF#0,11,22,34,14,5-1,-1 運(yùn)行結(jié)果：3、閱讀并運(yùn)行下面程序。#include#define N 20#define TRUE 1#define INF 32766 /*鄰接矩陣中的無窮大元素*/#define INFIN 32767 /*比無窮大元素大的數(shù)*/typedef struct /*圖的鄰接矩陣*/ int vexnum,arcnum; char vexsN;

12、 int arcsNN;graph;void createGraph_w(graph *g,int flag);void prim(graph *g,int u);void dijkstra(graph g,int v);void showprim();void showdij();/*建帶權(quán)圖的鄰接矩陣,若flag為1則為無向圖，flag為0為有向圖*/void createGraph_w(graph *g,int flag) int i,j,w; char v; g-vexnum=0; g-arcnum=0; i=0; printf(輸入頂點(diǎn)序列(以#結(jié)束)：n); while(v=get

13、char()!=#) g-vexsi=v; /*讀入頂點(diǎn)信息*/ i+; g-vexnum=i; for(i=0;i6;i+) /*鄰接矩陣初始化*/ for(j=0;jarcsij=INF; printf(輸入邊的信息：n); scanf(%d,%d,%d,&i,&j,&w); /*讀入邊(i,j,w)*/ while(i!=-1) /*讀入i為1時(shí)結(jié)束*/ g-arcsij=w; if(flag=1) g-arcsji=w; scanf(%d,%d,%d,&i,&j,&w); void prim(graph *g,int u)/*出發(fā)頂點(diǎn)u*/ int lowcostN,closestN,

14、i,j,k,min; for(i=0;ivexnum;i+) /*求其他頂點(diǎn)到出發(fā)頂點(diǎn)u的權(quán)*/ lowcosti=g-arcsui; closesti=u; lowcostu=0; for(i=1;ivexnum;i+) /*循環(huán)求最小生成樹中的各條邊*/ min=INFIN; for(j=0;jvexnum;j+) /*選擇得到一條代價(jià)最小的邊*/ if(lowcostj!=0&lowcostjvexsclosestk,g-vexsk,lowcostk); /*輸出該邊*/ lowcostk=0; /*頂點(diǎn)k納入最小生成樹 */ for(j=0;jvexnum;j+) /*求其他頂點(diǎn)到頂點(diǎn)

15、k 的權(quán)*/ if(g-arcskj!=0&g-arcskjarcskj; closestj=k; void printPath(graph g,int startVex,int EndVex) int stackN,top=0; /*堆棧*/ int i,k,j; int flagN; /*輸出路徑頂點(diǎn)標(biāo)志*/ k=EndVex; for (i=0;i0) /*找j到k的路徑*/ for (i=0;i %c(%d) ,g.vexsi,g.arcsji); /*輸出j到k的路徑的頂點(diǎn)i*/ flagi=1; j=i; k=stack-top; break; else if (i!=k) sta

16、cktop+=i; /*break;*/ void dijkstra(graph g,int v) /*dijkstra算法求單源最短路徑*/ int pathNN,distN,sN; int mindis,i,j,u,k; for(i=0;ig.vexnum;i+) disti=g.arcsvi; si=0; for(j=0;jg.vexnum;j+) pathij=0; if(distiINF) pathiv=1; pathii=1; distv=0; sv=1; for(i=0,u=1;ig.vexnum;i+) mindis=INFIN; for(j=0;jg.vexnum;j+) i

17、f(sj=0) if(distjmindis) u=j; mindis=distj; su=1; for(j=0;jg.vexnum;j+) if(sj=0)&distu+g.arcsujdistj) distj=distu+g.arcsuj; for(k=0;k到各頂點(diǎn)的最短路徑n,g.vexsv); for(i=0;i頂點(diǎn)%c：,g.vexsv,g.vexsi); if(disti=INF|disti=0) printf(無路徑); else printf(%d ,disti); printf(經(jīng)過頂點(diǎn)：); printPath(g,v,i); /*輸出v到i的路徑*/ void showprim()/*最小生成樹prim算法演示*/ graph ga; createGraph_w(&ga,1); prim(&ga,0);void showdij() /*dijstra算法演示*/ graph ga; createGraph_w(&ga,0); dijkstra(ga,0);int main()showprim(); /*prim算法演示*/getchar(); showdij(); /*dijstra算法演示*