图的深度优先周游_递归_邻接矩阵.c

图的深度优先算法

/* 用邻接矩阵表示的图的深度优先周游的递归算法*/


#include<stdio.h>
#define MAXVEX 6
#define MAX 0

typedef char VexType;

typedef float AdjType;

typedef struct 

{    /*VexType vexs[MAXVEX];                   顶点信息 */

     AdjType arcs[MAXVEX][MAXVEX];           /* 边信息 */

     int n;                                           /* 图的顶点个数 */

}GraphMatrix;

GraphMatrix graph={
	0,10,MAX,MAX,19,21,
	10,0,5,6,MAX,11,
	MAX,5,0,6,MAX,MAX,
	MAX,6,6,0,18,14,
	19,MAX,MAX,18,0,33,
	21,11,MAX,14,33,0,
	6};

#undef NULL
#define  NULL  -1

int  firstVertex(GraphMatrix* pgraph)

{    

      if(pgraph->n==0)

           return NULL;

      else return 0;

}

int  nextVertex(GraphMatrix* pgraph,int n)

{    

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

           return NULL;

      else return n+1;

}

int  firstAdjacent(GraphMatrix* pgraph, int i)

{    int k;

      for(k=0;k<pgraph->n;k++)

           if(pgraph->arcs[i][k]!=0) return k;

      return NULL; 

}  


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

{    int k;

      for(k=j+1; k<pgraph->n; k++)

           if(pgraph->arcs[i][k]!=0) return k;

      return NULL; 

}   


typedef int Vertex;
#define TRUE 1
#define FALSE 0

int visited[MAXVEX];
void dfs ( GraphMatrix* g , Vertex v );

void dft ( GraphMatrix* g )

{

           Vertex v ;

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

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

}

void dfs ( GraphMatrix* g , Vertex v )

{

           Vertex v1;

           visited[v] = TRUE ;
		   printf("%d ",v);

           for ( v1 = firstAdjacent ( g , v ); v1 != NULL ; v1=nextAdjacent ( g ,v, v1 ) )

                 if(visited[v1]==FALSE)

                       dfs ( g ,v1 );

}

int main(){
	dft(&graph);
	return 0;
}