實(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í)說(shuō)明以下概念1、深度優(yōu)先搜索遍歷：從根開(kāi)始一個(gè)一個(gè)搜索2、廣度優(yōu)先搜索遍歷：從根的鄰接點(diǎn)出發(fā)依次訪(fǎng)問(wèn)3、拓?fù)渑判颍?一個(gè)無(wú)指向的點(diǎn)開(kāi)始排序4、最小生成樹(shù)： 最小權(quán)的生成樹(shù)5、最短路徑： 路徑權(quán)數(shù)最小三、實(shí)驗(yàn)內(nèi)容和要求1、閱讀并運(yùn)行下面程序，根據(jù)輸入寫(xiě)出運(yùn)行結(jié)果。#include<stdio.h>#define N 20#define TRUE 1#define FALSE 0int visitedN; typedef struct /*隊(duì)列的定義

2、*/ int dataN; int front,rear;queue;typedef struct /*圖的鄰接矩陣*/ int vexnum,arcnum; char vexsN; int arcsNN;graph;void createGraph(graph *g); /*建立一個(gè)無(wú)向圖的鄰接矩陣*/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)先

3、搜索整個(gè)圖*/void init_visit(); /*初始化訪(fǎng)問(wèn)標(biāo)識(shí)數(shù)組*/void createGraph(graph *g) /*建立一個(gè)無(wú)向圖的鄰接矩陣*/ 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;i<g->vexnum;i+) /*鄰接矩陣初始化*

4、/ for(j=0;j<g->vexnum;j+) g->arcsij=0; printf("輸入邊的信息：n"); scanf("%d,%d",&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"

5、;,g->vexsi); visitedi=TRUE; for(j=0;j<g->vexnum;j+) if(g->arcsij=1)&&(!visitedj) dfs(j,g);void tdfs(graph *g) /*深度優(yōu)先搜索整個(gè)圖*/ int i; printf("n從頂點(diǎn)%C開(kāi)始深度優(yōu)先搜索序列：",g->vexs0); for(i=0;i<g->vexnum;i+) if(visitedi!=TRUE) dfs(i,g);void bfs(int k,graph *g) /*從第k個(gè)頂點(diǎn)廣度優(yōu)先搜索*

6、/ 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<g->vexnum;j+) if(g->

7、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開(kāi)始廣度優(yōu)先搜索序列：",g->vexs0); for(i=0;i<g->vexnum;i+) if(visitedi!=TRUE) bfs(i,g);void init_visit

8、() /*初始化訪(fǎng)問(wèn)標(biāo)識(shí)數(shù)組*/ int i; for(i=0;i<N;i+) visitedi=FALSE;int main() graph ga; int i,j; createGraph(&ga); printf("無(wú)向圖的鄰接矩陣：n");for(i=0;i<ga.vexnum;i+) for(j=0;j<ga.vexnum;j+) printf("%3d",ga.arcsij); printf("n"); init_visit(); tdfs(&ga); init_visit(); tbfs

9、(&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)行下面程序，補(bǔ)充拓?fù)渑判蛩惴ā?include<stdio.h>#include<malloc.h>#define N 20typedef struct edgenode /*圖的鄰接表：鄰接鏈表結(jié)點(diǎn)*/ int adjvex; /*頂點(diǎn)序號(hào)*/ struct edgenode *next; /*下一個(gè)結(jié)點(diǎn)的指針*/edgenode;typ

10、edef struct vnode /*圖的鄰接表：鄰接表*/ char data; /*頂點(diǎn)信息*/ int ind; /*頂點(diǎn)入度*/ struct edgenode *link; /*指向鄰接鏈表指針*/vnode;void createGraph_list(vnode adjlist,int *p)； /*建立有向圖的鄰接表*/void topSort(vnode g,int n)； /*拓?fù)渑判?/void createGraph_list(vnode adjlist,int *p) /*建立有向圖的鄰接表*/ int i,j,n,e; char v; edgenode *s; i=

