2 liuxinyancom liuxinyancom 于 2013.12.04 17:23 提问

哪位好心人帮我看下代码吧,深度遍历搜索图的,有点长,麻烦看下吧

//深度遍历搜索图
#include
#include
#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;ivexnum;i++)

    if(G->vertex[i].data==v)
        return i;
    else
        return 0;

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

void TraverseGraph(AdjList *G)
{
int vi=0;//没访问过的置0,访问过的置1;
for(vi=0;vivexnum;vi++)
visited[vi]=0;
for(vi=0;vivexnum;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;

}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!