dfs.cpp

数据结构中的DFS问题

#include <stdio.h>
#include <malloc.h>
#define max 100  //顶点最多个数
struct ArcNode   //邻接点结构体
{
  int adjvex;     //邻接点序号
  char info;       //邻接点内容
  struct ArcNode *nextarc;   //下一个邻接点
};
struct vexnode     //顶点结构体
{
  char data;       //顶点内容
  struct ArcNode *firstarc;    //此结点的第一个邻接点
};
void creatgraph(vexnode *g[])
{
  int n,e,i,s,d;
  struct ArcNode *p;
  printf("输入结点数（n）\n");
  scanf("%d",&n);
  printf("输入边数（e）\n");
  scanf("%d",&e);
  for(i=0;i<n;i++)      //结点初始化
  {
    printf("输入第%d个结点的内容(data):",i);
	scanf("%c",&(g[i]->data));
	g[i]->firstarc=NULL;    //结点第一个邻接点为空
  }
  for(i=0;i<e;i++)   //邻接点初始化
  {
    printf("输入第%d条边的起点序号（s）和终点序号（d）：",i+1);
	scanf("%d,%d",&s,&d);
	p=(ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex=d;   //邻接点等于边的终点
	p->info=g[d]->data;
	p->nextarc=g[s]->firstarc; //将p插入到s的邻接表中
	g[s]->firstarc=p;
  }
}
void dfs(vexnode *g[],int v)
{
  int i,n;
  ArcNode *p;
  int visit[max],top=-1,a[max];
  for(i=0;i<max;i++)
  {
    visit[i]=0;   //结点访问标志为0，表示开始时所有接点均未访问
  }
  printf("%d",v); //显示第一个结点
  top++;    
  a[top]=v;
  visit[v]=1;     
  while(top>-1)
  {
    n=a[top];
	top--;
	p=g[n]->firstarc;
	while((p!=NULL)&&(visit[p->adjvex]==1)) //找到第n个顶点的未访问的邻接点
      p=p->nextarc;
	if(p==NULL)  //若此顶点无邻接点或所有邻接点均被访问
	  top--;    //访问下一个顶点
	else
	{
	  n=p->adjvex;
      printf("%d",n);
	  visit[n]=1;
	  top++;
	  a[top]=n;
	}
  }

}
void main()
{ 
  vexnode *g[max];
  creatgraph(g);
  dfs(g,0);
}