数据结构 图的四种遍历

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

/****图的存储结构定义及实现*************/

#defineMaxVerNum30/*最大顶点个数*/

#defineVextypechar

#defineInfoTypeint

#defineEdgetypeint

#defineINFINITE999

#defineMAXSIZE100

typedefstruct

(

Vextypevexs[MaxVerNum];/*顶点表7

Edgetypeedges[MaxVerNum][MaxVerNum];/*邻接矩阵，即边表*/

intn,e;/*顶点数和边数*/

JMGragh;/*MGragh是以邻接矩阵存储的图类型*/

typedefstructnode

{/*表结点*/

intadjvex;/*邻接点域，普通是放顶点对应的序号或者在表头向量中的

标*/下

InfoTypeInfo;/*与边（或者弧）相关的信息*/

structnode*next;/*指向下一个邻接点的指针域*/

JEdgeNode;

typedefstructvnode

(/*顶点结点*/

Vextypevertex;r顶点域*/

EdgeNode*firstedge;/*边表头指针*/

JVertexNode;

typedefstruct

(

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

intn,e;/*顶点数和边数*/

}ALGraph;/*ALGraph是以邻接表方式存储的图类型7

voidCreatGraph(MGragh*G)/*建立图G的邻接矩阵7

inti,j,k,w;

charch;

输入图的顶点数和边数，如

输入顶点数和边数*/

请逐个输入图的顶点：

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

(

while(ch=='')〃处理读取回车符的异常情况

G->vexs[i]=ch;

//输入顶点信息，建立顶点表7

}

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

(

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

(

if(i==j)

G->edges[i]0]=O;〃对角线元素为0

else

G->edges[i][j]=INFINITE;〃其它元素元素为无穷大

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

)

)

请逐个输入图的边：如i,j：w...(索引下标从0开始

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

(

/*输入e条边,建立邻接矩阵*/

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

///*输入e条边,建立邻接矩阵*/

//G->edges[i]0]=1;/*若加入G->edges[j][i]=1,则为无向图的邻接矩阵*/

)

〃打印图

voidprintGragp(MGragh*G)

顶点如下：

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

)

邻接矩阵如下：

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

(

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

)

)

/*根据图的邻接矩阵存储建立图的邻接表存储*/

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)

{〃创建一顺序栈，入口参数无，返回一个指向顺

序栈的指针，为零表示分配空间失败*/

PSeqStackS;

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

if(S)

S->top=-1;

returnS;

)

voidDestroy_SeqStack(PSeqStack*SeqStackPoint)

{/*销毁顺序底，入口参数：为要销毁的顺序栈指针地址*/

if(*SeqStackPoint)

free(*SeqStackPoint);

*SeqStackPoint=NULL;

return;

}

intEmpty_SeqStack(PSeqStackS)

{/*判断栈是否为空，入口参数：顺序栈，返回值：1表示为空，0表示非空*/

if(S->top==-1)

return1;

else

return0;

intPush_SeqStack(PSeqStackS,intx)

{/*入口参数：顺序栈，返回值：1表示入栈成功，0表示失败。*/

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

return0;/*栈满不能入栈*/

else

(

S->top++;

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

return1;

)

)

intOut_SeqStack(PSeqStackS,int*x)

{/*取出栈顶元素，入口参数：顺序栈，被取出的元素指针，这里用

指针带出栈顶值返回值：1表示成功，0表示失败。7

if(Empty_SeqStack(S))

return0;/*栈空*/

else

(

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

return(1);

}

)

intGetStackTop(PSeqStackstack)

(

returnstack->top;

)

/************************队列的定义与算法********************

typedefstruct

(

intdat矶MAXSIZE];/*队列的存储空间*/

intfront,rear;/*队头队尾指针*/

}SeqQueue,*PSeqQueue;

PSeqQueuelnit_SeqQueue()

{/*返回值：新顺序队列指针，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表示队满溢出*/

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

(

队满

return-1;/*队满不能入队*/

)

else

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

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

return1;/*入队完成*/

)

)

intOut_SeqQueue(PSeqQueueQ,int*x)

{/*返回值：1表示成功，一1表示队空，出队的元素保存到*x7

if(Empty_SeqQueue(Q))

队空

return-1;/*队空不能出队7

)

else

(

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

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

return1;/*出队完成*/

)

)

intFront_SeqQueue(PSeqQueueQ,int*x)

{/*返回值：1表示成功，一1表示队空*/

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

(

队空

return-1;/*队空不能得到队头元素7

)

else

(

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

return1;/*取队头元素操作完成*/

}

)

/****图的遍历*************/

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)

邻接矩阵的深度遍历结果：

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)

邻接矩阵的广度遍历结果:

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)

(

邻接表的深度遍历结果：

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))

(