标题:邻接表的深度优先遍历
只看楼主
qwe885167759
Rank: 4
等 级:业余侠客
威 望:5
帖 子:148
专家分:259
注 册:2013-3-12
结帖率:72.22%
已结贴  问题点数:10 回复次数:1 
邻接表的深度优先遍历
求指点,错哪了,不能遍历全部的节点
//圖的鄰接表表示
#include<stdio.h>
#include<stdlib.h>
#define max_vertex_num  20
#define null 0
#define Gameover 0
int visited[max_vertex_num];
int (*visitfunc)(int v);
typedef struct arcnode
{
    int adjvex;
    struct arcnode * next;
}arcnode;
typedef struct vnode
{
    int data;
    arcnode * fristarc;
}vnode,adjlist[max_vertex_num];
typedef struct
{
    adjlist vertices;
    int vexnum,arcnum;
}Algraph;

Algraph G;

int create(Algraph & G)
{
     printf("请输入顶点数目:\n");
     scanf("%d",&G.vexnum);
     printf("请输入弧的数目:\n");
     scanf("%d",&G.arcnum);
     printf("请输入顶点的信息:\n");
     for(int i=0;i<G.vexnum;i++)
     {
         scanf("%d",&G.vertices[i].data);
         G.vertices[i].fristarc=null;
     }
     for(int k=0;k<G.arcnum;k++)
     {
         arcnode * p;
         int i,j;
         printf("请输入弧的弧头和弧尾:\n");
         scanf("%d %d",&i,&j);
         p=(arcnode *)malloc(sizeof(arcnode));
         p->adjvex=j;
         if(!p)
         {
            printf("Gameover\n");
            return 0;
         }
         p->next=G.vertices[i].fristarc;
         G.vertices[i].fristarc=p;
     }
return 1;     
}

int put(Algraph & G)
{
    arcnode  *p;
    printf("输出图:\n");
    for(int k=0;k<G.vexnum;k++)
    {
        p=G.vertices[k].fristarc;
        while(p!=null)
        {
            printf("(%d->%d)\n",k,p->adjvex);
            p=p->next;
        }
    }
    return 1;
}

int visit(int v)
{
    printf("%d\n",G.vertices[v].data);
    return 1;
}

int firstadjvex(Algraph & G,int v)
{
    int w ;
    if(G.vertices[v].fristarc!=null)
        w=G.vertices[v].fristarc->adjvex;
    else
        w=-1;
    return w;
}

int nextadjvex(Algraph & G , int v, int w)
{
   if(G.vertices[v].fristarc->next->next!=null)
       w=G.vertices[v].fristarc->next->adjvex;
   else
       w=-1;
   return w;
}

void DFS(Algraph & G,int v)
{

    int w;
    visited[v]=1;
    visitfunc(v);
    printf("\n");
    for(w=firstadjvex(G,v);w>=0;w=nextadjvex(G,v,w))
        if(!visited[w])
            DFS(G,w);
}

void dfstraverse (Algraph & G,int (* visit)(int v))
{   
    int v;
    visitfunc=visit;
    for(v=0;v<G.vexnum;++v)
        visited[v]=0;
    for(v=0;v<G.vexnum;++v)
        if(!visited[v])
            DFS(G,v);
}

void main()
{
    int a;
    for(int m=0;m<3;m++)
    {   
        printf("请输入1,2,3来选择程序:\n");
        scanf("%d",&a);
        if(a==1)
           create(G);
        else
            if(a==2)
              put(G);
            else
                if(a==3)
                    dfstraverse (G,visit);
    }
}
搜索更多相关主题的帖子: null create include 
2013-12-20 20:48
这名字也占
Rank: 3Rank: 3
来 自:无名
等 级:论坛游侠
帖 子:30
专家分:142
注 册:2013-12-7
得分:10 
路过学习

路过%%%%%学习
2013-12-22 14:06



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-425461-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.277862 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved