博客

Problem Description

给出一个无向图的各个点之间的邻接关系，要求采用邻接表对图进行存储，并输出遍历序列。

Input

有多组数据，每组数据第一行有两个整数n和m(0<n,m<100)，n表示是有n个点（记为1~n）形成的图，接下来有m行数据，每一行有两个整数（表示点的序号，从1开始），说明这两点之间有一条边，要求采用头插法建立边表。

Output

对于每组数据，分别输出从序号为1的点开始的深度和广度优先搜索序列，每个序列分别占一行，每个数之后有一个空格。

要求在选取下一未被访问的邻接点时，按边表中邻接点的存储顺序进行选取。

Sample Input

8 9
1 2
1 3
2 4
2 5
3 6
3 7
4 5
4 8
6 7

Sample Output

1 3 7 6 2 5 4 8
1 3 2 7 6 5 4 8

#include <iostream>
#include <stdlib.h>
#define maxvex 20
#include<stdio.h>
using namespace std;

typedef struct {
    int adjvex;

} ArcCell[maxvex][maxvex];

typedef struct {
    ArcCell arc;
    int vertexnum,arcnum;
    char vex[maxvex];
} MatrixGraph;

struct ArcNode {
    int adjvex;
    ArcNode* next;
};
typedef struct Edge {
    char vertex;
    int vex;
    ArcNode *firstedge;
} EdgeList[maxvex];

typedef struct {
    EdgeList adjlist;
    int vertexnum,arcnum;
} GraphList;


bool visited[maxvex];

void init() {
    for(int i=0; i<maxvex; i++) {
        visited[i]=false;
    }

}

void CreatList(GraphList &G,int n,int e) {
    G.arcnum=e;
    G.vertexnum=n;
    for(int i=0; i<G.vertexnum; i++) {
        //    cin>>G.adjlist[i].vertex;
        G.adjlist[i].firstedge=NULL;
    }
    for(int i=0; i<G.arcnum; i++) {
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        ArcNode* p=new ArcNode;
        p->adjvex=b;
        p->next=G.adjlist[a].firstedge;
        G.adjlist[a].firstedge=p;
        p=new ArcNode;
        p->adjvex=a;
        p->next=G.adjlist[b].firstedge;
        G.adjlist[b].firstedge=p;
    }

}




void DFSTraverse(GraphList g,int v) {
    cout<<(v+1)<<" ";
    visited[v]=true;
//for(int i=0;i<g.vertexnum;i++){
    ArcNode* p=g.adjlist[v].firstedge;
    while(p) {
        if(!visited[p->adjvex]) DFSTraverse(g,p->adjvex);
        p=p->next;
    }


}

void BFSTraverse(GraphList g,int v) {
    int rear=-1;
    int front =-1;
    int Q[maxvex];
    cout<<(v+1)<<" ";
    visited[v]=true;
    Q[++rear]=v;
    while(rear!=front) {
        v=Q[++front];
        ArcNode* p=g.adjlist[v].firstedge;
        while(p) {
            if(!visited[p->adjvex]) {
                cout<<(p->adjvex+1)<<" ";
                visited[p->adjvex]=true;
                Q[++rear]=p->adjvex;
            }
            p=p->next;
        }
    }
}


int main() {
  
    int n,e;

    while(cin>>n>>e) {
        GraphList g;
        CreatList(g,n,e);
        init();
        DFSTraverse(g,0);
        cout<<endl;
        init();
        BFSTraverse(g,0);
        cout<<endl;

    }
    return 0;
}