能否用广度优先查找无向图所有路径

Question

问题遇到的现象和发生背景

BFS 搜索无向图 两点之间的所有路径

#include <iostream>
#include <vector>
#include <list>
#include <queue>

class Graph{
private:
    int num_vertex;
    std::vector< std::list<int> > AdjList;
    int *color,             // 0:白色, 1:灰色, 2:黑色
        *distance,          // 0:起點, 無限大:從起點走不到的vertex
        *predecessor;       // -1:沒有predecessor, 表示為起點vertex
public:
    Graph():num_vertex(0){};           // default constructor
    Graph(int N):num_vertex(N){        // constructor with input: number of vertex
        // initialize Adjacency List
        AdjList.resize(num_vertex);
    };
    void AddEdgeList(int from, int to);
    void BFS(int Start);
};

void Graph::AddEdgeList(int from, int to){
    AdjList[from].push_back(to);
}

void Graph::BFS(int Start){

    color = new int[num_vertex];
    predecessor = new int[num_vertex];
    distance = new int[num_vertex];

    for (int i = 0; i < num_vertex; i++) {  // 初始化，如圖二(b)
        color[i] = 0;                       // 0:白色;
        predecessor[i] = -1;                // -1表示沒有predecessor
        distance[i] = num_vertex+1;         // num_vertex個vertex, 
    }                                       // 最長距離 distance = num_vertex -1條edge

    std::queue<int> q;
    int i = Start;

    for (int j = 0; j < num_vertex; j++) {  // j從0數到num_vertex-1, 因此j會走過graph中所有vertex
        if (color[i] == 0) {                // 第一次i會是起點vertex, 如圖二(c)
            color[i] = 1;                   // 1:灰色
            distance[i] = 0;                // 每一個connected component的起點之距離設成0
            predecessor[i] = -1;            // 每一個connected component的起點沒有predecessor
            q.push(i);
            while (!q.empty()) {
                int u = q.front();                  // u 為新的搜尋起點
                for (std::list<int>::iterator itr = AdjList[u].begin();        // for loop 太長
                     itr != AdjList[u].end(); itr++) {                         // 分成兩段
                    if (color[*itr] == 0) {                // 若被「找到」的vertex是白色
                        color[*itr] = 1;                   // 塗成灰色, 表示已經被「找到」
                        distance[*itr] = distance[u] + 1;  // 距離是predecessor之距離加一
                        predecessor[*itr] = u;             // 更新被「找到」的vertex的predecessor
                        q.push(*itr);                      // 把vertex推進queue
                    }
                }
                q.pop();        // 把u移出queue
                color[u] = 2;   // 並且把u塗成黑色
            }
        }
        // 若一次回圈沒有把所有vertex走過, 表示graph有多個connected component
        // 就把i另成j, 繼續檢查graph中的其他vertex是否仍是白色, 若是, 重複while loop
        i = j;
    }
}

int main(){
    Graph g1(9);    
    // 建立出圖二(a)的Adjacency List
    g1.AddEdgeList(0, 1);g1.AddEdgeList(0, 2);g1.AddEdgeList(0, 3);
    g1.AddEdgeList(1, 0);g1.AddEdgeList(1, 4);
    g1.AddEdgeList(2, 0);g1.AddEdgeList(2, 4);g1.AddEdgeList(2, 5);g1.AddEdgeList(2, 6);g1.AddEdgeList(2, 7);
    g1.AddEdgeList(3, 0);g1.AddEdgeList(3, 7);
    g1.AddEdgeList(4, 1);g1.AddEdgeList(4, 2);g1.AddEdgeList(4, 5);
    g1.AddEdgeList(5, 2);g1.AddEdgeList(5, 4);g1.AddEdgeList(5, 8);
    g1.AddEdgeList(6, 2);g1.AddEdgeList(6, 7);g1.AddEdgeList(6, 8);
    g1.AddEdgeList(7, 2);g1.AddEdgeList(7, 3);g1.AddEdgeList(7, 6);
    g1.AddEdgeList(8, 5);g1.AddEdgeList(8, 6);

    g1.BFS(0);    

    return 0;
}

用代码块功能插入代码，请勿粘贴截图

运行结果及报错内容

无法查找所有路径，部分路径由于着色原因，无法被找到。如何解决？

我的解答思路和尝试过的方法

能否使用BFS，还是必须要用DFS。请提供一个BFS可行的代码。

我想要达到的结果

查找无向图的，所有路径。

Answer 1

// 无向图的邻接矩阵表示法实现深搜
#include <vector>
#include <iostream>
using namespace std;
#define MAX 5 //节点数量
char node[MAX]; //存储节点的容器
int node_edge[MAX][MAX]; //邻接矩阵
vector<char> dfs; //算法实现的辅助栈
bool visited[MAX]; //记录已经访问过的节点

void InPut() //输入邻接矩阵
{
    //依次输入节点
    cout << "Input nodes ：" << endl;
    for (int i = 0; i < MAX; i++)
    {
        cin >> node[i];
    }
    // 1代表有边，0代表无边
    cout << "Input edges：" << endl;
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            cin >> node_edge[i][j];
        }
    }
    //将访问标记数组初始化
    memset(visited, false, MAX);
}
void DFS()
{
    //先取出第一个顶点
    char n = node[0];
    //入栈
    dfs.push_back(n); 
    while (!dfs.empty())
    {
        //获取栈顶元素
        char ch = dfs.back();
        //获取栈顶元素坐标
        int index;
        for (index = 0; index < MAX; index++)
        {
            if (node[index] == ch)
            {
                break;
            }
        }
        //判断是否已经被访问过
           if (visited[index] == true)
        {
            //将这个节点的最近的一个没有被访问过的节点入栈
            int i;
            for (i = 0; i < MAX; i++)
            {
                if (node_edge[index][i] == 1 && visited[i] == false)
                {
                    //入栈
                    dfs.push_back(node[i]);
                    break;
                }
            }
            if (i == MAX)
            {
                //所有邻接点都访问过了，出栈
                dfs.pop_back();
            }
            continue;
        }
        //访问栈顶元素
        cout << ch << " ";
        //标记已经被访问
        visited[index] = true;
    }
}
int main()
{
    InPut();
    DFS();
    return 0;
}