Блог пользователя rootn

Автор rootn, история, 7 лет назад, По-английски

BFS

Breadth first search uses queue.If we use adjacency list to store graph then the following code will implement the BFS:

// V is the number of vertices
// s is the starting index;

list<int> G[V]; 
vector<bool> visited(V, false);
queue<int> q;

void BFS(int s)
{
    q.push_back(s);
    while(!q.empth())
    {
        s = q.front();
        cout << s << " ";
        q.pop_front();
        for(auto i = F[s].begin();i != G[s].end();i++)
        {
            if(!visited[*i])
            {
                visited[*i] = true;
                q.push_back(*i);
            }
        }
    }
}

However, this implementation will not be able to traverse a disconnected graph completely.To do so, we have to check every node by making it a starting node and BFS from that node.

for(int i = 0;i < V;i++)
{
    if(!visited[i])
        BFS(i);
}

DFS

DFS make use of stack. For than we don't have to use a separate stack, we can implement it using recursion. Following code shows implementation of DFS using assumptions taken while explaining BFS:

void DFS(int s)
{
    visited[s] = true;
    cout << s << " ";
    for(auto i = G[s].begin();i != G[s].end();i++)
        if(!visited[*i])
            DFS(*i);
}

This implementation can also be made to traverse the whole graph, in case of disconnected graph, by using the iterative calls used in BFS.

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится