带权无向图中如何使用BFS和DFS实现遍历至指定节点后终止？

原有代码核心问题 #

• 邻接表遍历逻辑错误：原有BFS、DFS函数中直接将邻接表数组下标作为节点编号使用，导致遍历逻辑完全不符合预期
• 缺少目标节点终止逻辑：没有设计目标节点入参，也没有添加到达目标节点后终止遍历的判断

修正后代码 #

#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "algorithm"

using namespace std;

typedef pair<int , int> Pair;

struct Edge{
    int src, dest, weight;
};

class Graph{
public:
    vector<vector<Pair>> adjacencyList;
    Graph(vector<Edge> const &edges, int N)
    {
       adjacencyList.resize(N);
       for(auto &edge: edges)
       {
           int src = edge.src;
           int dest = edge.dest;
           int weight = edge.weight;
           adjacencyList[src].push_back(make_pair(dest,weight));
           adjacencyList[dest].push_back(make_pair(src,weight));
       }
    }
};

// 新增target参数作为终止节点
void BFS(Graph const &graph, int src, int target, vector<bool> &discovered)
{
    queue<int> q;
    discovered[src] = true;
    q.push(src);
    while(!q.empty())
    {
        src = q.front();
        q.pop();
        cout<<src<<" ";
        // 到达目标节点直接终止遍历
        if(src == target) {
            return;
        }
        for(int i = 0; i < graph.adjacencyList[src].size() ;i++)
        {
            // 正确获取邻接节点编号
            int adj_node = graph.adjacencyList[src][i].first;
            if(!discovered[adj_node])
            {
                discovered[adj_node] = true;
                q.push(adj_node);
            }
        }
    }
}

// 新增target参数作为终止节点
void DFS(Graph const &graph, int src, int target, vector<bool> &discovered)
{
    stack<int> stack;
    stack.push(src);
    while(!stack.empty()){
        src = stack.top();
        stack.pop();
        if(discovered[src])
        {
            continue;
        }
        discovered[src] = true;
        cout<<src<< " ";
        // 到达目标节点直接终止遍历
        if(src == target) {
            return;
        }
        // 倒序遍历保证遍历顺序和递归DFS一致，不需要可改为正向遍历
        for(auto it = graph.adjacencyList[src].rbegin(); it != graph.adjacencyList[src].rend(); ++it)
        {
            int adj_node = it->first;
            if(!discovered[adj_node])
            {
                stack.push(adj_node);
            }
        }
    }
}

void printGraph(Graph const &graph, int N)
{
    for (int i = 0; i < N; ++i) {
        for(Pair v: graph.adjacencyList[i])
        {
            cout<<"("<<i<<" , "<<v.first<<" , "<<v.second<<") ";
        }
        cout<<endl;
    }
}

int main()
{
    vector<Edge> edges =
            {
                    // `(x, y, w)` —> edge from `x` to `y` having weight `w`
                    {0,1,0}, {0,2,0}, {0,3,0},
                    {1, 2,0}, {2,4,0}, {3,3,0}, {4,4,0}
            };
    int N = 5;
    Graph graph(edges,N);
    int start, target;
    cout << "请输入源节点编号（有效范围0~4）：";
    cin >> start;
    cout << "请输入目标节点编号（有效范围0~4）：";
    cin >> target;
    if(start <0 || start >=N || target <0 || target >=N) {
        cout << "输入节点编号非法" << endl;
        return 0;
    }
    vector<bool> discovered(N, false);
    cout << "BFS遍历结果（到目标节点为止）：";
    BFS(graph, start, target, discovered);
    cout<<endl;
    vector<bool> discovered2(N, false);
    cout << "DFS遍历结果（到目标节点为止）：";
    DFS(graph, start, target, discovered2);
    cout<<endl;
    cout << "图的邻接表结构：" << endl;
    printGraph(graph, N);
    return 0;
}

效果说明 #

输入源节点为0、目标节点为4时，输出示例如下：

请输入源节点编号（有效范围0~4）：0
请输入目标节点编号（有效范围0~4）：4
BFS遍历结果（到目标节点为止）：0 1 2 3 4 
DFS遍历结果（到目标节点为止）：0 3 2 4 
图的邻接表结构：
(0 , 1 , 0) (0 , 2 , 0) (0 , 3 , 0) 
(1 , 0 , 0) (1 , 2 , 0) 
(2 , 0 , 0) (2 , 1 , 0) (2 , 4 , 0) 
(3 , 0 , 0) (3 , 3 , 0) (3 , 3 , 0) 
(4 , 2 , 0) (4 , 4 , 0) (4 , 4 , 0) 

内容的提问来源于stack exchange，提问作者Danyal Sufyan