Search for C++connectivity components?

Sample code in c++/java? Meaning, searching for connectivity components using depth/width traversal. I'm going to search the adjacency matrix.

Author: Pavel, 2011-03-23
Source

2 answers

As far as I understand, the author of the question needs an algorithm for finding the components of connectivity, and not the component of strong connectivity, and this is not the same thing at all! 

    int n, a[100][100], cur = 0;
    fin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            fin >> a[i][j];
    vector <int> was(n, -1);
    queue <int> q;
    for (int i = 0; i < n; i++)
    {
        if (was[i] != -1)
           continue;
        q.push(i);
        while (!q.empty())
        {
              int v = q.front();
              q.pop();
              if (was[v] != -1)
                 continue;
              was[v] = cur;
              for (int j = 0; j < n; j++)
                  if (a[i][j] != 0 && was[j] == -1)
                     q.push(j);
        }
        cur++;
    }
This code reads the graph given by the adjacency matrix(but I advise you to use adjacency lists). As a result, the vector was for each vertex will contain the number of its connected component, and cur - the number of its connected component.

 1
Author: di0gen, 2011-05-05 21:45:37

Boost has a library for working with graphs, here's about connectivity components: strong_components.

The strong_components() functions compute the strongly connected components of a directed graph using Tarjan's algorithm based on DFS.

 3
Author: yapycoder, 2011-03-23 12:22:05