• 求无向图的连通分量
2022-04-05 19:46:05

1、DFS
每调用一次DFS(u)，就能遍历u所在的连通分量

class Solution {
private:
static const int N = 2010;
int n, G[N][N];
bool visited[N] = {false};
public:
int countComponents(int n, vector<vector<int>>& edges) {
this->n = n;
memset(G, 0, sizeof G);
for (vector<int> edge : edges){
int u = edge[0], v = edge[1];
G[u][v] = G[v][u] = 1;
}
int res = 0;
for (int i = 0; i < n; i++){
if (!visited[i]){
DFS(i);
res++;
}
}
return res;
}

void DFS(int u){
visited[u] = true;
for (int v = 0; v < n; v++){
if (G[u][v] != 0 && !visited[v])
DFS(v);
}
}
};


2、并查集
将两个节点看做集合，如果a、b之间有边，那么把a、b合并，最后计算集合中根节点的个数即可

class Solution {
private:
static const int N = 2010;
int father[N];
public:
int countComponents(int n, vector<vector<int>>& edges) {
int res = 0;
memset(father, 0, sizeof father);
for (int i = 0; i < n; i++) father[i] = i;
for (vector<int> edge : edges){
int a = edge[0], b = edge[1];
int FaA = findFather(a), FaB = findFather(b);
if (FaA != FaB){
father[FaB] = FaA;  //将b的父节点连接到a所在的子树上
}
}
for (int i = 0; i < n; i++){
if (father[i] == i) res++;
}
return res;
}

int findFather(int a){
if (a != father[a]) father[a] = findFather(father[a]);
return father[a];
}
};

更多相关内容
• 利用深度遍历算法实现int getNum(MGraph G) {int i, count = 0;for(i = 0; i < G.vexnum; i++)visited[i] = false;for(i = 0; i < G.vexnum; i++)if(!...}测试代码如下：以下代码以邻接表作为...

利用深度遍历算法实现

int getNum(MGraph G) {

int i, count = 0;

for(i = 0; i < G.vexnum; i++)

visited[i] = false;

for(i = 0; i < G.vexnum; i++)

if(!visited[i]) {

count++;

DFS(G, i);

}

return count;

}

测试代码如下：

以下代码以邻接表作为图的存储方式

#include

#include

#define MAXVEX 10

typedef int VertexType;

typedef struct arcNode {

struct arcNode *next;

} arcNode;

typedef struct vertexNode {

VertexType data;

arcNode *first;

typedef struct {

int vexnum, arcnum;

} ALGraph;

//邻接表初始化

void createALGraph(ALGraph &G) {

int i, j, k;

arcNode *e;

printf("输入顶点数和边数：\n");

scanf("%d%d", &G.vexnum, &G.arcnum);

for(i = 0; i < G.vexnum; i++) {

}

for(k = 0; k < G.arcnum; k++) {

printf("输入边(vi, vj)上的顶点序号：\n");

scanf("%d%d", &i, &j);

e = (arcNode *)malloc(sizeof(arcNode));

e = (arcNode *)malloc(sizeof(arcNode));

}

}

//深度优先遍历

int visited[MAXVEX];

void DFS(ALGraph G, int i) {

arcNode *p;

visited[i] = 1;

while(p) {

p = p->next;

}

}

//求连通分量

int getNum(ALGraph G) {

int i, count = 0; //记录连通分量个数

for(i = 0; i < G.vexnum; i++)

visited[i] = 0;

for(i = 0; i < G.vexnum; i++)

if(!visited[i]) {

count++;

DFS(G, i);

}

return count;

}

int main() {

ALGraph G;

createALGraph(G);

printf("%d", getNum(G));

return 0;

}

展开全文
• 给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图连通分量的数目。 示例 1: 输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]]  0 3  | |  1 — 2 4  ...
• 对于一个无向连通图，从图中某一顶点出发，...然而图的深度优先搜索（DFS）算法一般采用递归算法来实现，鉴于二叉树遍历算法可以转换为非递归算法来实现，试编写基于DFS的非递归遍历算法的无向图连通分量的识别程序。
• #include #define MAX_VERTEX_NUM 50 using namespace std; typedef char VerType; typedef struct ArcNode //定义弧结点所在位置， { int adj; int info;...=1) cout为非连通,连通分量为"为连通通"; }

