如何以連接的方式遍歷連接的節點網絡？

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 然而，在實際網絡中，每個邊緣具有重量值，這意味着邊緣的距離或速度。