12 dfs.cpp

数据结构的必做编程题

#include<stdio.h>
#include<math.h>
#include<malloc.h>
#define MAX_VERTEX_NUM 100
#define MAX		1000
#include<string.h>

typedef struct ArcCell // 弧的定义
 { int  adj;     // 用1或0表示相邻否；
   int  quan;  // 该弧相关信息的指针
 }   AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM],Adj;

typedef struct // 图的定义
{        
      char     vexs[MAX_VERTEX_NUM];  // 顶点信息
      AdjMatrix    arcs;      // 弧的信息                     
      int    n, e;   // 顶点数，弧数             
  } MGraph;


void createMGraph(MGraph *G)
{  int i,j,k,w = 0;
   printf("\n请输入此无向图的顶点数和弧数：");
   scanf("%d %d",&(G->n),&(G->e));
   printf("\n请输入此图的各个结点的名称: ");
   for(i=1; i<=G->n; i++) 
   {getchar();
   scanf("%c",&(G->vexs[i]));
   }
   for(i=1; i<=G->n; i++)
       for(j=1; j<=G->n; j++)  
	   {
		   G->arcs[i][j].adj = 0;
           G->arcs[i][j].quan = (i==j?0:MAX);
	   }
   printf("\n 请依次输入这%d条弧的起点，终点(用邻接矩阵表示):",G->e);
      for(k=1; k<=G->e; k++)
        { 
		   printf("\n 第%d条弧:",k);
		   

		  scanf("%d %d",&i,&j);
 
		   G->arcs[i][j].adj = 1;
	
		   G->arcs[j][i].adj = 1;
	  }
}     //建无向网的邻接矩阵表示
int visited[MAX_VERTEX_NUM];
int FirstAdjVex(MGraph G,int v)
{
	int i;
	for(i=1;i<=G.n;i++)
	{
		if(G.arcs[v][i].adj == 1)
			return i;
	}
	return -1;
}
int NextAdiVex(MGraph G,int v,int w)
{
	int i;
	for(i=1;i<=G.n;i++)
	{
		if((G.arcs[v][i].adj == 1)&&(i!=w))
			return i;
	}
	return -1;
}


void DFS(MGraph G,int v)
{
    int top,w,stack[100];
    top = 1;
    stack[top]=v;
	while(top!=0)
	{
		while((visited[stack[top]]==0)&&(stack[top]!=-1))
		{
            w = stack[top];
			printf(" %c ",G.vexs[w]);
	        visited[w]=1;
			top++;
			stack[top]=NextAdiVex(G,w,stack[top - 2]);
		}
		top--;
		stack[top]=NextAdiVex(G,stack[top-1],stack[top]);
       	
	}

}
void DFSTravers(MGraph G)
{
    int i,v;
	for(i=1;i<=G.n;i++)
		visited[i]=0;
	for(v=1;v<=G.n;v++)
		if(!visited[v])
			DFS(G,v);
}
void main()
{
    MGraph G;
 	createMGraph(&G);
	printf("\nDFS深度优先搜索此图的结果为：");
    DFSTravers(G);
	printf("\n");
}