11、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("n請(qǐng)輸入弧的信息(i=-1結(jié)束)：i,j:n"); scanf("%d,%d",&i,&j); while(i!=-1) s=(struct edgenode*)malloc(sizeof(

12、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<n;i+) /*輸出鄰接表*/ printf("n%c,%d:",adjlisti.data,adjlisti.ind); s=adjlisti.link; while(s!=NULL) printf("-&

13、gt;%d",s->adjvex); s=s->next; void topSort(vnode g,int n) /*拓?fù)渑判?/int main() vnode adjlistN; int n,*p; p=&n; createGraph_list(adjlist,p); return 0;§ 根據(jù)輸入，輸出有向圖的拓?fù)渑判蛐蛄小２?huà)出有向圖。輸入:ABCDEF#0,11,22,34,14,5-1,-1§ 運(yùn)行結(jié)果：3、閱讀并運(yùn)行下面程序。#include<stdio.h>#define N 20#define TRUE 1#de

14、fine INF 32766 /*鄰接矩陣中的無(wú)窮大元素*/#define INFIN 32767 /*比無(wú)窮大元素大的數(shù)*/typedef struct /*圖的鄰接矩陣*/ int vexnum,arcnum; char vexsN; 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則為無(wú)向圖，flag為0為有向圖*/vo

15、id 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=getchar()!='#') g->vexsi=v; /*讀入頂點(diǎn)信息*/ i+; g->vexnum=i; for(i=0;i<6;i+) /*鄰接矩陣初始化*/ for(j=0;j<6;j+) g->arcsij=INF; printf("輸入邊的信息：n"

16、;); 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,i,j,k,min; for(i=0;i<g->vexnum;i+) /*求其他頂點(diǎn)到出發(fā)頂點(diǎn)u的

17、權(quán)*/ lowcosti=g->arcsui; closesti=u; lowcostu=0; for(i=1;i<g->vexnum;i+) /*循環(huán)求最小生成樹(shù)中的各條邊*/ min=INFIN; for(j=0;j<g->vexnum;j+) /*選擇得到一條代價(jià)最小的邊*/ if(lowcostj!=0&&lowcostj<min) min=lowcostj; k=j; printf("(%c,%c)-%dn",g->vexsclosestk,g->vexsk,lowcostk); /*輸出該邊*/ l

18、owcostk=0; /*頂點(diǎn)k納入最小生成樹(shù) */ for(j=0;j<g->vexnum;j+) /*求其他頂點(diǎn)到頂點(diǎn)k 的權(quán)*/ if(g->arcskj!=0&&g->arcskj<lowcostj) lowcostj=g->arcskj; 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;i<g.vex

19、num;i+) flagi=0; j=startVex; printf("%c",g.vexsj); flagj=1; stacktop+=k; while (top>0) /*找j到k的路徑*/ for (i=0;i<g.vexnum;i+) if (pathki=1 && flagi=0) /*j到k的路徑含有i頂點(diǎn)*/ if (g.arcsji!=INF ) /*j到i的路徑含有中間頂點(diǎn)*/ printf("-> %c(%d) ",g.vexsi,g.arcsji); /*輸出j到k的路徑的頂點(diǎn)i*/ flagi=

20、1; j=i; k=stack-top; break; else if (i!=k) stacktop+=i; /*break;*/ void dijkstra(graph g,int v) /*dijkstra算法求單源最短路徑*/ int pathNN,distN,sN; int mindis,i,j,u,k; for(i=0;i<g.vexnum;i+) disti=g.arcsvi; si=0; for(j=0;j<g.vexnum;j+) pathij=0; if(disti<INF) pathiv=1; pathii=1; distv=0; sv=1; for(i

21、=0,u=1;i<g.vexnum;i+) mindis=INFIN; for(j=0;j<g.vexnum;j+) if(sj=0) if(distj<mindis) u=j; mindis=distj; su=1; for(j=0;j<g.vexnum;j+) if(sj=0)&&distu+g.arcsuj<distj) distj=distu+g.arcsuj; for(k=0;k<g.vexnum;k+) pathjk=pathuk; pathjj=1; printf("n頂點(diǎn)%c->到各頂點(diǎn)的最短路徑n",g.vexsv); for(i=0;i<g.vexnum;i+) printf("n頂點(diǎn)%