图遍历 [英] Graph traversal

问题描述

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#define MAX_VRTEX_NUM 20

struct EdgeNode{
	int adjvex;
	struct EdgeNode *next;
};
typedef struct EdgeNode **adjlist;

void Initialization(adjlist &GL,int n);
void Create(adjlist &GL,int n,int m);
void DFS(adjlist GL,int *visited,int i,int n);
void Check(int n,int &i,int &j);

void Initialization(adjlist &GL,int n)
{
	GL=(EdgeNode **)malloc(sizeof(2*n));
	for(int i=1;i<=n;i++)
	{
		GL[i]=NULL;
	}
}

void Create(adjlist &GL,int n,int m)
{
	int i,j,k,e;
	printf("Enter the total number of edges:");
	scanf("%d",&e);
	if(m==0)
	{
		for(k=1;k<=e;k++)
		{
			printf("Input the No.%d edge''s startpoint and endpoint:\n",k);
			scanf("%d %d",&i,&j);
			char temp=getchar();
			Check(n,i,j);
			struct EdgeNode *p;
		    p=(struct EdgeNode *)malloc(sizeof(struct EdgeNode));
		    p->adjvex=j;
		    p->next=GL[i];
		    GL[i]=p;
	        p=(struct EdgeNode *)malloc(sizeof(struct EdgeNode));
		    p->adjvex=i;
		    p->next=GL[j];
		    GL[j]=p;
		}
		printf("\n==============\n");
		printf("Adjacency-list representetion:\n");
		for(i=1;i<=n;i++)
		{
			struct EdgeNode *p=GL[i];
			printf("%d |V%d",i-1,i);
			for(p=GL[i];p!=NULL;p=p->next)
			{
				printf("|-|->|%d",p->adjvex);
			}
			printf("|^|");
			printf("\n");
		}
	}
	else 
		if(m==1)
		{
			for(k=1;k<=e;k++)
			{
				printf("Input the No.%d edge''s startpoint and endpoint:\n",k);
				scanf("%d %d",&i,&j);
				Check(n,i,j);
				struct EdgeNode *p;
				p=(struct EdgeNode *)malloc(sizeof(struct EdgeNode));
				p->adjvex=j;
				p->next=GL[i];
				GL[i]=p;
			}
         printf("Adjacency-list representetion:\n");
         for(i=1;i<=n;i++)
		 {
			struct EdgeNode *p=GL[i];
			printf("%d |V%d",i-1,i);
			for(p=GL[i];p!=NULL;p=p->next)
			{
				printf("|-|->|%d",p->adjvex);
			}
			printf("|^|");
			printf("\n");
		 }
		}
}

void DFS(adjlist GL,int *visited,int i,int n)
{
	printf("%d ",i);
	visited[i]=1;
	struct EdgeNode *p=GL[i];
	while(p!=NULL)
	{
		int j=p->adjvex;
		if(!visited[j])
			DFS(GL,visited,j,n);
		p=p->next; 
	}
}

void Check(int n,int &i,int &j)
{
	while(true)
	{
		if(i<=0||i>n||j<=0||j>n)
			printf("Entry error, please re-enter!\n");
		else
			return;
		scanf("%d %d",&i,&j);
	}
}

void main()
{
	int i,n,m;
	printf("==============\n");
	printf("Input graph vertices:");
	scanf("%d",&n);
	printf("Undirected graph:input 0 OR Digraph:input 1:");
	scanf("%d",&m);

    int visited[MAX_VRTEX_NUM];
	adjlist gl;
	Initialization(gl,n);
    Create(gl,n,m);
    printf("==============\n");
	printf("Depth-first search:\n");
	for(i=1;i<=n;i++)
		visited[i]=0;
	DFS(gl,visited,1,n);
}

该程序的主要目的是使用深度优先"搜索输出图的序列.当我在Visual c ++ 2008上调试它时，没有错误.但是它不能正常运行.输入第一条边的起点和终点后，它将停止运行.我找不到解决方法.:confused:而且，我是一个初学者.我刚刚开始学习图.请问你能帮帮我吗?谢谢. :)

The main purpose of the program is to output the sequence of a graph with the Depth-first search. When I debugged it on visual c++ 2008, there is no error. But it can''t run properly. It stops running after I input the first edge''s startpoint and endpoint. I can''t find the solution.:confused: What''s more, I am a beginner. I just started learning the Graph. Could you help me, please? Thanks. :)

推荐答案

几件事:
*给出变量和函数名称的含义.像i，n，m，i，j，k，e这样的东西可以调试整个PITA.
*有很多malloc，而没有任何free.永远记得自己清理.
*在主程序中调用DFS后，程序不会等待任何退出.如果您是从命令行运行的，那应该没问题，但是如果您使用的是Visual Studio，那么在您进行更改以查看被printf编辑的任何内容之前，将关闭命令窗口.
*在DFS中有if (m == 0) else { if (m == 1) }，当m是其他东西时会发生什么?
*在Initialization中，在将n用于malloc之前，请确保它不是一个疯狂的庞大数字是明智的.输入2147483647，看看会发生什么.
*为什么仍然要分配sizeof(2*n)?那不是sizeof(EdgeNode *) * n吗?

A couple things:
* give variables and functions names with meaning. Things like i,n,m,i,j,k,e make debugging a total PITA.
* there are a lot of mallocs without any frees. Always remember to cleanup after yourself.
* after the call to DFS in main the program doesn''t wait for anything to exit. If you''re running from the command line this shouldn''t be a problem but if you''re using Visual Studio then the command window will close before you get a change to look at anything that is printfed.
* in DFS there''s if (m == 0) else { if (m == 1) }, what happens when m is something else?
* in Initialization it would be wise to make sure n isn''t some crazy huge number before you use it for mallocing. Input 2147483647 for it and see what happens.
* why allocate sizeof(2*n) anyway? Shouldn''t that be sizeof(EdgeNode *) * n?

这篇关于图遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！