用C语言实现 图的邻接表和邻接矩阵数据结构的定义、创建；图的深度优先遍历、广度优先遍历。

Question

用C语言，百度到的程序运行不正确，最好亲自运行一下再贴过来，求大神相助！

Answer 1

/*
                程序1：邻接表的dfs,bfs
                其中n是点的个数,m是边的个数,你需要输入m条有向边，如果要无向只需要反过来多加一遍即可。
*/
#include <stdio.h>
#include <string.h>
#define MAXM 100000
#define MAXN 10000
int next[MAXM],first[MAXN],en[MAXM],n,m,flag[MAXN],pd,dl[MAXN],head,tail;

void input_data()
{
                scanf("%d%d",&n,&m);
                int i,x,y;
                for (i=1;i<=m;i++)
                                {
                                                int x,y;
                                                scanf("%d%d",&x,&y);
                                                next[i]=first[x];
                                                first[x]=i;
                                                en[i]=y;
                                }
}

void pre()
{
                memset(flag,0,sizeof(flag));
                pd=0;
}

void dfs(int x)
{
                flag[x]=1;
                if (!pd)
                                {
                                                pd=1;
                                                printf("%d",x);
                                }else
                                                printf(" %d",x);
                int p=first[x];
                while (p!=0)
                                {
                                                int y=en[p];
                                                if (!flag[y])   dfs(y);
                                                p=next[p];
                                }
}

void bfs(int k)
{
                head=0;tail=1;
                flag[k]=1;dl[1]=k;
                while (head<tail)
                                {
                                                int x=dl[++head];
                                                if (!pd)
                                                                {
                                                                                pd=1;
                                                                                printf("%d",x);
                                                                }else printf(" %d",x);
                                                int p=first[x];
                                                while (p!=0)
                                                                {
                                                                                int y=en[p];
                                                                                if (!flag[y])
                                                                                                {
                                                                                                                flag[y]=1;
                                                                                                                dl[++tail]=y;
                                                                                                }
                                                                                p=next[p];
                                                                }
                                }
}

int main()
{
                input_data();//读入图信息。
                pre();//初始化
                printf("图的深度优先遍历结果:");
                int i;
                for (i=1;i<=n;i++)//对整张图进行dfs; 加这个for主要是为了防止不多个子图的情况
                                if (!flag[i])
                                                dfs(i);
                printf("\n-------------------------------------------------------------\n");
                pre();//初始化
                printf("图的广度优先遍历结果为:");
                for (i=1;i<=n;i++)
                                if (!flag[i])
                                                bfs(i);
                printf("\n----------------------end------------------------------------\n");
                return 0;
}

/*
                程序2:邻接矩阵
                图的广度优先遍历和深度优先遍历
*/
#include <stdio.h>
#include <string.h>
#define MAXN 1000

int n,m,w[MAXN][MAXN],flag[MAXN],pd,dl[MAXN];

void input_data()
{
                scanf("%d%d",&n,&m);
                int i;
                for (i=1;i<=m;i++)
                                {
                                                int x,y;
                                                scanf("%d%d",&x,&y);
                                                w[x][0]++;
                                                w[x][w[x][0]]=y;
                                }
}

void pre()
{
                memset(flag,0,sizeof(flag));
                pd=0;
}

void dfs(int x)
{
                flag[x]=1;
                if (!pd)
                                {
                                                pd=1;
                                                printf("%d",x);
                                }else printf(" %d",x);
                int i;
                for (i=1;i<=w[x][0];i++)
                                {
                                                int y=w[x][i];
                                                if (!flag[y])   dfs(y);
                                }
}

void bfs(int t)
{
                int head=0,tail=1;
                dl[1]=t;flag[t]=1;
                while (head<tail)
                {
                                int x=dl[++head];
                                if (!pd)
                                                {
                                                                pd=1;
                                                                printf("%d",x);
                                                }else printf(" %d",x);
                                int i;
                                for (i=1;i<=w[x][0];i++)
                                                {
                                                                int y=w[x][i];
                                                                if (!flag[y])
                                                                                {
                                                                                                flag[y]=1;
                                                                                                dl[++tail]=y;
                                                                                }
                                                }
                }
}

int main()
{
                input_data();
                printf("图的深度优先遍历结果:");
                pre();
                int i;
                for (i=1;i<=n;i++)
                                if (!flag[i])
                                                dfs(i);
                printf("\n---------------------------------------------------------------\n");
                printf("图的广度优先遍历结果:");
                pre();
                for (i=1;i<=n;i++)
                                if (!flag[i])
                                                bfs(i);
                printf("\n-----------------------------end--------------------------------\n");
                return 0;
}