如何以连接的方式穿越连接的节点网络？

Question

我的数据结构可以可视化为连接的网络，如下所示：

​

​

我相信(在没有证据的情况下)应该能够遍历所有节点，总是从一个节点移动到一个连接的节点(当然，回溯是必需的和允许的--就像您对树结构所做的那样)。该怎么做呢？

数据结构可以用伪代码写成如下：

node[N] nodes; // the network as an array of N nodes

class node {
  List<pt_to_node> friend_nodes;  // a list of pointers to connected nodes
}

Answer 1

您可以简单地使用堆栈实现深度优先搜索，或者使用队列实现广度优先搜索。

例如：

假设我们将从Node 1开始，

#include <vector>
#include <list>
#include <vector>
using namespace std;

class Graph
{
public:
    int vert; //number of vertices
    vector<list<int>> adj;

    Graph(int _v)
    {
        adj.resize(_v);
        vert = _v;
    }

    void addEdge(int v, int key)
    {
        adj[v].push_back(key);
        adj[key].push_back(v); // comment out if undirected
    }

    void bfs(int start);
    void dfs(int start);
};



void Graph::bfs(int start)
{

    vector<bool> visited(vert,false);

    list<int> queue;

    visited[start] = true; // visit the first node
    queue.push_back(start);


    while (!queue.empty())
    {
        start = queue.front();
        cout << start << " ";
        queue.pop_front();

        for (auto i = adj[start].begin(); i != adj[start].end(); ++i)
            if (!visited[*i])
            {
                visited[*i] = true;
                queue.push_back(*i);
            }
    }
    cout << endl;
}

void Graph::dfs(int start)
{
    vector<bool> visited(vert,false);

    vector<int> stack;

    visited[start] = true;
    stack.push_back(start);

    while (!stack.empty())
    {
        start = stack.back();
        cout << start << " ";
        stack.pop_back();

        for (auto i = adj[start].begin(); i != adj[start].end(); ++i)
            if (!visited[*i])
            {
                visited[*i] = true;
                stack.push_back(*i);
            }
    }
    cout << endl;
}

int main()
{

    Graph g(6); // number of vertices we need
    g.addEdge(1, 4);
    g.addEdge(4, 2);
    g.addEdge(4, 5);
    g.addEdge(2, 5);
    g.addEdge(5, 3);

    g.bfs(1); // start with 1
    g.dfs(1);


}

计算结果为DFS :1 4 2 5 3和BFS 1 4 5 3 2，但在实际网络中，每条边缘都有一个权值，表示边缘的距离或速度。

​