如何以连接的方式遍历连接的节点网络？

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

你可以简单地实现对深度优先搜索或队列为广度优先搜索与堆栈图

eg 假设我们要与节点开始，

#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 然而，在实际网络中，每个边缘具有重量值，这意味着边缘的距离或速度。