时间戳

首页 > 解决方案 > 计算无向无权图的每个连接部分中的节点数

c++ - 计算无向无权图的每个连接部分中的节点数

问题描述

我是 C++ STL 的新手，最近开始学习图论。参考https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/后，我可以使用 DFS 计算无向、未加权图中的连接组件数：

#include <bits/stdc++.h>
typedef long long ll;

using namespace std;
int connected=0, temp1, temp2,n, p;

void DFS(int start, vector<int> v[],vector<int> &visited) {
    visited[start] = 1;
    for(int i= 0; i<v[start].size(); ++i) {        
        if(visited[v[start][i]] == 0)
            DFS(v[start][i], v, visited);        
    }    
}

int main() {
    cin>>n>>p; // number of vertices and edges
    vector<int> v[n+1], visited(n+1,0);
    for(int i=0; i<p; ++i) {
        cin>>temp1>>temp2;
        v[temp1].push_back(temp2);
        v[temp2].push_back(temp1);
    }     
    connected = 0;
    for(int i=1;i<=n;++i) {
        if(visited[i] == 0 ) {
            connected++;
            DFS(i,v,visited);
        }        
    }
    cout<<connected<<endl;    
return 0;
}

但是我们如何计算每个组件中的节点总数呢？

例如：在此图中，请参见图像有 3 个连接组件，没有。节点分别为 3、2 和 1。

标签： c++graphstlundirected-graph

解决方案

count您可以在每次调用DFSfrom时维护一个虚拟变量main()

void DFS(int start, vector<int> v[],vector<int> &visited, int &count)
{
  visited[start] = 1;
  count++;
  for(int i= 0; i<v[start].size(); ++i)
  {        
    if(visited[v[start][i]] == 0)
        DFS(v[start][i], v, visited);        
  }    
}

和

for(int i=1;i<=n;++i)
{
  if(visited[i] == 0 )
  {
     connected++;
     int count=0;
     DFS(i,v,visited,count);
     cout<<"This component has "<<count<<" nodes"<<"\n";
  }        
}

或者您可以visited在每次调用DFS()from后参考向量的变化（其中的新 1 的数量）main()

推荐阅读