C語(yǔ)言版圖的深度和廣度優(yōu)先遍歷源代碼Word版

1、鄰接表表示的圖：#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 50 /定義最大頂點(diǎn)數(shù)typedef struct node /邊表結(jié)點(diǎn)int adjvex; /鄰接點(diǎn)域struct node *next; /鏈域EdgeNode;typedef struct vnode /頂點(diǎn)表結(jié)點(diǎn)char vertex; /頂點(diǎn)域EdgeNode *firstedge; /邊表頭指針VertexNode;typedef VertexNode AdjListMaxVertexNum; /AdjList是鄰

2、接表類型typedef struct AdjList adjlist; /鄰接表int n,e; /圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) ALGraph; /圖類型/=建立圖的鄰接表=void CreatALGraph(ALGraph *G)int i,j,k;char a;EdgeNode *s; /定義邊表結(jié)點(diǎn)printf("Input VertexNum(n) and EdgesNum(e): ");scanf("%d,%d",&G->n,&G->e); /讀入頂點(diǎn)數(shù)和邊數(shù)fflush(stdin); /清空內(nèi)存緩沖printf(&qu

3、ot;Input Vertex string:");for(i=0;i<G->n;i+) /建立邊表scanf("%c",&a);G->adjlisti.vertex=a; /讀入頂點(diǎn)信息G->adjlisti.firstedge=NULL; /邊表置為空表printf("Input edges,Creat Adjacency Listn");for(k=0;k<G->e;k+) /建立邊表 scanf("%d%d",&i,&j); /讀入邊（Vi，Vj）的頂點(diǎn)對(duì)序

4、號(hào)s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成邊表結(jié)點(diǎn)s->adjvex=j; /鄰接點(diǎn)序號(hào)為js->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s; /將新結(jié)點(diǎn)*S插入頂點(diǎn)Vi的邊表頭部s=(EdgeNode *)malloc(sizeof(EdgeNode); s->adjvex=i; /鄰接點(diǎn)序號(hào)為is->next=G->adjlistj.firstedge; G->adjlistj.firstedge=s; /將新結(jié)點(diǎn)*S插入頂點(diǎn)Vj的邊表頭部/

5、=定義標(biāo)志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度優(yōu)先遍歷的遞歸算法=void DFSM(ALGraph *G,int i)/以Vi為出發(fā)點(diǎn)對(duì)鄰接鏈表表示的圖G進(jìn)行DFS搜索EdgeNode *p;printf("%c",G->adjlisti.vertex); /訪問(wèn)頂點(diǎn)Vivisitedi=TRUE; /標(biāo)記Vi已訪問(wèn)p=G->adjlisti.firstedge; /取Vi邊表的頭指針while(p) /依次搜索Vi的鄰接點(diǎn)Vj，這里j=p-&g

6、t;adjvexif(! visitedp->adjvex) /若Vj尚未被訪問(wèn)DFSM(G,p->adjvex); /則以Vj為出發(fā)點(diǎn)向縱深搜索p=p->next; /找Vi的下一個(gè)鄰接點(diǎn)void DFS(ALGraph *G)int i;for(i=0;i<G->n;i+)visitedi=FALSE; /標(biāo)志向量初始化for(i=0;i<G->n;i+)if(!visitedi) /Vi未訪問(wèn)過(guò) DFSM(G,i); /以Vi為源點(diǎn)開(kāi)始DFS搜索 /=BFS：廣度優(yōu)先遍歷=void BFS(ALGraph *G,int k) /以Vk為源點(diǎn)對(duì)用鄰

7、接鏈表表示的圖G進(jìn)行廣度優(yōu)先搜索int i,f=0,r=0; EdgeNode *p; int cqMaxVertexNum; /定義FIFO隊(duì)列 for(i=0;i<G->n;i+)visitedi=FALSE; /標(biāo)志向量初始化for(i=0;i<=G->n;i+)cqi=-1; /初始化標(biāo)志向量printf("%c",G->adjlistk.vertex); /訪問(wèn)源點(diǎn)Vkvisitedk=TRUE;cqr=k; /Vk已訪問(wèn)，將其入隊(duì)。注意，實(shí)際上是將其序號(hào)入隊(duì) while(cqf!=-1) / 隊(duì)列非空則執(zhí)行i=cqf; f=f+1;

8、 /Vi出隊(duì)p=G->adjlisti.firstedge; /取Vi的邊表頭指針while(p) /依次搜索Vi的鄰接點(diǎn)Vj（令p->adjvex=j）if(!visitedp->adjvex) /若Vj未訪問(wèn)過(guò)printf("%c",G->adjlistp->adjvex.vertex); /訪問(wèn)Vjvisitedp->adjvex=TRUE;r=r+1; cqr=p->adjvex; /訪問(wèn)過(guò)的Vj入隊(duì)p=p->next; /找Vi的下一個(gè)鄰接點(diǎn)/endwhile/=主函數(shù)=void main()/int i;ALGra

9、ph *G;G=(ALGraph *)malloc(sizeof(ALGraph);CreatALGraph(G);printf("Print Graph DFS: ");DFS(G);printf("n");printf("Print Graph BFS: ");BFS(G,3);printf("n");鄰接矩陣表示的圖：#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 100 /定義最大頂點(diǎn)數(shù)typedef s

10、tructchar vexsMaxVertexNum; /頂點(diǎn)表int edgesMaxVertexNumMaxVertexNum; /鄰接矩陣，可看作邊表int n,e; /圖中的頂點(diǎn)數(shù)n和邊數(shù)eMGraph; /用鄰接矩陣表示的圖的類型/=建立鄰接矩陣=void CreatMGraph(MGraph *G)int i,j,k;char a;printf("Input VertexNum(n) and EdgesNum(e): ");scanf("%d,%d",&G->n,&G->e); /輸入頂點(diǎn)數(shù)和邊數(shù)scanf(&qu

11、ot;%c",&a); printf("Input Vertex string:");for(i=0;i<G->n;i+) scanf("%c",&a);G->vexsi=a; /讀入頂點(diǎn)信息，建立頂點(diǎn)表for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)G->edgesij=0; /初始化鄰接矩陣printf("Input edges,Creat Adjacency Matrixn");for(k=0;k<G->e;k+) /讀

12、入e條邊，建立鄰接矩陣 scanf("%d%d",&i,&j); /輸入邊（Vi，Vj）的頂點(diǎn)序號(hào)G->edgesij=1; G->edgesji=1; /若為無(wú)向圖，矩陣為對(duì)稱矩陣；若建立有向圖，去掉該條語(yǔ)句 /=定義標(biāo)志向量，為全局變量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度優(yōu)先遍歷的遞歸算法=void DFSM(MGraph *G,int i) /以Vi為出發(fā)點(diǎn)對(duì)鄰接矩陣表示的圖G進(jìn)行DFS搜索，鄰接矩陣是0，1矩陣int j;printf(&q

13、uot;%c",G->vexsi); /訪問(wèn)頂點(diǎn)Vivisitedi=TRUE; /置已訪問(wèn)標(biāo)志for(j=0;j<G->n;j+) /依次搜索Vi的鄰接點(diǎn)if(G->edgesij=1 && ! visitedj)DFSM(G,j); /（Vi，Vj）E，且Vj未訪問(wèn)過(guò)，故Vj為新出發(fā)點(diǎn)void DFS(MGraph *G) int i;for(i=0;i<G->n;i+)visitedi=FALSE; /標(biāo)志向量初始化for(i=0;i<G->n;i+)if(!visitedi) /Vi未訪問(wèn)過(guò)DFSM(G,i);

14、/以Vi為源點(diǎn)開(kāi)始DFS搜索/=BFS：廣度優(yōu)先遍歷=void BFS(MGraph *G,int k) /以Vk為源點(diǎn)對(duì)用鄰接矩陣表示的圖G進(jìn)行廣度優(yōu)先搜索int i,j,f=0,r=0;int cqMaxVertexNum; /定義隊(duì)列 for(i=0;i<G->n;i+)visitedi=FALSE; /標(biāo)志向量初始化for(i=0;i<G->n;i+)cqi=-1; /隊(duì)列初始化printf("%c",G->vexsk); /訪問(wèn)源點(diǎn)Vkvisitedk=TRUE;cqr=k; /Vk已訪問(wèn)，將其入隊(duì)。注意，實(shí)際上是將其序號(hào)入隊(duì)while(cqf!=-1) /隊(duì)非空則執(zhí)行i=cqf; f=f+1; /Vf出隊(duì)for(j=0;j<G->n;j+) /依次Vi的鄰接點(diǎn)Vjif(!visitedj && G->edgesij=1) /Vj未訪問(wèn)printf("%c",G->vexsj); /訪問(wèn)Vjvisitedj=TRUE; r=r+1; cqr=j; /訪問(wèn)過(guò)Vj入隊(duì)/=main=void main()/int i;MGraph *G;G=(MGraph *)malloc(si