由向量的向量构成的有向图中的可达顶点

Question

我正在为我的学习做一个简单的编程作业，我遇到了一个问题。作业有一个预定义的header，无法修改，所以我必须使用设置的结构，使问题比应该的更复杂。

我需要实现一个函数，returns 一个从起始顶点可达的所有顶点的向量。如果我可以为它使用更复杂的结构，那将是一项简单的任务，但整个图表示为向量的向量，让我不知道如何去做。任何帮助将不胜感激。

图形结构意味着例如{{1,2,3}, {3}, {3}, {}}的图形意味着顶点0通向顶点1、2、3；顶点 1 通向 3，顶点 2 通向 3，顶点 3 通向任何地方。

graph.hpp

#include <vector>
#include <algorithm>

/*
 * Struct representing graph, that is, vertices and edges between the vertices.
 * Vertices are identified with indices, where 0 stands for 1st added vertex,
 * 1 stands for 2nd added vertex, 2 stands for 3rd added vertex, etc...
 *
 * The edges between vertices are directed.
 */
struct graph {
    std::vector<std::vector<int>> connections;
};

// Other functions manipulating the graph here

/*
 * Return vertices that are reachable from given vertex.
 * That is, the vertex itself,
            all vertices connected to the given vertex,
            all vertices connected to these vertices,
            etc...
 *
 * Can only be called with existing vertex.
 */
std::vector<int> reachable_vertices(const graph& g, int vertex);

我试过一种天真的暴力方法，但它不起作用。

graph.cpp

#include "graph.hpp"

// Other functions manipulating the graph here

std::vector<int> reachable_vertices(const graph& g, int vertex) {
    if (g.connections.size() < vertex) {
        return{};
    }
    std::vector<int> reachables;
    for (auto vert : g.connections[vertex]) {
        if (vert > vertex) {
            reachables = reachable_vertices(g, vert);
        }
    }
    reachables.push_back(vertex);
    std::sort(reachables.begin(), reachables.end());
    reachables.erase(std::unique(reachables.begin(), reachables.end()), reachables.end());
    return reachables;
}

Answer 1

边界从一个节点开始。您从边界取一个节点（如果您需要循环检测：并将其添加到一组已访问节点中）。在节点上执行功能。然后取出所有从该节点直接可达的节点，并将它们添加到边界（如果需要循环检测：除非该节点之前被访问过）。继续，直到没有更多节点离开。

根据您 "add" 如何到达边界以及您如何 "take a node" 从边界出发，这是对整个 class 搜索策略的描述。

一个队列（在末尾添加，从前面取）将给你一个 BFS，一个堆栈（在顶部添加，从顶部取）将给你一个 DFS。

"Perform a function" 在你的情况下会是 "add it to the set of reachable nodes".

由向量的向量构成的有向图中的可达顶点

Reachable vertices in directed graph made from vector of vectors

c++

graph

vector

vertices