shen.cpp

1、深度优先搜索遍历图的算法：首先访问指定的起始顶点V0

#include<stdio.h>
#include<stdlib.h>
#define maxvertexnum 20  //设最大顶点数为20
typedef struct node    //定义表结点结构
{
  int adjvex;
  struct node *next;
}node;
typedef int vertextype;
typedef struct frontnode    //定义表头结点结构
{
  vertextype vertex;          
  node *firstedge;
}frontnode;
typedef frontnode AdjList[maxvertexnum];
typedef struct ALGraph
{ 
  AdjList adjlist;
  int n,e;
}adjlist;


int visited[maxvertexnum];
void GreatALGraph(ALGraph *G);
void DFSTraverseAL(ALGraph *G);
void DFSAL(ALGraph *G,int i);


void GreatALGraph(adjlist *G)       //建立有向图的邻接表存储
{
   int i,j,k;
   node *s;
   printf("请输入顶点数和边数:\n");
   scanf("%d,%d",&(G->n),&(G->e));  //读入顶点数和边数
   printf("请输入顶点信息:\n");
   for(i=0;i<G->n;i++)      //建立有n个顶点的顶点表
   {
     scanf("\n%c",&(G->adjlist[i].vertex));
     G->adjlist[i].firstedge=NULL;
   }
   printf("请输入边的信息(i,j):\n");
   for(k=0;k<G->e;k++)   //建立边表
   {
	 scanf("%d,%d",&i,&j);  //读入边<Vi,Vj>的顶点对应序号
     s=(node*)malloc(sizeof(node));
	 s->adjvex=j;         //邻接点序号为j
	 s->next=G->adjlist[i].firstedge;
	 G->adjlist[i].firstedge=s; 
     s=(node*)malloc(sizeof(node));
	 s->adjvex=i;         //邻接点序号为i
	 s->next=G->adjlist[j].firstedge;
	 G->adjlist[j].firstedge=s; 
   }
}//GrateALGraph

void DFSAL(adjlist *G,int i)  //以Vi为出发点对图G进行DFS搜索
{
  node *p;  
  printf("visit vertex:V%c\n",G->adjlist[i].vertex);
  visited[i]=1;   //标记Vi已访问
  p=G->adjlist[i].firstedge;   //取Vi边表的头指针
  while(p)  //依次搜索Vi的邻接点Vj,j=p->adjva
  {
     if(!visited[p->adjvex])
		 DFSAL(G,p->adjvex);
	 p=p->next;   //找Vi的下一个邻接点  
  }
}//DFSAL
void DFSTraverseAL(adjlist *G)    //深度优先遍历图G
{
  int i;
  for(i=0;i<G->n;i++)
	  visited[i]=0;
  for(i=0;i<G->n;i++)
	  if(!visited[i])
		  DFSAL(G,i);   //Vi未被访问过，从Vi开始DFS搜索
}//DFS

void main()
{
  adjlist Great;
  GreatALGraph(&Great);
  DFSTraverseAL(&Great);
}