接続された方法で接続ノードネットワークをトラバースする方法はありますか？

Question

私はこのような接続されたネットワークとして視覚化することができるデータ構造を有する：私はは常に1つのノードから移動し、すべてのノードをトラバースすることが可能でなければならないこと（証明なし）信じ

を接続されたノード（もちろん、ツリー構造で行ったように、バックトラッキングは必須で、許可されています）。どうやってするの？

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

あなたは単に幅優先探索のため深さ優先探索またはキューためスタックでグラフを実装することができますよう

データ構造は、擬似コードで記述することができます

それぞれ、実際のネットワークでは、しかし1 4 2 5 3及びBFS 1 4 5 3 2 ： は結果がDFSある

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


} 

、我々はノードを開始するつもりだと仮定しますエッジは、エッジの距離または速度を意味する重み値を持ちます。