數(shù)據(jù)結(jié)構(gòu) 圖的四種遍歷

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

/****圖的存儲(chǔ)結(jié)構(gòu)定義及實(shí)現(xiàn)*************/

#defineMaxVerNum30/*最大頂點(diǎn)個(gè)數(shù)*/

#defineVextypechar

#defineInfoTypeint

#defineEdgetypeint

#defineINFINITE999

#defineMAXSIZE100

typedefstruct

(

Vextypevexs[MaxVerNum];/*頂點(diǎn)表7

Edgetypeedges[MaxVerNum][MaxVerNum];/*鄰接矩陣，即邊表*/

intn,e;/*頂點(diǎn)數(shù)和邊數(shù)*/

JMGragh;/*MGragh是以鄰接矩陣存儲(chǔ)的圖類型*/

typedefstructnode

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

intadjvex;/*鄰接點(diǎn)域，普通是放頂點(diǎn)對(duì)應(yīng)的序號(hào)或者在表頭向量中的

標(biāo)*/下

InfoTypeInfo;/*與邊（或者?。┫嚓P(guān)的信息*/

structnode*next;/*指向下一個(gè)鄰接點(diǎn)的指針域*/

JEdgeNode;

typedefstructvnode

(/*頂點(diǎn)結(jié)點(diǎn)*/

Vextypevertex;r頂點(diǎn)域*/

EdgeNode*firstedge;/*邊表頭指針*/

JVertexNode;

typedefstruct

(

VertexNodeadjlist[MaxVerNum];/*鄰接表*/

intn,e;/*頂點(diǎn)數(shù)和邊數(shù)*/

}ALGraph;/*ALGraph是以鄰接表方式存儲(chǔ)的圖類型7

voidCreatGraph(MGragh*G)/*建立圖G的鄰接矩陣7

inti,j,k,w;

charch;

輸入圖的頂點(diǎn)數(shù)和邊數(shù)，如

輸入頂點(diǎn)數(shù)和邊數(shù)*/

請(qǐng)逐個(gè)輸入圖的頂點(diǎn)：

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

(

while(ch=='')〃處理讀取回車符的異常情況

G->vexs[i]=ch;

//輸入頂點(diǎn)信息，建立頂點(diǎn)表7

}

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

(

for(j=0;jvG->n;j++)

(

if(i==j)

G->edges[i]0]=O;〃對(duì)角線元素為0

else

G->edges[i][j]=INFINITE;〃其它元素元素為無(wú)窮大

//G->edges[i][j]=O;/*初始化鄰接矩陣7

)

)

請(qǐng)逐個(gè)輸入圖的邊：如i,j：w...(索引下標(biāo)從0開(kāi)始

for(k=0;k<G->e;k++)

(

/*輸入e條邊,建立鄰接矩陣*/

G->edges[i][j]=w;

///*輸入e條邊,建立鄰接矩陣*/

//G->edges[i]0]=1;/*若加入G->edges[j][i]=1,則為無(wú)向圖的鄰接矩陣*/

)

〃打印圖

voidprintGragp(MGragh*G)

頂點(diǎn)如下：

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

)

鄰接矩陣如下：

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

(

for(intj=O;j<G->n;j++)

)

)

/*根據(jù)圖的鄰接矩陣存儲(chǔ)建立圖的鄰接表存儲(chǔ)*/

voidCreateALGraph(MGragh*G,ALGraph*alG)

(

alG->n=G->n;

alG->e=G->e;

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

(

alG->adjlist[i].vertex=G->vexs[i];

alG->adjlist[i].firstedge=NULL;

EdgeNode*p;

for(intj=O;j<G->n;j++)

(

if(G->edges[i][j]!=O&&G->edges[i][j]!=INFINITE)

(

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

p->adjvex=j;

p->lnfo=G->edges[i][j];

p->next=alG->adjlist[i].firstedge;

alG->adjlist[i].firstedge=p;

)

)

)

)

voidprintALGragp(ALGraph*alG)

(

鄰接表如下

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

EdgeNode*edge=alG->adjlist[i].firstedge;

while(edge)

edge=edge->next;

)

)

)

