c++ - C++中无向图中的连接组件

Question

我正在寻找一个 c++ 代码来查找无向图中的连接组件。我有一个叫做“定向”的大矩阵。它的元素是零或一。 directed(i,j)=1 表示 i 顶点有指向 j 顶点的直接链接。我想找到通过直接或间接连接顶点和组的大小创建的不同组的数量。下面的代码采用连接的顶点并在不同的行中打印不同组的元素。 知道有向矩阵，谁能帮我找到组的数量和每个组的大小？这是代码:

// C++ program to print connected components in
// an undirected graph
#include<iostream>
#include <list>
using namespace std;

// Graph class represents a undirected graph
// using adjacency list representation
int input(istream& in=cin)
{
int x;
in >> x;
return x;
}


class Graph
{
int V;    // No. of vertices

// Pointer to an array containing adjacency lists
list<int> *adj;

// A function used by DFS
void DFSUtil(int v, bool visited[]);
public:
Graph(int V);   // Constructor
void addEdge(int v, int w);
void connectedComponents();
};

// Method to print connected components in an
// undirected graph
void Graph::connectedComponents()
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int v = 0; v < V; v++)
    visited[v] = false;

for (int v=0; v<V; v++)
{
     if (visited[v] == false)
       {
        // print all reachable vertices
        // from v
        DFSUtil(v, visited);

        cout << "\n";
       }
    }
}

void Graph::DFSUtil(int v, bool visited[])
{
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";

// Recur for all the vertices
// adjacent to this vertex
list<int>::iterator i;
for(i = adj[v].begin(); i != adj[v].end(); ++i)
    if(!visited[*i])
        DFSUtil(*i, visited);
}

Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}

// method to add an undirected edge
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}

// Drive program to test above
int main()
{
int directed[2][2];

 directed[0][0]=1;
 directed[0][1]=0;
 directed[0][2]=0;
 directed[1][1]=1;
 directed[1][0]=1;
 directed[1][2]=1;
 directed[2][1]=0;
 directed[2][2]=0;
 directed[2][0]=1;
 return 0;
 }

Answer 1

Could you please provide a runnable answer (x4)

当然:

Live On Coliru

// C++ program to print connected components in
// an undirected graph
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/connected_components.hpp>

// Graph class represents a undirected graph
// using adjacency list representation
class Graph {
    using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS>;
    using Component = int;
    using Mapping = std::map<G::vertex_descriptor, Component>;
    G g;

  public:
    Graph(int V) : g(V) {}
    void addEdge(int v, int w);
    void connectedComponents();
};

// Method to print connected components in an
// undirected graph
void Graph::connectedComponents() {
    Mapping mappings;
    int n = boost::connected_components(g, boost::make_assoc_property_map(mappings));

    for (Component c = 0; c<n; ++c) {
        std::cout << "component " << c << ":";

        for (auto& mapping : mappings)
            if (mapping.second == c) std::cout << " " << mapping.first;

        std::cout << "\n";
    }
}

void Graph::addEdge(int v, int w) {
    boost::add_edge(v, w, g);
}

int main() {
    // Create a graph given in the above diagram
    Graph g(5); // 5 vertices numbered from 0 to 4
    g.addEdge(1, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 4);

    std::cout << "Following are connected components \n";
    g.connectedComponents();
}

打印

Following are connected components 
component 0: 0 1
component 1: 2 3 4