| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
ADSL如何秒变专线,公网IP盒子了解一下千里之行 始于足下
共有 449 人关注过本帖
标题:深度遍历图,请问这个程序哪里出了问题呢?
只看楼主 加入收藏
liuxinyancom
Rank: 1
等 级:新手上路
帖 子:13
专家分:0
注 册:2013-10-16
结帖率:50%
  问题点数:0  回复次数:0   
深度遍历图,请问这个程序哪里出了问题呢?
//深度遍历搜索图
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 3
typedef enum {DG,DN,UDG,UDN} GraphKind;//图的类型
typedef int OtherInfo; //弧的信息,如权
typedef char VertexData;//图结点的内容为char
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode *nextarc;
    OtherInfo info;
}ArcNode;//弧结点
typedef struct VertexNode
{
    VertexData data;
    ArcNode *firstarc;

}VertexNode;//表头结点
typedef struct
{
    VertexNode vertex[MAX_VERTEX_NUM];
    int arcnum;
    int vexnum;
    GraphKind kind;
}AdjList;//邻接表(图)

int visited[MAX_VERTEX_NUM];//全局变量:访问标志数组
void CreateAdjList(AdjList *G);
int Locate(AdjList *G, char v);
void TraverseGraph(AdjList *G);
void DepthFirstSearch(AdjList*G,int v0);

void CreateAdjList(AdjList *G)//建立邻接表
{
   
    char v1;char v2;//v1,v2为一条弧上的两个端点,一个为起始端点,一个为尾端点
    ArcNode *s;
    int i,j,k;
    char ch;
    printf(" 输入图结点:");
    for(i=0;i<G->vexnum;i++)//表头结点初始化
    {
        
        
        scanf("%c",&ch);
        G->vertex[i].data=ch;
        G->vertex[i].firstarc=NULL;
        fflush(stdin);
        
        
    }
   

    for(k=0;k<G->arcnum;k++)
    {
        printf("输入连接弧端点值,如“A,B”");
        scanf("%c,%c",&v1 ,&v2 );
        //v1=getchar();
        //v2=getchar();
        
        i=Locate(G,v1);printf("%d",i);//定位v1在表头结点里的数组下标,即第几个
        j=Locate(G,v2);printf("#");
        s=(ArcNode*)malloc(sizeof(ArcNode));
        s->adjvex=j;
        s->nextarc=G->vertex[i].firstarc;
        G->vertex[i].firstarc=s;//头结点插入法
        s=(ArcNode*)malloc(sizeof(ArcNode));
        s->adjvex=i;
        s->nextarc=G->vertex[j].firstarc;
        G->vertex[j].firstarc=s;
    }
}
//定位,查找v1,v2的相应数组下标
int Locate(AdjList *G,char v)
{
    for(int i=0;i<G->vexnum;i++)
   
        if(G->vertex[i].data==v)
            return i;
        else
            return 0;

}
//深度优先搜索邻接表



void TraverseGraph(AdjList *G)
{
    int vi=0;//没访问过的置0,访问过的置1;
    for(vi=0;vi<G->vexnum;vi++)
        visited[vi]=0;
    for(vi=0;vi<G->vexnum;vi++)
        if(visited[vi]==0)
            DepthFirstSearch(G,vi);
}
void DepthFirstSearch(AdjList*G,int v0)//DFS
{
    ArcNode*p;
    printf("%c",v0);
    visited[v0]=1;//访问过后标志数组置为1;
    p=G->vertex[v0].firstarc;
    while(p!=NULL)
    {
        if(visited[p->adjvex]==0)
            DepthFirstSearch(G,p->adjvex);
        p=p->nextarc;
    }
}

int main()
{
    AdjList * G;

    G=(AdjList*)malloc(sizeof(AdjList));
    printf("输入图结点数目,弧数目,如“4,3”\n");
    scanf("%d,%d",&G->vexnum,&G->arcnum );
   
    CreateAdjList(G);
    TraverseGraph(G);
    free(G);
    return 0;

}
搜索更多相关主题的帖子: 信息 include 
2013-11-27 17:26







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

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