Chinaunix首页 | 论坛 | 博客
  • 博客访问: 391644
  • 博文数量: 199
  • 博客积分: 154
  • 博客等级: 入伍新兵
  • 技术积分: 1530
  • 用 户 组: 普通用户
  • 注册时间: 2011-03-14 08:43
文章分类

全部博文(199)

文章存档

2015年(101)

2014年(97)

2011年(1)

分类: C/C++

2015-05-18 14:32:01

typedef struct ArcNode{
/*单链表中的结点的类型*/
int  adjvex;                /*该边指向的顶点在顺序表中的位置*/
struct ArcNode  *next;        /*下一条边*/
}ArcNode;
typedef struct VNode{
/*顶点类型*/
int  data;            /*顶点中的数据信息*/
ArcNode  *firstarc;            /*指向单链表,即指向第一条边*/
}VNode;

int visited[5]={0,0,0,0,0};
CreatGraph(int n , VNode G[] ){
   int i,e;
   ArcNode *p , *q;
   printf("Input the information of the vertex\n");
   for(i=0;i        scanf("%d",&G[i]);
       G[i].firstarc = NULL;                        /*初始化第一条边为空*/
       }
   for(i=0;i    printf("Creat the edges for the %dth vertex\n",i) ;
   scanf("%d",&e);
    while(e!=-1){
      p = (ArcNode *)malloc(sizeof(ArcNode));            /*创建一条边*/
      p->next = NULL;
      p->adjvex = e;
      if(G[i].firstarc == NULL) G[i].firstarc = p;        /*i结点的第一条边*/
      else q->next = p;                            /*下一条边*/
      q = p;
      scanf("%d",&e);
      }
   }
}

int  FirstAdj(VNode G[],int v){
if(G[v].firstarc != NULL)  return (G[v].firstarc)->adjvex;
    return -1;
}

int  NextAdj(VNode G[],int v){
     ArcNode *p;
     p = G[v].firstarc;
     while( p!= NULL){
        if(visited[p->adjvex]) p = p->next;
        else return p->adjvex;
     }
     return -1;
}
void DFS(VNode G[],int v){
    int w;
   printf("%d ",G[v]);     /*访问当前顶点,打印出该顶点中的数据信息*/
    visited[v] = 1;         /*将顶点v对应的访问标记置1*/
    w = FirstAdj(G,v);      /*找到顶点v的第一个邻接点,如果无邻接点,返回-1*/
    while(w != -1){
    if(visited[w] == 0)        /*该顶点未被访问*/
            DFS(G,w);                /*递归地进行深度优先搜索*/
    w = NextAdj(G,v);        /*找到顶点v的下一个邻接点,如果无邻接点,返回-1*/
    }
}


main()
{
    VNode G[5];
    CreatGraph(5,G);
    DFS(G,0);
}
阅读(967) | 评论(0) | 转发(0) |
0

上一篇:二叉树

下一篇:python函数_abs()

给主人留下些什么吧!~~