正文

图的遍历(深度优先算法)(C语言程序)2011-04-17 10:53:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/edwardguo/52432.html

分享到:

图的遍历(深度优先算法)(C语言程序)

图的遍历是指按某条搜索路径访问图中每个结点,使得每个结点均被访问一次,而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法,最近阿杰做了关于图的遍历的算法,下面是图的遍历深度优先的算法(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();
}

阅读(6525) | 评论(1)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册