/★★★★★★★★★★★★★★★★★★★★★★★it木戈Ij，彳[****************

typedefstruct

(

intdata[MAXSIZE];

inttop;

JSeqStack,*PSeqStack;

PSeqStacklnit_SeqStack(void)

{〃創(chuàng)建一順序棧，入口參數(shù)無(wú)，返回一個(gè)指向順

序棧的指針，為零表示分配空間失敗*/

PSeqStackS;

S=(PSeqStack)malloc(sizeof(SeqStack));

if(S)

S->top=-1;

returnS;

)

voidDestroy_SeqStack(PSeqStack*SeqStackPoint)

{/*銷毀順序底，入口參數(shù)：為要銷毀的順序棧指針地址*/

if(*SeqStackPoint)

free(*SeqStackPoint);

*SeqStackPoint=NULL;

return;

}

intEmpty_SeqStack(PSeqStackS)

{/*判斷棧是否為空，入口參數(shù)：順序棧，返回值：1表示為空，0表示非空*/

if(S->top==-1)

return1;

else

return0;

intPush_SeqStack(PSeqStackS,intx)

{/*入口參數(shù)：順序棧，返回值：1表示入棧成功，0表示失敗。*/

if(S->top==MAXSIZE-1)

return0;/*棧滿不能入棧*/

else

(

S->top++;

S->data[S->top]=x;

return1;

)

)

intOut_SeqStack(PSeqStackS,int*x)

{/*取出棧頂元素，入口參數(shù)：順序棧，被取出的元素指針，這里用

指針帶出棧頂值返回值：1表示成功，0表示失敗。7

if(Empty_SeqStack(S))

return0;/*棧空*/

else

(

*x=S->data[S->top-];/*棧頂元素存入*x中7

return(1);

}

)

intGetStackTop(PSeqStackstack)

(

returnstack->top;

)

/************************隊(duì)列的定義與算法********************

typedefstruct

(

intdat磯MAXSIZE];/*隊(duì)列的存儲(chǔ)空間*/

intfront,rear;/*隊(duì)頭隊(duì)尾指針*/

}SeqQueue,*PSeqQueue;

PSeqQueuelnit_SeqQueue()

{/*返回值：新順序隊(duì)列指針，null表示失敗*/

PSeqQueueQ;

Q=(PSeqQueue)malloc(sizeof(SeqQueue));

if(Q){

Q->front=0;

Q->rear=O;

)

returnQ;

)

voidDestroy_SeqQueue(PSeqQueue*Q)

(

if(*Q)

free(*Q);

*Q=NULL;

intEmpty_SeqQueue(PSeqQueueQ)

/?返回值：1表示為空，0表示非空*/

{if(Q&&Q->front==Q->rear)

return(1);

else

return(0);

)

intln_SeqQueue(PSeqQueueQ,intx)

{/*返回值：1表示成功，一1表示隊(duì)滿溢出*/

if((Q->rear+1)%MAXSIZE==Q->front)

(

隊(duì)滿

return-1;/*隊(duì)滿不能入隊(duì)*/

)

else

{Q->rear=(Q->rear+1)%MAXSIZE;

Q->data[Q->rear]=x;

return1;/*入隊(duì)完成*/

)

)

intOut_SeqQueue(PSeqQueueQ,int*x)

{/*返回值：1表示成功，一1表示隊(duì)空，出隊(duì)的元素保存到*x7

if(Empty_SeqQueue(Q))

隊(duì)空

return-1;/*隊(duì)空不能出隊(duì)7

)

else

(

Q->front=(Q->front+1)%MAXSIZE;

*x=Q->data[Q->front];

return1;/*出隊(duì)完成*/

)

)

intFront_SeqQueue(PSeqQueueQ,int*x)

{/*返回值：1表示成功，一1表示隊(duì)空*/

if(Q->front==Q->rear)

(

隊(duì)空

return-1;/*隊(duì)空不能得到隊(duì)頭元素7

)

else

(

*x=Q->data[(Q->front+1)%MAXSIZE];

return1;/*取隊(duì)頭元素操作完成*/

}

)

/****圖的遍歷*************/

intvisited[MaxVerNum];

〃深度鄰接矩陣

voidDFS(MGraghg,intv)

visited[v]=1;

for(inti=0;i<g.n;i++)

(

if(g.edges[v][i]!=O&&g.edges[v][i]!=INFINITE)

(

if(!visited[i])

DFS(g,i);

)

)

)

voidDFSTranverseForMG(MGraghg)

鄰接矩陣的深度遍歷結(jié)果：

for(inti=O;i<g.n;i++)

visited[i]=O;

for(intj=O;j<g.n;j++)

(

if(!visited[j])

DFS(g,j);

)

)

〃廣度鄰接矩陣

voidBFS(MGraghg,intv)

(

PSeqQueueQ;

Q=lnit_SeqQueue();

visited[v]=1;

ln_SeqQueue(Q,v);

inti;

while(!Empty_SeqQueue(Q))

(

Out_SeqQueue(Q,&i);

for(intj=O;j<g.n;j++)

(

if(g.edges[i][j]!=O&&g.edges[i][j]!=INFINITE)

(

if(!visited[j])

(

visited[j]=1;

ln_SeqQueue(Q,j);

)

)

)

)

)

voidBFSTranverseForMG(MGraghg)

鄰接矩陣的廣度遍歷結(jié)果:

for(inti=O;i<g.n;i++)

visited[i]=O;

for(intj=O;j<g.n;j++)

(

if(!visited[j])

BFS(g,j);

)

)

〃深度鄰接表

voidDFS2(ALGraphg,intv)

(

EdgeNode*P；

intw;

visited[v]=1;

for(p=g.adjlist[v].firstedge;p;p=p->next)

(

w=p->adjvex;

if(!visited[w])

DFS2(g,w);

)

)

voidDFSTranverseForALG(ALGraphg)

(

鄰接表的深度遍歷結(jié)果：

for(inti=0;i<g.n;i++)

visited[i]=O;

for(intj=O;j<g,n;j++)

(

if(!visited[j])

DFS2(g,j);

)

)

〃廣度鄰接表

voidBFS2(ALGraphg,intv)

EdgeNode*p;

PSeqQueueQ;

Q=lnit_SeqQueue();

visited[v]=1;

ln_SeqQueue(Q,v);

inti,w;

while(!Empty_SeqQueue(Q))

(