图的遍历（深度优先算法）（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(); }

评论