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

鄰接表表示的圖：#include"stdio.h"

#include"stdlib.h"#defineMaxVertexNum50//定義最大頂點(diǎn)數(shù)typedefstructnode{//邊表結(jié)點(diǎn)

intadjvex;//鄰接點(diǎn)域

structnode*next;//鏈域

}EdgeNode;

typedefstructvnode{//頂點(diǎn)表結(jié)點(diǎn)

charvertex;//頂點(diǎn)域

EdgeNode*firstedge;//邊表頭指針

}VertexNode;

typedefVertexNodeAdjList[MaxVertexNum];//AdjList是鄰接表類型

typedefstruct{

AdjListadjlist;//鄰接表

intn,e;//圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)

}ALGraph;//圖類型//=========建立圖的鄰接表=======

voidCreatALGraph(ALGraph*G)

{

inti,j,k;

chara;

EdgeNode*s;//定義邊表結(jié)點(diǎn)

printf("InputVertexNum(n)andEdgesNum(e):");

scanf("%d,%d",&G->n,&G->e);//讀入頂點(diǎn)數(shù)和邊數(shù)

fflush(stdin);//清空內(nèi)存緩沖

printf("InputVertexstring:");

for(i=0;i<G->n;i++)//建立邊表

{

scanf("%c",&a);

G->adjlist[i].vertex=a;//讀入頂點(diǎn)信息

G->adjlist[i].firstedge=NULL;//邊表置為空表

}

printf("Inputedges,CreatAdjacencyList\n");

for(k=0;k<G->e;k++){//建立邊表

scanf("%d%d",&i,&j);//讀入邊（Vi，Vj）的頂點(diǎn)對(duì)序號(hào)

s=(EdgeNode*)malloc(sizeof(EdgeNode));//生成邊表結(jié)點(diǎn)

s->adjvex=j;//鄰接點(diǎn)序號(hào)為j

s->next=G->adjlist[i].firstedge;

G->adjlist[i].firstedge=s;//將新結(jié)點(diǎn)*S插入頂點(diǎn)Vi的邊表頭部

s=(EdgeNode*)malloc(sizeof(EdgeNode));

s->adjvex=i;//鄰接點(diǎn)序號(hào)為i

s->next=G->adjlist[j].firstedge;

G->adjlist[j].firstedge=s;//將新結(jié)點(diǎn)*S插入頂點(diǎn)Vj的邊表頭部

}

}

//=========定義標(biāo)志向量，為全局變量=======

typedefenum{FALSE,TRUE}Boolean;

Booleanvisited[MaxVertexNum];

//========DFS：深度優(yōu)先遍歷的遞歸算法======

voidDFSM(ALGraph*G,inti)

{//以Vi為出發(fā)點(diǎn)對(duì)鄰接鏈表表示的圖G進(jìn)行DFS搜索

EdgeNode*p;

printf("%c",G->adjlist[i].vertex);//訪問頂點(diǎn)Vi

visited[i]=TRUE;//標(biāo)記Vi已訪問

p=G->adjlist[i].firstedge;//取Vi邊表的頭指針

while(p){//依次搜索Vi的鄰接點(diǎn)Vj，這里j=p->adjvex

if(!visited[p->adjvex])//若Vj尚未被訪問

DFSM(G,p->adjvex);//則以Vj為出發(fā)點(diǎn)向縱深搜索

p=p->next;//找Vi的下一個(gè)鄰接點(diǎn)

}

}

voidDFS(ALGraph*G)

{

inti;

for(i=0;i<G->n;i++)

visited[i]=FALSE;//標(biāo)志向量初始化

for(i=0;i<G->n;i++)

if(!visited[i])//Vi未訪問過

DFSM(G,i);//以Vi為源點(diǎn)開始DFS搜索

}//==========BFS：廣度優(yōu)先遍歷=========

voidBFS(ALGraph*G,intk)

{//以Vk為源點(diǎn)對(duì)用鄰接鏈表表示的圖G進(jìn)行廣度優(yōu)先搜索

inti,f=0,r=0;EdgeNode*p;

intcq[MaxVertexNum];//定義FIFO隊(duì)列

for(i=0;i<G->n;i++)

visited[i]=FALSE;//標(biāo)志向量初始化

for(i=0;i<=G->n;i++)

cq[i]=-1;//初始化標(biāo)志向量

printf("%c",G->adjlist[k].vertex);//訪問源點(diǎn)Vk

visited[k]=TRUE;

cq[r]=k;//Vk已訪問，將其入隊(duì)。注意，實(shí)際上是將其序號(hào)入隊(duì)

while(cq[f]!=-1){//隊(duì)列非空則執(zhí)行

i=cq[f];f=f+1;//Vi出隊(duì)

p=G->adjlist[i].firstedge;//取Vi的邊表頭指針

}

voidDFS(MGraph*G)

{

inti;

for(i=0;i<G->n;i++)

visited[i]=FALSE;//標(biāo)志向量初始化

for(i=0;i<G->n;i++)

if(!visited[i])//Vi未訪問過

DFSM(G,i);//以Vi為源點(diǎn)開始DFS搜索

}

//===========BFS：廣度優(yōu)先遍歷=======

voidBFS(MGraph*G,intk)

{//以Vk為源點(diǎn)對(duì)用鄰接矩陣表示的圖G進(jìn)行廣度優(yōu)先搜索

inti,j,f=0,r=0;

intcq[MaxVertexNum];//定義隊(duì)列

for(i=0;i<G->n;i++)

visited[i]=FALSE;//標(biāo)志向量初始化

for(i=0;i<G->n;i++)

cq[i]=-1;//隊(duì)列初始化

printf("%c",G->vexs[k]);//訪問源點(diǎn)Vk

visited[k]=TRUE;

cq[r]=k;//Vk已訪問，將其入隊(duì)。注意，實(shí)際上是將其序號(hào)入隊(duì)

while(cq[f]!=-1){//隊(duì)非空則執(zhí)行

i=cq[f];f=f+1;//Vf出隊(duì)

for(j=0;j<G->n;j++)//依次Vi的鄰接點(diǎn)Vj

if(!visited[j]&&G->edges[i][j]==1){//Vj未訪問

printf("%c",G->vexs[j]);//訪問Vj

visited[j]=TRUE;

r=r+1;cq[r]=j;//訪問過Vj入隊(duì)

}

}

}

//==========main=====

voidmain()

{

//inti;

MGraph*G;

G=(