机试常用算法和题型-图专题
2020-04-25 本文已影响0人
DecadeHeart
图专题
并查集，寻找父节点，合并模板
/*
这题有个小坑，当然也不算是坑，就是，看起来是求并查集的没错，但是额外附加了一个条件，单个端点只接收一次消息，所以，不能有环出现，排除也很简单，根据树的边数为n-1定则，而且要所有端点必须为同一集合，那么M必须等于N-1，否则，
所有端点无法连通，或出现环，so~题目就简单啦~~
*/
#include <iostream>
using namespace std;
//通信系统，要求所有结点都能收到发端消息且不重复
int father[1000];
int findFather(int a){
int x=a;
while(x!=father[x]){
x=father[x];
}
while(a!=father[a]){
int z=a;
a=father[a];
father[z]=x;
}
return x;
}
void init(int n){
for(int i=1;i<=n;i++){
father[i]=i;
}
}
void Union(int a,int b){
int A=findFather(a);
int B=findFather(b);
if(A!=B){
father[A]=B;
}
}
int main()
{
int n,k,a,b;
while(cin>>n>>k){
if(n==0) break;
init(n);
for(int i=0;i<k;i++){
cin>>a>>b;
Union(a,b);
}
int ans=0;
for(int i=1;i<=n;i++){
if(father[i]==i)
ans++;
}
//边只能有n-1条时才不会有环！！
if(ans==1&&k==n-1)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}
图的遍历DFS邻接矩阵和邻接表法
//给定一个无向图和所有边，判断这个图是否所有顶点都是联通的
#include <iostream>
#include <cstring>
using namespace std;
const int maxn=1010;
bool G[maxn][maxn];
bool flag[maxn]={false};
int n;
//n是点数，m是边数
void DFS(int x){
flag[x]=true;
for(int i=1;i<=n;i++){
//由于是无向边true表示可达
if(flag[i]==false&&G[x][i]==true){
G[x][i]=false;
G[i][x]=false;
//上面这个操作是为了提前清除已经访问边，这样就可以 不用下一组初始化
DFS(i);
}
}
}
int main(){
int m,d1,d2;
while(cin>>n>>m){
if(n==0) break;
for(int i=0;i<m;i++){
cin>>d1>>d2;
if(G[d1][d2]==false)
G[d1][d2]=G[d2][d1]=true;
}
int number=0;
memset(flag,0,sizeof(flag));
for(int i=1;i<=n;i++){
if(flag[i]==false){
number++;
DFS(i);
}
}
if(number==1){
printf("YES\n");
}else{
printf("NO\n");
}
}
return 0;
}
//邻接矩阵法，其实就要最后的连通块只有一个，有点类似并查集！！
//邻接表法
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn=1010;
vector<int> Adj[maxn];
bool flag[maxn]={false};
int n;
void DFS(int x){
flag[x]=true;
for(int i=0;i<Adj[x].size();i++){
int u=Adj[x][i];
//x的后继点！！
if(flag[u]==false){
DFS(u);
}
}
//清空，这样不用初始化为空
Adj[x].clear();
}
using namespace std;
int main()
{
int m,d1,d2;
while(cin>>n>>m)
{
if(n==0)
break;
for(int i=0;i<m;i++){
cin>>d1>>d2;
Adj[d1].push_back(d2);
Adj[d2].push_back(d1);
}
int number=0;
memset(flag,0,sizeof(flag));
for(int i=1;i<=n;i++){
if(flag[i]==false){
number++;
DFS(i);
}
}
if(number==1) printf("YES\n");
else printf("NO\n");
}
return 0;
}
迪杰特斯拉求最短路径长度+从某点到另一点的路径
6 8 0
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1
3 2 2
3 4 3
4 5 3
0 1 5 3 4 6
//迪杰特斯拉最短路劲
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXV=1000; //最大顶点数
const int INF=1000000000; //设置一个很大值表示不可达
int n,m,s,G[MAXV][MAXV]; //n为顶点数，m为边数，s为起点
int d[MAXV]; //起点到各点的最短路径长度
int pre[MAXV]; //prev【v】表示从起点到顶点v的最短路径上v的前一个顶点
bool vis[MAXV]={false}; //标记数组
void Dijkstra(int s){
fill(d,d+MAXV,INF); //s到所有点先设置成不可达
d[s]=0; //这个也很关键，s一开始到自己为0
for(int i=0;i<n;i++){
int u=-1,MIN=INF; //找到使d[u]最小的u,MIn存放最小的d[u]
for(int j=0;j<n;j++){
//第一轮自由一个d[s]=0,之后每轮d[u]都是更新的！！
if(vis[j]==false&&d[j]<MIN){
u=j;
MIN=d[j];
}
}
if(u==-1) return;
//找不到小于INF的d[u]说明剩下的顶点和起点s不连通
vis[u]=true;
//找到了标记成已访问
//从u出发能到达的下一个点，这样每次相当于都知道了下一轮要访问的点的距离
for(int v=0;v<n;v++){
//如果v未访问&&u能到达v&&以u为中介点，可以使d[v]更优
if(vis[v]==false&&G[u][v]!=INF&&d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
//优化d[v]
pre[v]=u;
//记录前驱顶点是u
}
}
}
}
//如何使用递归，根据前驱顶点，求最短路径
void DFS(int s,int v){
//s为起点编号，v为当前访问的顶点编号，要从重点开始递归，这样才能从头输出
if(v==s){
//递归重点，就是达到起点
printf("%d\n",s);
return;
}
DFS(s,pre[v]); //递归访问v的前驱顶点pre[v]
printf("%d\n",v); //从最深return回来之后再输出每一层
}
int main()
{
int u,v,w;
cin>>n>>m>>s;
//顶点个数，边数，起点编号
fill(G[0],G[0]+MAXV*MAXV,INF);
//对于矩阵如何初始化，学到了
for(int i=0;i<m;i++){
cin>>u>>v>>w;
G[u][v]=w;
//输入u，v以及u->v的边权，有向图
}
Dijkstra(s);
//直接算法入口
for(int i=0;i<n;i++){
//输出s到所有顶点的最短距离
printf("%d ",d[i]);
}
cout<<endl;
DFS(0,3);
return 0;
}
优先队列实现地杰斯特拉
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=60;
const int INF=0x3fffffff;
int G[maxn][maxn],n,d[maxn];
bool vis[maxn]={false};
struct Node{
int v,dis;
//这是有点队列所需要的！！
bool operator<(const Node &a)const{
return dis>a.dis;
}
//结构定义
Node(int x,int y){
v=x;
dis=y;
}
};
void Dijkstra(int s){
fill(d,d+maxn,INF);
d[s]=0;
//使用优先队列查找未访问的距离最短结点
priority_queue<Node> q;
q.push(Node(s,d[s]));
for(int i=0;i<n;i++){
if(q.empty()==true) return;
while(vis[q.top().v]==true){
q.pop();
if(q.empty()==true) return;
}
int u=q.top().v;
q.pop();
for(int v=0;v<n;v++){
if(G[u][v]!=0&&vis[v]==false&&d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
q.push(Node(v,d[v]));
}
}
}
}
int main()
{
int s;
while(cin>>n){
cin>>s;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin>>G[i][j];
}
}
Dijkstra(s);
for(int i=0;i<n;i++){
if(i!=s){
if(d[i]==INF)
printf("-1 ");
else printf("%d ",d[i]);
}
}
printf("\n");
}
return 0;
}
prim最小生成树算法
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=110;
const int INF=0x3fffffff;
int G[maxn][maxn],d[maxn];
int n;
bool vis[maxn];
int prim()
{
fill(d,d+maxn,INF);
memset(vis,0,sizeof(vis));
d[1]=0;
int ans=0;
for(int i=0;i<n;i++)
{
int min=INF,u=-1;
for(int j=1;j<=n;++j)
{
if(d[j]<min&&vis[j]==false)
{
u=j;
min=d[j];
}
}
//终于知道-1的作用，表示存在没有联通的地方！！
if(u==-1)
return -1;
vis[u]=true;
ans+=d[u];
for(int v=1;v<=n;++v)
{
if(vis[v]==false&&G[u][v]!=INF&&G[u][v]<d[v])
{
d[v]=G[u][v];
}
}
}
return ans;
}
int main()
{
int w,u,v;
while(~scanf("%d",&n))
{
if(n==0)
break;
fill(G[0],G[0]+maxn*maxn,INF);
for(int i=0;i<n*(n-1)/2;++i)
{
scanf("%d %d %d",&u,&v,&w);
G[u][v]=G[v][u]=w;
}
int ans=prim();
printf("%d\n",ans);
}
return 0;
}
并查集+最小生成树
#include <iostream>
#include <algorithm>
using namespace std;
#define N 101
int Tree[N];
//关键算法，找到爸爸节结点的标号
int findRoot(int x){
//查找代表集合的树的根节点，分成两个集合，以此来判断是否要合并两点到一个集合
if(Tree[x]==-1){
return x;
}else{
//当Tree[x]=1时，表示x爸爸是1，Tree[1]=-1,return Tree[x]=1是一个整体！！
int tmp=findRoot(Tree[x]);
//找x的爸爸，递归
Tree[x]=tmp;
//tmp确实是x的爸爸，爸爸存了
return tmp;
}
}
struct Edge{
//边要有结构体，来进行排序
int a,b;//顶点编号
int cost;
//重载小于运算符很关键！！
bool operator < (const Edge &A) const{
return cost<A.cost;
}edge[6000];
int main(){
int n;
while(cin>>n){
for(int i=1;i<=n*(n-1)/2;i++){
cin>>edge[i].a>>edge[i].b>>edge[i].cost;
}
sort(edge+1,edge+1+n*(n-1)/2);
for(int i=1;i<=n;i++){
Tree[i]=-1;
//初始所有边都处于孤立集合
}
int ans=0;
for(int i=1;i<=n*(n-1)/2;i++){
int a=findRoot(edge[i].a);
int b=findRoot(edge[i].b);
//查找两个顶点的集合信息
if(a!=b){
Tree[b]=a;
//合并两个集合，加入了一个边
cout<<a<<" "<<b<<" "<<edge[i].cost<<endl;
ans=ans+edge[i].cost;
}
}
cout<<ans;
}
return 0;
}
}
克鲁斯卡尔最小生成树
6 10
0 1 4
0 4 1
0 5 2
1 2 1
1 5 3
2 3 6
2 5 5
3 4 5
3 5 4
4 5 3
11
//克鲁斯卡尔最小生成树算法
#include <iostream>
#include <32/bits/stdc++.h>
using namespace std;
const int MAXV=110;
const int MAXE=10010;
struct edge{
int u,v; //边的两个端点编号
int cost; //边权
}E[MAXE];
bool cmp(edge a,edge b){
return a.cost<b.cost;
}
//并查集部分
int father[MAXV]; //并查集数组
int findFather(int x){
//并查集查询函数
int a=x;
while(x!=father[x]){
x=father[x];
}
//路径要锁，直接得到每个点的爸爸
while(a!=father[a]){
int z=a;
a=father[a];
father[z]=x;
}
return x;
}
//n为顶点个数，m为图的边数
int kruskal(int n,int m){
//ans为所求边权和，Num_Edge为当前生成树的边数
int ans=0,Num_Edge=0;
for(int i=0;i<n;i++){
father[i]=i; //并查集初始化
}
sort(E,E+m,cmp); //所有边按权值大小排序
for(int i=0;i<m;i++){
cout<<E[i].v<<" "<<E[i].u<<" "<<E[i].cost<<endl;
}
cout<<"路径："<<endl;
for(int i=0;i<m;i++){
//枚举所有边
int faU=findFather(E[i].u); //查询测试边两个端点所在集合根结点
int faV=findFather(E[i].v);
//这就是合并了
if(faU!=faV){
//只有不在同一个集合才可以合并
father[faU]=faV;
ans+=E[i].cost;
cout<<E[i].v<<"->"<<E[i].u<<endl;
Num_Edge++; //当前生成树边数加1
if(Num_Edge==n-1) break;
//边数等于顶点数减一时结束算法
}
}
if(Num_Edge!=n-1) return -1; //无法连通时返回-1
else return ans; //返回最小生成树的边权之和
}
int main()
{
int n,m;
cin>>n>>m; //顶点数和边数
for(int i=0;i<m;i++){
cin>>E[i].u>>E[i].v>>E[i].cost;
}
int ans=kruskal(n,m);
cout << ans<< endl;
return 0;
}
