Question

怎么用c语言写图的优先遍历程序？

Answer 1

写法：

图的遍历是指按某条搜索路径访问图中每个结点，使得每个结点均被访问一次，而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法，最近阿杰做了关于图的遍历的算法，下面是图的遍历深度优先的算法（C语言程序）：

#include<stdio.h>
#include<malloc.h>
#define MaxVertexNum 5
#define m 5
#define TRUE 1
#define NULL 0
typedef   struct   node
{ 
 int  adjvex;
 struct  node  *next;
}JD;
typedef   struct  EdgeNode
{
 int   vexdata;
    JD  *firstarc;
}TD;
typedef struct
{
 TD  ag[m];
 int n;
}ALGRAPH;
void DFS(ALGRAPH *G,int i)
{
 JD *p;
 int visited[80]; 
 printf("visit vertex:%d->",G->ag[i].vexdata);
 visited[i]=1;
 p=G->ag[i].firstarc; 
 while(p)
 {
  if (!visited[p->adjvex])
   DFS(G,p->adjvex);
  p=p->next;
 }
}
void creat(ALGRAPH *G)
{
 int i,m1,j;
 JD *p,*p1;
 printf("please input the number of graph\n");
 scanf("%d",&G->n);
 for(i=0;i<G->n;i++)
 {
  printf("please input the info of node %d",i);
  scanf("%d",&G->ag[i].vexdata);
  printf("please input the number of arcs which adj to  %d",i);
  scanf("%d",&m1);
  printf("please input the adjvex position of the first arc\n");
  p=(JD *)malloc(sizeof(JD));
  scanf("%d",&p->adjvex);
  p->next=NULL;
  G->ag[i].firstarc=p;
  p1=p;
  for(j=2 ;j<=m1;j++)
  {
   printf("please input the position of the next arc vexdata\n");
   p=(JD *)malloc(sizeof(JD));
   scanf("%d",&p->adjvex);
   p->next=NULL;
   p1->next=p;
   p1=p;
  }
 }
}
int  visited[MaxVertexNum];
void DFSTraverse(ALGRAPH *G)
{
 int i;
 for(i=0;i<G->n;i++)
  visited[i]=0;
 for(i=0;i<G->n;i++)
  if(!visited[i])
   DFS(G,i);
}
int main()
{
 ALGRAPH *G;
 printf("下面以临接表存储一个图；\n");
 creat(G);
 printf("下面以深度优先遍历该图 \n");
 DFSTraverse(G);
 getchar();
}