图的两种遍历方法


#include <iostream>
#include <queue>
#include <string.h>
#include <cstdio>
#include <stack>
#include <stdlib.h>
#define MAX 100
using namespace std;

typedef struct
{
    int n, e;
    //标记顶点是否被访问过
    int c[100][100];
} Graph;

int visited[100] = {0};
void CreatGraph(Graph &G)
{
    cin >> G.n;
    cin >> G.e;

    for (int i = 1; i <= G.n; ++i)
        for (int j = 1; j <= G.n; ++j)
            G.c[i][j] = 0;

    for (int i = 1; i <= G.e; ++i)
    {
        int p, q;
        cin >> p >> q;

        G.c[p][q] = 1; // p指向q
        G.c[q][p] = 1; // q指向p，这样表示无向图
    }
}
void ShowGraph(Graph &G)
{
    for (int i = 1; i <= G.n; ++i)
    {
        for (int j = 1; j <= G.n; ++j)
            printf("%4d", G.c[i][j]);
        printf("\n\n");
    }
    cout << endl;
}

void DFS(Graph &G, int start) //深度优先搜索
{

    printf("%d ", start); //访问结点v
    visited[start] = 1;
    for (int i = 1; i <= G.n; i++) //访问与v相邻的未被访问过的结点
    {
        if (G.c[start][i] != 0 && visited[i] == 0)
        {
            DFS(G, i);
        }
    }
}
void BFS(Graph &G, int start)
{
    int visited[100] = {0};
    queue<int> Q;
    Q.push(start);
    visited[start] = 1;
    while (!Q.empty())
    {
        int front = Q.front();
        cout << front << " ";
        Q.pop();
        for (int i = 1; i <= G.n; i++)
        {
            if (!visited[i] && (G.c[front][i] == 1))
            {
                visited[i] = 1;
                Q.push(i);
            }
        }
    }
}

int main()
{
    Graph G;
    freopen("input.txt", "r", stdin);
    CreatGraph(G); //输入图中的信息并转化为邻接矩阵
    ShowGraph(G);  //输出邻接矩阵

    cout << "深度优先遍历结果:";
    DFS(G, 1);
    cout << endl;

    cout << "广度优先遍历结果:";
    BFS(G, 1);
    cout << endl;
}

input.txt