我正在写一个算法 BFS 图遍历。该图使用邻接链表实现。对于图遍历,是否必须在节点中有 int m_id 参数?
template <class T>
void graph<T>::bfs(int s, int& d)
{
bool used[m_vertex_sizes];
used[s] = true;
int p[m_vertex_sizes];
p[s] = s;
int dist[m_vertex_sizes];
dist[s] = 0;
std::queue<T> q;
q.push(s);
while(!q.empty())
{
int ii = q.front();
q.pop();
node<T>* t = m_adj[ii]->get_begin();
/// for(int i = 0; i < m_adj[ii]->get_size(); ++i)
for(; t != m_adj[ii]->get_end(); t = m_adj[ii]->get_next_node())
{
/****** int*/ v = m_adj[ii]->get_next_node(); // here I do not know how to get the node, may be need to have the id parameter in the node
if(!used[v])
{
used[v] = true;
p[v] = ii;
dist[v] = dist[ii] + 1;
d = dist[v];
q.push(v);
}
}
}
}
template <class T>
node<T>* get_next_node() const
{
m_next = m_next->m_next;
assert(m_next != 0);
return m_next;
}