如何以连接的方式遍历连接的节点网络?
问题描述:
我有数据结构,它可以被可视化为连接的网络如此:如何以连接的方式遍历连接的节点网络?
相信(不证明),它应该能够遍历所有的节点,总是从一个节点移动到一个连接的节点(回溯当然是必需的并且被允许 - 就像你在树结构中所做的那样)。怎么做?
的数据结构可以写成伪代码为:
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
}
答
你可以简单地实现对深度优先搜索或队列为广度优先搜索与堆栈图
#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 然而,在实际网络中,每个边缘具有重量值,这意味着边缘的距离或速度。
你的意思是像[深度优先搜索](https://en.wikipedia.org/wiki/Depth-first_search)? – Dukeling
如果允许回溯,您可以使用BFS或DFS,否则使用DFS。 – syntagma
看起来好像是。感谢您指出游戏的名称:) – Svein