求连通分量(无向图,邻接矩阵,BFS)

2024-05-06 03:08

本文主要是介绍求连通分量(无向图,邻接矩阵,BFS),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1、题目:


 Problem Description

设有一无向图,其顶点值为字符型并假设各值互不相等,采用邻接矩阵表示法存储表示。利BFS用算法求其各连通分量,并输出各连通分量中的顶点。

 Input

有多组测试数据,每组数据的第一行为两个整数n和e,表示n个顶点和e条边(0<n<20);第二行为其n个顶点的值,按输入顺序进行存储;后面有e行,表示e条边的信息,每条边信息占一行,包括边所依附的顶点下标i和j,数据之间用空格隔开。

 Output

按存储顺序的先后,输出各连通分量中的顶点,每组输出占若干行,每行最后均无空格,每两组数据之间有一空行,具体格式见样例。

 Sample Input

4 4
ABCD
0 1
0 3
1 2
1 3
4 3
ABCD
0 1
0 3
1 3

 Sample Output

1:A,B,D,C1:A,B,D
2:C

 Author

hwt


2、参考代码:


#include <iostream>
#include <string.h>
using namespace std;class MGraph{
private:int vertexNum,arcNum;char vertex[111];int edge[111][111];
public:int vis[111];MGraph(char* a,int n,int e);~MGraph(){}void BFS(int v);
};MGraph::MGraph(char* a,int n,int e){vertexNum=n;arcNum=e;memset(edge,0,sizeof(edge));int i,j;for(i=0;i<n;i++)vertex[i]=a[i];while(e--){cin>>i>>j;edge[i][j]=edge[j][i]=1;}
}void MGraph::BFS(int v){int front,rear,count=0;front=rear=-1;int Q[111];vis[v]=1;Q[++rear]=v;cout<<vertex[v];while(front!=rear){v=Q[++front];for(int j=0;j<vertexNum;j++){if(edge[v][j]==1 && !vis[j]){cout<<","<<vertex[j];vis[j]=1;Q[++rear]=j;}}}
}int main()
{int n,e;bool flag=false;char a[111];while(cin>>n>>e){if(flag)cout<<endl;cin>>a;MGraph w(a,n,e);memset(w.vis,0,sizeof(w.vis));int x=1;for(int i=0;i<n;i++){if(w.vis[i]==0){cout<<x++<<":";w.BFS(i);cout<<endl;}}flag=true;}return 0;
}



这篇关于求连通分量(无向图,邻接矩阵,BFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/963319

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

poj 2914 无向图的最小割

题意: 求无向图的最小割。 解析: 点击打开链接 代码: #pragma comment(linker, "/STACK:1677721600")#include <map>#include <set>#include <cmath>#include <queue>#include <stack>#include <vector>#include <cstd

线性因子模型 - 独立分量分析(ICA)篇

序言 线性因子模型是数据分析与机器学习中的一类重要模型,它们通过引入潜变量( latent variables \text{latent variables} latent variables)来更好地表征数据。其中,独立分量分析( ICA \text{ICA} ICA)作为线性因子模型的一种,以其独特的视角和广泛的应用领域而备受关注。 ICA \text{ICA} ICA旨在将观察到的复杂信号

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

C语言-数据结构 克鲁斯卡尔算法(Kruskal)邻接矩阵存储

相比普里姆算法来说,克鲁斯卡尔的想法是从边出发,不管是理解上还是实现上都更简单,实现思路:我们先把找到所有边存到一个边集数组里面,并进行升序排序,然后依次从里面取出每一条边,如果不存在回路,就说明可以取,否则就跳过去看下一条边。其中看是否是回路这个操作利用到了并查集,就是判断新加入的这条边的两个顶点是否在同一个集合中,如果在就说明产生回路,如果没在同一个集合那么说明没有回路可以加入

双头BFS

牛客月赛100 D题,过了80%数据,调了一下午。。。烦死了。。。 还是没调试出来,别人的代码用5维的距离的更新有滞后性,要在遍历之前要去重。。。 #include<bits/stdc++.h>using namespace std;const int N=2e3+10;char g[N][N];int dis[N][N],d1[N][N];int n,m,sx,sy;int dx

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历,在uva上找了个题敲了出来,感觉还不错,最近敲代码挺有手感的,希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in

【CF】D. Arthur and Walls(BFS + 贪心)

D题 解题思路就是每次检查2X2的方格里是否只有一个‘*’,如果有的话这个*就需要变成‘.’,利用BFS进行遍历,入队的要求是这个点为. 一开始将所有的'.'全部加入队列,如果碰到一个'*'变成'.'就入队,判断的时候从4个方向就行判断 题目链接:http://codeforces.com/contest/525/problem/D #include<cstdio>#include<