考研數據結構之圖的深度遍歷的非遞歸C語言實現

考研數據結構，圖是一個很重要的知識點，圖的算法也比較重要，比如深度遍歷，廣度遍歷。而這些遍歷算法，一般都是遞歸遍歷。今天，我們來學習一下圖的深度遍歷（DFS）的非遞歸算法的C語言完整實現，供大家學習和掌握。

#include<stdio.h>

#include<stdlib.h>

#define MAXVEX 20

typedef struct EdgeNode EdgeNode;

typedef struct EdgeNode * PEdgeNode;

typedef struct EdgeNode * EdgeList;

struct EdgeNode

{ int endvex;

PEdgeNode nextedge;

};

typedef struct

{

EdgeList edgelist;

} VexNode;

typedef struct

{ VexNode vexs[MAXVEX];

int n;

}GraphList;

void insert(GraphList* p,int a,int b){

EdgeList pp;

PEdgeNode temp;

temp=(PEdgeNode)malloc(sizeof(EdgeNode));

temp->endvex=b;

temp->nextedge=NULL;

pp=p->vexs[a].edgelist;

if(pp==NULL)p->vexs[a].edgelist=temp;

else{

while(pp->nextedge!=NULL)

pp=pp->nextedge;

pp->nextedge=temp;

}

}

GraphList* makeList(){

GraphList* p;

int i;

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

p->n=8;

for(i=0;in;i++)

p->vexs[i].edgelist=NULL;

insert(p,0,1);

insert(p,0,2);

insert(p,1,3);

insert(p,1,4);

insert(p,2,5);

insert(p,2,6);

insert(p,3,7);

insert(p,4,7);

insert(p,5,6);

return p;

}

#define null -1

int firstVertex(GraphList* pgraph)

{

if(pgraph->n==0)

return null;

else return 0;

}

int nextVertex(GraphList* pgraph,int n)

{

if(n==pgraph->n-1)

return null;

else return n+1;

}

int firstAdjacent(GraphList* pgraph, int i)

{ if(pgraph->vexs[i].edgelist!=NULL)

return pgraph->vexs[i].edgelist->endvex;

else return null;

}

int nextAdjacent(GraphList* pgraph, int i, int j)

{ PEdgeNode p;

for(p=pgraph->vexs[i].edgelist; p!=NULL; p=p->nextedge)

if(p->endvex==j) {

if(p->nextedge!=NULL)

return p->nextedge->endvex;

else

return null;

}

return null;

}

typedef int Vertex;

#define TRUE 1

#define FALSE 0

typedef struct{

Vertex v;

Vertex k;

}DataType;

#define MAXNUM 20

struct SeqStack

{ DataType s[MAXNUM];

int t;

};

typedef struct SeqStack *PSeqStack;

PSeqStack createEmptyStack_seq( void )

{ PSeqStack pastack;

pastack = (PSeqStack)malloc(sizeof(struct SeqStack));

if (pastack==NULL)

printf("Out of space!!

");

else

pastack->t=-1;

return (pastack);

}

int isEmptyStack_seq( PSeqStack pastack )

{

return ( pastack->t == -1 );

}

void push_seq( PSeqStack pastack, DataType x )

{ if( pastack->t >= MAXNUM - 1 )

printf( "Overflow!

" );

else

{ pastack->t = pastack->t + 1;

pastack->s[pastack->t] = x;

}

}

void pop_seq( PSeqStack pastack )

{ if (pastack->t == -1 )

printf( "Underflow!

" );

else

pastack->t = pastack->t - 1;

}

DataType top_seq( PSeqStack pastack )

{

return (pastack->s[pastack->t]);

}

int visited[MAXVEX];

void dfs ( GraphList* g , Vertex v );

void dft ( GraphList* g )

{

Vertex v ;

for ( v =firstVertex ( g ) ; v != null ; v = nextVertex ( g , v ) )

if ( visited[v] == FALSE ) dfs ( g , v ) ;

}

void dfs ( GraphList* g , Vertex v )

{

DataType element;

Vertex v1,v2;

PSeqStack s ;

s = createEmptyStack_seq ( ) ;

element.v=v;

element.k=firstAdjacent(g,v);

push_seq ( s ,element) ;

printf("%d ",v);

visited[v] = TRUE ;

while ( !isEmptyStack_seq(s) ) {

element =top_seq ( s ) ;

pop_seq ( s );

v1 =element.v;

v2 =element.k;

while (v2!=null ) {

if ( visited[v2] == FALSE ) {

element.v=v1;

element.k=v2;

push_seq ( s, element);

visited[v2] = TRUE ;

printf("%d ",v2);

v1=v2;

v2=firstAdjacent(g,v1);

}

else v2= nextAdjacent(g , v1 , v2 ) ;

}

}

}

int main(){

GraphList* p=makeList();

dft(p);

return 0;

}

想了解最新考研資訊和院校指導，點擊上方頭像關注我，或給我發私信，也可關注上方圖片右下角的賬號，為你提供最新考研乾貨。