0

我正在写一个算法 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;
}
4

0 回答 0