问题描述 

【问题描述】

给定一个无向图，创建图的邻接矩阵表示，并对无向图进行深度和广度遍历。

【输入形式】

输入图的顶点序列（以#结束）和图的边（以输入-1，-1作为结束）。

ABCDEFGH#

0,1

0,2

0,5

1,3

1,4

2,5

2,6

3,7

4,7

-1,-1

输入遍历的起始顶点序号，如输入2（表示从顶点C出发遍历）。

【输出形式】

输出图的邻接矩阵表示；（邻接矩阵的每个元素之间以空格分隔）

输出从起始顶点出发的深度和广度遍历序列。

【样例输入】

ABCDEFGH#

0,1

0,2

0,5

1,3

1,4

2,5

2,6

3,7

4,7

-1,-1

2

【样例输出】

graph:

0 1 1 0 0 1 0 0

1 0 0 1 1 0 0 0

1 0 0 0 0 1 1 0

0 1 0 0 0 0 0 1

0 1 0 0 0 0 0 1

1 0 1 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 1 1 0 0 0

dfs:CABDHEFG

bfs:CAFGBDEH

程序设计 

#include
#include

#define N 20
#define M 20
#define MAX 100

typedef char VexType;
typedef int ElemType;

typedef struct
{
    int vexnum,arcnum;
    VexType vexs[N];
    int arcs[N][N];
}MGraph;

typedef struct
{
    ElemType data[MAX];
    int front;
    int rear;
}SqQueue;

void createMGraph(MGraph *g)
{
    int i=0,j;
    g->vexnum=0;
    g->arcnum=0;
    scanf("%c",&g->vexs[i]);
    while(g->vexs[i]!='#')
    {
        i++;
        scanf("%c",&g->vexs[i]);
        g->vexnum++;
    }
    
    
    for(i=0;ivexnum;i++)
       for(j=0;jvexnum;j++)
          g->arcs[i][j]=0;
    
    scanf("%d,%d",&i,&j);
    while(i!=-1&&j!=-1)
    {
        g->arcs[i][j]=1;
        g->arcs[j][i]=1;
        g->arcnum++;
        scanf("%d,%d",&i,&j);
    }
    printf("graph:\n");
    for(i=0;ivexnum;i++)
    {
        for(j=0;jvexnum;j++)
        {
            printf("%d ",g->arcs[i][j]);
        }
        printf("\n");
    }
}

int visited1[N];
int visited2[M];

void DFS(int i,MGraph *g)
{
    int j;
    printf("%c",g->vexs[i]);
    visited1[i]=1;
    for(j=0;jvexnum;j++)
        if((g->arcs[i][j]==1)&&(!visited1[j]))
            DFS(j,g);
}

void BFS(int k, MGraph *g)
{
int i,j;
    SqQueue qlist,*q;
    q=&qlist;
    q->rear=0;
    q->front=0;
    printf("%c",g->vexs[k]);
    visited2[k]=1;
    q->data[q->rear]=k;
    q->rear=(q->rear+1)%MAX;
    while(q->rear!=q->front)
    {
        i=q->data[q->front];
        q->front=(q->front+1)%MAX;
        for(j=0;jvexnum;j++)
            if((g->arcs[i][j]==1)&&(!visited2[j]))
        {
            printf("%c",g->vexs[j]);
            visited2[j]=1;
            q->data[q->rear]=j;
            q->rear=(q->rear+1)%MAX;
        }
    }
}

int main()
{
    int x;
    MGraph p;
    createMGraph(&p);
    scanf("%d",&x);
    printf("dfs:");
    DFS(x,&p);
    printf("\n");
    printf("bfs:");
    BFS(x,&p);
    return 0;
}