1. 图的广度优先遍历

        当一道题的AC变成了找不同的时候，一切就开始失去意义。

        到底是谁？把Search写成Seacrh，害我一直找不同。

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

程序的输入是图的顶点序列和边序列(顶点序列以*为结束标志，边序列以-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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Node
{
    char data;
    bool visited;
    vector<int> edges;
};
void bfs(vector<Node> &nodeList, int startIndex)
{
    queue<int> nodeQueue;
    nodeQueue.push(startIndex);
    nodeList[startIndex].visited = true;
    while (!nodeQueue.empty())
    {
        int currentIndex = nodeQueue.front();
        nodeQueue.pop();
        cout << nodeList[currentIndex].data;
        for (int i = nodeList[currentIndex].edges.size() - 1; i >= 0; --i)
        {
            int nextIndex = nodeList[currentIndex].edges[i];
            if (!nodeList[nextIndex].visited)
            {
                nodeQueue.push(nextIndex);
                nodeList[nextIndex].visited = true;
            }
        }
    }
}

int main()
{
    vector<Node> nodeList;
    char ch;
    int indexA, indexB;
    while (cin >> ch && ch != '*')
    {
        Node node{ch, false, {}};
        nodeList.push_back(node);
    }
    while (cin >> indexA >> ch >> indexB && !(indexA == -1 && indexB == -1))
    {
        nodeList[indexA].edges.push_back(indexB);
        nodeList[indexB].edges.push_back(indexA);
    }
    cout << "the ALGraph is\n";
    for (const Node &node : nodeList)
    {
        cout << node.data;
        for (int i = node.edges.size() - 1; i >= 0; --i)
            cout << " " << node.edges[i];
        cout << endl;
    }
    cout << "the Breadth-First-Seacrh list:";
    for (int i = 0; i < nodeList.size(); ++i)
        if (!nodeList[i].visited)
            bfs(nodeList, i);
    cout << endl;
}