#include

#define MAX_VERTEX_NUM 50

using namespace std;

typedef char VerType;

typedef struct ArcNode //定义弧结点所在位置，

{

int info;

ArcNode *next;

}ArcNode;

typedef struct VerNode //定义顶点(顶点数据，顶点所指向第一条弧的指针)

{

VerType data;

ArcNode *first;

}VerNode;

{

VerNode VerNodes[MAX_VERTEX_NUM]; //顶点集

int verNum,arcNum; //顶点数，弧数

typedef struct Queue //FIFO队列

{

int Item[MAX_VERTEX_NUM];

int front,rear;

}Queue;

int visited[MAX_VERTEX_NUM]; //顶点访问标志数组

//定位某一结点的位置,找不到返回0

int LocateGraph(const AdjList *g,const char data)

{

for(int i=1;i<=g->verNum;i++)

{

if(g->VerNodes[i].data==data)

return i;

}

return 0;

}

//初始化队列

void InitQueue(Queue *Q)

{

for(int i=1;i<=MAX_VERTEX_NUM;i++)

{

Q->Item[i]=0;

}

Q->front=Q->rear=1;

}

//创建图的邻接表

{

int s,d,weigth;

char sChar,dChar;

ArcNode *q=NULL;

cout<

cin>>g->verNum>>g->arcNum;

cout<

//初始化顶点

for(int i=1;i<=g->verNum;i++)

{

cin>>g->VerNodes[i].data;

g->VerNodes[i].first=NULL;

}

//初始化弧

for(i=1;i<=g->arcNum;i++)

{

cout<

cin>>sChar>>dChar>>weigth;

s=LocateGraph(g,sChar);

d=LocateGraph(g,dChar); //定位该顶点的位置

q=(ArcNode *)malloc(sizeof(ArcNode));

q->next=g->VerNodes[s].first;

g->VerNodes[s].first=q;

}

}

//初始化访问标志数组,0为未访问过相应的顶点i

{

for(int i=1;i<=g->verNum;i++)

{

visited[i]=0;

}

}

//访问顶点值

{

cout<VerNodes[v].data<

}

//广度遍历图从v顶点开始

{

ArcNode *q=NULL;

Queue *Q=(Queue *)malloc(sizeof(Queue));

InitQueue(Q);

Q->Item[Q->rear]=v;visit(g,v);visited[v]=1;

Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;

while(Q->front!=Q->rear) //队列不为空

{

v=Q->Item[Q->front]; //取队首元素

Q->front=(Q->front+1)%MAX_VERTEX_NUM;

q=g->VerNodes[v].first;

while(q!=NULL) //同一层上(广度搜索的层)还有其他元素,则访问顶点，入队

{

{

Q->rear=(Q->rear+1)%MAX_VERTEX_NUM;

q=q->next;

}

}

}

}

//广度遍历图

{

int count=0;

InitVisited(g);

for(int i=1;i<=g->verNum;i++)

{

if(!visited[i])

{

BFS(g,i);

count++;

}

}

return count;

}

int main()

{

int count;

if((count=BFSTransfer(g))!=1)

cout<

else

cout<

return 0;

}

展开全文
• (注意：判断一个无向图是否连通) 一个无向图连通分量。 输入描述 第一行输入无向图的顶点数和边的条数，以空格隔开 第二行输入每个顶点的数据，中间没有空格 第三行输入每条边，每条边的格式为i j，中间有空格，...

## 问题描述

已知无向图的顶点为字符型，要求采用邻接矩阵表示，图中顶点序号按字符顺序排列，从键盘输入图中顶点的个数、边的条数、顶点的信息和边的组成等。(注意：判断一个无向图是否连通) 求一个无向图的连通分量。
输入描述
第一行输入无向图的顶点数和边的条数，以空格隔开
第二行输入每个顶点的数据，中间没有空格
第三行输入每条边，每条边的格式为i j，中间有空格，所有边占一行
输出描述
输出该无向图的连通分量，占一行
输入样例
5 5
ABCDE
0 1 0 4 1 2 2 3 3 4
输出样例
1

## 问题分析

首先要清楚什么是无向图，在图的结构中每两个点之间最多只有一条线，这条线即代表了由a指向b，也代表了由b指向a，连通分量的概念：
在上图中连通分量就是4.所以说连通分量就是在图中非连通子图的数量。

## 代码

#include<iostream>
using namespace std;
const int MaxSize = 20;
struct EdgeNode						//保存边表结点其中有下一个结点的下表和指向下一个结点的指针
{
EdgeNode *next;					//下一结点
};

struct VertexNode
{
char vertex;					//保存顶点
EdgeNode *firstEdge;			//指针域，指向下一个结点
};

class AlGraph
{
public:
AlGraph();
~AlGraph();
void BFTraverse(int v);			//广度优先遍历
int visited[MaxSize];
int EdgeNum,VertexNum; 			//保存顶点和边的个数
private:

};

AlGraph::AlGraph()
{
int x, y;								//用来保存边
EdgeNode *s = NULL;
cin >> VertexNum >> EdgeNum;

for(int i =0;i < VertexNum; i++)		//输入顶点
{
visited[i] = 0;
}
for(int j = 0; j< EdgeNum; j++)			//尾插法
{
cin >> x >> y;
s = new EdgeNode;
}
}

AlGraph::~AlGraph()								//释放资源
{
EdgeNode *p = NULL, *q = NULL;
for(int i = 0; i < VertexNum; i++)
{
while(p != NULL)
{
p = p->next;
delete q;
q = p;
}
}
}

void AlGraph::BFTraverse(int v)
{
for(int i = 0; i < VertexNum; i++)
{
visited[i] = 0;
}
EdgeNode *p = NULL;
char Q[MaxSize];
int w,j;
int rear,front;
rear = front = -1;
visited[v] = 1;
Q[++rear] = v;
while(rear != front)
{
w = Q[++front];
while(p != NULL)
{

if(visited[j] == 0)
{

visited[j] = 1;
Q[++rear] = j;
}
p = p->next;
}
}
front = rear = -1;

}

int main()
{
int i, count = 0;
int judge = 1;
AlGraph A;

A.BFTraverse(0);						//广度优先遍历
for(i = 0; i < A.VertexNum; i++)
{
if(A.visited[i] == 0)				//遍历之后如果还存在未访问的顶点，那就是连通分量的个数
{
judge = 0;
A.BFTraverse(i);
count++;
}
}
if(judge == 1)
{
cout << 1;
}
else
{
cout << count ;
}
}

展开全文
• 一:求无向图连通分量个数  基于DFS，count计数。  从某一顶点出发遍历图，for循环，改变起始顶点，count计数 void DFSTraverse(ALGraph G){ //深度遍历图 void DFS(ALGraph G,int i); int count=0; ...
• Input： ...1个整数，表示连通分量的个数 虽然不是很难，但是初学者可能要花很长时间才能独立写出来（包括我自己） #include <iostream> #include <cstdio> #include <cstring...
• 1：DFS：循环找有没有没被遍历的点， 有的话连通就多了一个连通分量， 从该点再dfs遍历其他点。 每次找没被遍历的点（如果找到没被遍历的点，分量++），从改点进行bfs遍历； 2：并查集： 有多少集合 就有多少 连通...
• 标签：并查集、深度优先搜索、广度优先搜索、 解法 时间复杂度 空间复杂度 执行用时 Ans 1 (Python) O(N)O(N)O(N) O(N)O(N)O(N) 132ms (49.22%) Ans 2 (Python) Ans 3 (Python) 解法一： ...
• 就能count++下去了，后来想了一下，从起点开始循环，到每一个顶点的深度优先遍历一下，那么没有一个没有遍历到的顶点那么这不就是一个新的分支么，深度优先遍历过一次的就是一个连通分量。也许过几天我自己又理解不...
• 一，介绍本文使用数据结构：并查集 来实现 求解无向图连通分量个数。无向图连通分量就是：无向图的一个极大连通子图，在极大连通子图中任意两个顶点之间一定存在一条路径。对于连通的无向图而言，只有一个连通...
• 假设无向图G采用邻接矩阵存储，编写一个算法求连通分量的个数。 输入 第一行为一个整数n，表示顶点的个数（顶点编号为0到n-1），接下来是为一个n*n大小的整数矩阵，表示图的邻接关系。数字为0表示不邻接，1表示不...
• 深度优先搜索的下一个直接应用就是找出一幅的所有连通分量。“与…连通”是一种等价关系，它能够将所有顶点切分为等价类（连通分量）。 连通分量的API： API 功能 CC(Graph G) 预处理构造函数 boolean ...
• ## 图论算法——无向图的连通分量

万次阅读 多人点赞 2019-05-22 19:19:37
引言 深度优先搜索的一个直接应用就是找出一幅的所有连通分量
• #define N 10000 //中点的个数 int graph[N][N];// 0 表示没有边 1 表示有边 bool visited[N]={false}; void DFS(int root){ visited[root]=true; for(int i=0;i&lt;N;i++){ if(visited[i]==false&amp;...
• 今天小编就为大家分享一篇关于判断一个无向图是否为连通图的方法，小编觉得内容挺不错的，现在分享给大家，具有很好的参考价值，需要的朋友一起跟随小编来看看吧
• 特里斯坦·乌塞尔2012 年 4 月无向图上的连通分量分析，具有各种阈值和连通性约束。 [groups,orphans] = graph_analysis(W); [groups,orphans] = graph_analysis(W,'field',value,...); [groups,~] = graph_...
• 计算无向图连通子图个数，使用dfs遍历，例如 Input : 5 1 2 1 3 1 4 2 5 Output: 1 Input: 5 1 3 1 4 2 5 3 4 Output: 2
• #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; int mp[100][100]; int visit[100]; void dfs(int x,int n) { int i; visit[x]=1;... if(...
• ## 无向图的连通分量

千次阅读 2022-04-23 21:56:47
读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法建立无向图的生成森林。对于森林中的每一棵生成树，遍历所有顶点，并输出遍历顶点的顺序。 输入 输入的第一行包含一个正整数n...
• 这里基于MATLAB图论工具制作输入邻接矩阵，输出连通分量。 输入输出 函数输入为A为邻接矩阵，ng为所含最少智能体个数的连通分量，如ng为2则输出含智能体个数大于等于2的连通分量； 函数输出为输入邻接矩阵对应的...
• 使用networkx包求图的所有连通子图 import networkx as nx import matplotlib.pyplot as plt pointList = ['A','B','C','D','E','F','G'] linkList = [('A','B'),('B','C'),('C','D'),('E','F'),('F','G'),] def ...
• 给定编号从 0 到 n-1 的 n 个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图连通分量的数目。 示例 1: 输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]] 0 3 | | 1 --- 2 4 ...
• 给定编号从0到n-1的n个节点和一个无向边列表（每条边都是一对节点），请编写一个函数来计算无向图连通分量的数目。 示例 1: 输入: n = 5 和 edges = [[0, 1], [1, 2], [3, 4]] 0 3 | | 1 --- 2 4 输出: 2...
• 求图连通分量个数在算法题中时有考到，是算法中基础而重要的问题。对于这个问题，常用的解法有搜索算法（DFS、BFS等），及并查集算法。的搜索算法在我的其他博文中已经介绍过，这里用一个例题介绍一下并查集...
• 先初始化，再循环每一组连接，最后返回连通个数。 990. 等式方程的可满足性 class Solution { public int countComponents(int n, int[][] edges) { UF uf = new UF(n); for (int[] e : edges) { uf.union(e[0...

...