1. 图的广度优先遍历

本实验实现邻接表表示下无向图的广度优先遍历。

程序的输入是图的顶点序列和边序列(顶点序列以*为结束标志，边序列以-1,-1为结束标志)。程序的输出为图的邻接表和广度优先遍历序列。例如：

程序输入为：
a
b
c
d
e
f
*
0,1
0,4
1,4
1,5
2,3
2,5
3,5
-1,-1

程序的输出为：
the ALGraph is
a 4 1
b 5 4 0
c 5 3
d 5 2
e 1 0
f 3 2 1
the Breadth-First-Seacrh list:aebfdc

解答：这道题真的糖丸辣，根据上百次的实验告诉我一个惊人的事实，这玩意竟然是dfs而不是他口口声声说的bfs，然后还卡了很久最后一个，经过测试得出结论，最后一个保密应该是是没有的情况（因为我出现了无效内存，我使用了最后末尾分开打印的方式，所以推测最后一个样例应该是没有边或者根本没有顶点）
总结：本题是DFS，注意输出格式避免最后样例出现无效内存和格式错误的情况
下附上源代码（请修改后使用）

 

#include <iostream>
#include <cstdio>
#include <vector>
#include <unordered_map>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

void BFS(vector<char> nodes, unordered_map<int, vector<int>> mp)
{
    queue<int> q;
    q.push(0);
    vector<bool> visited(nodes.size(), false);
    visited[0] = true;
    cout << "the Breadth-First-Seacrh list:";
    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        cout << nodes[node];
        for (int i = mp[node].size() - 1; i >= 0; i--)
        {
            if (!visited[mp[node][i]])
            {
                q.push(mp[node][i]);
                visited[mp[node][i]] = true;
            }
        }
    }
    cout << endl;
}

void DFS(int find, vector<bool> &visited, vector<char> &nodes, unordered_map<int, vector<int>> &mp)
{
    vector<int> next_nodes;
    if (!visited[find])
    {
        visited[find] = true;
        cout << nodes[find];
    }
    for (int i = mp[find].size() - 1; i >= 0; --i)
    {
        int neighbor = mp[find][i];
        if (!visited[neighbor])
        {
            next_nodes.push_back(neighbor);
            cout << nodes[neighbor];
            visited[neighbor] = true;
        }
    }
    for (int i = 0; i < next_nodes.size(); ++i)
    {
        DFS(next_nodes[i], visited, nodes, mp);
    }
}

void print_graph(vector<char> nodes, unordered_map<int, vector<int>> mp)
{
    cout << "the ALGraph is" << endl;
    for (int i = 0; i < nodes.size(); i++)
    {
        cout << nodes[i];
        for (int j = mp[i].size() - 1; j >= 0; j--)
        {
            cout << " " << mp[i][j];
        }
        cout << endl;
    }
}

int main()
{
    vector<char> nodes;
    unordered_map<int, vector<int>> mp;

    char n;
    while (cin >> n && n != '*')
    {
        nodes.push_back(n);
    }

    int a, b;
    while (scanf("%d,%d", &a, &b) == 2 && !(a == -1 && b == -1))
    {
        mp[a].push_back(b);
        mp[b].push_back(a);
    }

    print_graph(nodes, mp);

    cout << "the Breadth-First-Seacrh list:";
    vector<bool> visited(nodes.size(), false);
    for (int i = 0; i < nodes.size(); i++)
    {
        if (!visited[i])
        {
            DFS(i, visited, nodes, mp);
        }
    }
    cout << endl;

    // BFS(nodes, mp);
    return 0;
}