MousE0910 - 4 months ago 26

C++ Question

I'm working on a simple programming assignment for my studies and I've encountered a problem. The assignment has a predefined header which cannot be modified, so I have to use the structures that are set, making the problem more complicated than it should be.

I need to implement a function that returns a vector of all vertices reachable from the start vertex. That would be a simple task if I could use a more complex structure for it, but the whole graph is represented as a vector of vectors, leaving me stumped with how to do it. Any help would be greatly appreciated.

The graph structure means that for example graph that's

`{{1,2,3}, {3}, {3}, {}}`

`#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);

I've tried a kind of naive brute force approach but it doesn't work.

`#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

The frontier starts out with a single node. You take a node from the frontier (*if you need cycle detection*: and add it to a set of visited nodes). Perform a function on the node. Then take all the nodes that are directly reachable from that node, and add them to the frontier (*if you need cycle detection*: unless the node has been visited before). Continue until no more nodes left.

Depending on how you "add" nodes to the frontier and how you "take a node" from the frontier this is a description of a whole class of search strategies.

A queue (adding at the end, take from front) will give you a BFS, a stack (adding on top, take from top) will give you a DFS.

"Perform a function" would in your case be "add it to the set of reachable nodes".