图论2023.4.14
图结构如何表示？邻接矩阵or邻接表
稠密图适合使用邻接矩阵进行存储而稀疏图则适合邻接表进行存储，并且当问题中存在大量遍历邻接顶点的操作而较少判断两个特定顶点的关系时，使用邻接表较为适宜。
虽然叫邻接表，但是实际编码过程中通常并不采用链表的方式来实现，而是采用向量来实现。
一、并查集
并查集的两个操作：查找与合并
但是在合并中，为了避免因为树的退化而产生额外的时间消耗，可以在查找某特定结点的根结点的同时，将其与根结点之间的所有结点都直接指向根结点。
ex1.畅通工程（浙江大学复试上机题）
//畅通工程
#include <bits/stdc++.h>using namespace std;
const int N=1010;
int father[N];
int height[N];void init(int n)
{for(int i=0;i<=n;i++){father[i]=i; height[i]=0;}
}
int find(int x)//找到最上方的根节点
{ //路径压缩 if(x!=father[x]){father[x]=find(father[x]);}return father[x];
}
void Union(int x,int y)
{//合并 int fx=find(x);int fy=find(y);if(height[fx]<height[fy]) father[fx]=fy;else if(height[fx]>height[fy]) father[fy]=fx;else{father[fy]=fx;height[fx]++; }
}
int main()
{int n;while(scanf("%d",&n)!=EOF){if(n==0) return 0;else{int m;scanf("%d",&m);init(n);//初始化 while(m--){int x,y;scanf("%d%d",&x,&y);Union(x,y);}int res=-1;for(int i=1;i<=n;i++){if(find(i)==i) res++;}printf("%d\\n",res);}}return 0;
} ex2 连通图（吉林大学复试上机题）
//连通图
#include <bits/stdc++.h>using namespace std;
const int N=1010;
int father[N];
int height[N];
void init(int n)
{for(int i=0;i<=n;i++){father[i]=i;height[i]=0;}
}
int find(int x)
{if(x!=father[x]){father[x]=find(father[x]);}return father[x];
}
void Union(int x,int y)
{int fx=find(x);int fy=find(y);if(height[fx]<height[fy]) father[fx]=fy;else if(height[fy]<height[fx]) father[fy]=fx;else {father[fy]=fx;height[fx]++;}
}
int main()
{int n,m;while(scanf("%d%d",&n,&m)!=EOF){init(n);//别忘记初始化 while(m--){int x,y;scanf("%d%d",&x,&y);Union(x,y); } int res=0;for(int i=1;i<=n;i++){if(find(i)==i)res++;}if(res==1) printf("YES\\n");else printf("NO\\n");}
} ex3.Is It A Tree?（北京大学复试上机题）
分析：不仅需要判断所有点是否属于一个集合，还需要判断各个点是否符合树的定义，而判断各点是否符合树的定义可以转换为判断它的入度是否符合要求，根结点的入度为0，而其余点的入度为1.只要各个结点满足入度要求，只有一个根节点，以及各个结点属于同一集合，就可以构成一棵树
代码如下：
//连通图
#include <bits/stdc++.h>
using namespace std;
const int N=10000;
int father[N];
int height[N];
bool visit[N];
int inDegree[N];void init()
{for(int i=0;i<N;i++){father[i]=i;height[i]=0;inDegree[i]=0;visit[i]=false;}
}
int find(int x)
{if(x!=father[x]){father[x]=find(father[x]);}return father[x];
}
void Union(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy){if(height[fx]<height[fy]) father[fx]=fy;else if(height[fy]<height[fx]) father[fy]=fx;else {father[fy]=fx;height[fx]++;} }
}
bool isTree()
{bool flag=true;int res=0;//连通分量int root=0;//根结点数目for(int i=0;i<N;i++){if(!visit[i]) continue;if(find(i)==i) res++; if(inDegree[i]==0) root++;else if(inDegree[i]>1) flag=false; } if(res!=1||root!=1) flag=false;if(res==0&&root==0) flag=true;return flag;
}
int main()
{int x,y;int Casenumber=0;init();while(scanf("%d%d",&x,&y)!=EOF){if(x==-1&&y==-1) break;if(x==0&&y==0){if(isTree()) printf("Case %d is a tree\\n",++Casenumber);else printf("Case %d is not a tree\\n",++Casenumber); init(); }else{Union(x,y);inDegree[y]++;visit[x]=true;visit[y]=true;}}
} ex11.1找出直系亲属（浙江大学复试上机题）
采用并查集思想，用son数组记录自己儿子结点
#include <bits/stdc++.h>using namespace std;
const int N=51;
int son[N];
void init()
{for(int i=0;i<N;i++)son[i]=i;
}
int Find(int x,int y)//注意这个函数的含义
{int ans=0;while(son[x]!=x){if(son[x]==y) {++ans;break;}else{++ans;x=son[x];}}if(son[x]==x) return 0;return ans;
}
int main()
{ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0);init();int n,m;cin>>n>>m;char a,b,c,x,y;while(n--){cin>>a>>b>>c;son[b-'A']=a-'A';son[c-'A']=a-'A'; }while(m--){cin>>x>>y;int ans=Find(x-'A',y-'A');if(ans==0){ans=Find(y-'A',x-'A');if(ans==0) cout<<"-"<<endl;else if(ans==1){cout<<"child"<<endl;}else{for(int i=0;i<ans-2;i++) cout<<"great-";cout<<"grandchild"<<endl;}}else{if(ans==1) cout<<"parent"<<endl;else {for(int i=0;i<ans-2;i++) cout<<"great-";cout<<"grandparent"<<endl;}}}
}ex11.2 连通图分支数
#include <bits/stdc++.h>
using namespace std;
const int N=1000010;
int father[N];
int height[N];
bool vis[N];void init()
{for(int i=0;i<N;i++){father[i]=i;height[i]=0;}
}
int Find(int x)
{if(x!=father[x])father[x]=Find(father[x]);return father[x];
}
void Union(int x,int y)
{int fx=Find(x);int fy=Find(y);if(fx!=fy){if(height[fx]<height[fy]) father[fx]=fy;else if(height[fx]>height[fy]) father[fy]=fx;else{father[fy]=fx;height[fx]++;}}return;
}
int main()
{int x,y;memset(vis,false,sizeof vis);init();while(cin>>x>>y){Union(x,y);vis[x]=true;vis[y]=true;}int res=0;for(int i=1;i<N;i++){if(Find(i)==i&&vis[i]) res++;}cout<<res<<endl; return 0;
} ex11.3 Head of a Gang
#include <bits/stdc++.h>using namespace std;
const int N=26;
int father[N];
int height[N];
int phone[N];
void init()
{for(int i=0;i<N;i++){father[i]=i;height[i]=0;phone[i]=0;}
}
int find(int x)
{if(x!=father[x])father[x]=find(father[x]);return father[x];
}
void Union(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy){if(height[fx]<height[fy]) father[fx]=fy;else if(height[fy]<height[fx]) father[fy]=fx;else{father[fy]=fx;height[fx]++;}}
}
int countFather(int x)//查询每个连通分支的结点数目
{int count=0;for(int i=0;i<N;i++){if(find(x)==find(i))count++;}return count;
}
int main()
{int num,weight;string a,b;int numa,numb,minute;while(cin>>num>>weight){map<int,int> result;map<int,string> m;init();while(num--){cin>>a>>b>>minute;numa=a[0]-'A';numb=b[0]-'A';m[numa]=a;m[numb]=b;phone[numa]+=minute;phone[numb]+=minute;Union(numa,numb);}for(int i=0;i<N;i++){if(find(i)==i&&countFather(i)>2)//帮派是超过2个人的群集 {int sumWeight,maxWeight,maxIndex;sumWeight=0;maxWeight=0;maxIndex=0;for(int j=0;j<N;j++){if(find(j)==i)//搜索属于该点连通分支的结点 {sumWeight+=phone[j];if(phone[j]>maxWeight){maxWeight=phone[j];maxIndex=j;} } } sumWeight/=2;if(sumWeight>weight) result[maxIndex]=countFather(i); }}cout<<result.size()<<endl;map<int,int>::iterator it;for(it=result.begin();it!=result.end();it++){cout<<m[it->first]<<" "<<it->second<<endl;}}}补充深度优先搜索
ex9.3 A Knight's Journey
//dfs深度优先搜索
#include <bits/stdc++.h>
using namespace std;
const int N=30;
int p,q;
bool vis[N][N];
int dx[8]={-1,1,-2,2,-2,2,-1,1};
int dy[8]={-2,-2,-1,-1,1,1,2,2};bool dfs(int x,int y,int step,string ans)
{if(step==p*q)//走遍了棋盘每个坐标 {cout<<ans<<endl<<endl;return true;}else{for(int i=0;i<8;i++){int nx=x+dx[i];int ny=y+dy[i];char col=ny+'A';char row=nx+'1';if(nx<0||nx>=p||ny<0||ny>=q||vis[nx][ny]) continue;//越界或者已经访问过了 vis[nx][ny]=true;//进行标记 if(dfs(nx,ny,step+1,ans+col+row))return true;vis[nx][ny]=false;//恢复现场 }}return false;
}
int main()
{int n;scanf("%d",&n);int caseNumber=0;while(n--){scanf("%d%d",&p,&q);memset(vis,false,sizeof(vis));//记得初始化vis数组 cout<<"Scenario #"<<++caseNumber<<":"<<endl;vis[0][0]=true;if(!dfs(0,0,1,"A1")){cout<<"impossible"<<endl<<endl; } } return 0;
} ex9.4 Square
#include <bits/stdc++.h>
using namespace std;
const int N=25;
int side;//边长
int m;//树枝数目
int sticks[N];
bool vis[N];bool cmp(int x,int y)
{return x>y;
}
bool dfs(int sum,int number,int position)
//sum是当前拼凑的木棍长度,number是已经拼凑成边长的数量,position是当前木棍的编号
{if(number==3) return true;for(int i=position;i<m;i++){if(vis[i]||sum+sticks[i]>side) continue;vis[i]=true;//木棍已经被用过 if(sum+sticks[i]==side){if(dfs(0,number+1,0)) return true;}else{if(dfs(sum+sticks[i],number,i+1)) return true;}vis[i]=false;//恢复现场 }return false;
}
int main()
{int n;scanf("%d",&n);while(n--){int length=0;cin>>m;for(int i=0;i<m;i++){cin>>sticks[i];length+=sticks[i];}memset(vis,false,sizeof vis);if(length%4!=0) {cout<<"no"<<endl;continue;}side=length/4;sort(sticks,sticks+m,cmp);if(sticks[0]>side){cout<<"no"<<endl;continue;}if(dfs(0,0,0)) cout<<"yes"<<endl;else cout<<"no"<<endl; }return 0;
}11.3最小生成树
kruskal算法的步骤是：
1.初始时所有顶点属于孤立的集合
2.按照边权递增顺序遍历所有边，若遍历到的边的两个顶点仍然分属不同的集合，则确定该边为最小生成树上的一条边，并将该边两个顶点分属的集合合并。
3.遍历完所有边后，若原图连通，则被选取的边和所有顶点构成最小生成树。若原图不连通，最小生成树不存在。
ex11.4 还是畅通工程(浙江大学复试上机题）
#include <bits/stdc++.h>using namespace std;
const int N=100;
struct Edge
{int from,to,length;
};
bool cmp(Edge e1,Edge e2)
{return e1.length<e2.length;
}
Edge edge[N*N];
int father[N];
int height[N];
void init(int n)
{for(int i=0;i<n;i++){father[i]=i;height[i]=0; }
}
int find(int x)
{if(x!=father[x])father[x]=find(father[x]);return father[x];
}
void Union(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy){if(height[fx]<height[fy]) father[fx]=fy;else if(height[fy]<height[fx]) father[fy]=fx;else{father[fy]=fx;height[fx]++;}}
}
int kruskal(int n,int edgeNumber)
{init(n);sort(edge,edge+edgeNumber,cmp);int sum=0;for(int i=0;i<edgeNumber;i++){Edge cur=edge[i];if(find(cur.from)!=find(cur.to)) {Union(cur.from,cur.to);sum+=cur.length; }}return sum;
}
int main()
{int n;while(cin>>n){if(n==0) break;for(int i=0;i<n;i++) cin>>edge[i].from>>edge[i].to>>edge[i].length;int edgeNumber=n*(n-1)/2;int res=kruskal(n,edgeNumber);cout<<res<<endl;}return 0;
}ex11.5 继续畅通工程（浙江大学复试上机题）
//还是畅通工程
#include <bits/stdc++.h>using namespace std;
const int N=100;
struct Edge{int from,to,length;
};
bool cmp(Edge e1,Edge e2)
{return e1.length<e2.length;
}
int father[N];
int height[N];
Edge edge[N*N];
void init(int n)
{for(int i=0;i<=n;i++){father[i]=i;height[i]=0;}
}
int find(int x)
{if(x!=father[x])father[x]=find(father[x]);return father[x];
}
void Union(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy){if(height[fx]<height[fy]) father[fx]=fy;else if(height[fy]<height[fx]) father[fy]=fx;else{father[fy]=fx;height[fx]++;}}
}
int kruskal(int n,int edgeNumber)
{init(n);int sum=0;sort(edge,edge+edgeNumber,cmp);for(int i=0;i<edgeNumber;i++){Edge cur=edge[i];if(find(cur.from)!=find(cur.to)){Union(cur.from,cur.to);sum+=cur.length;}}return sum;
}
int main()
{ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0);int n;while(cin>>n){if(n==0) break;int edgeNumber=n*(n-1)/2;int status;for(int i=0;i<edgeNumber;i++) {cin>>edge[i].from>>edge[i].to>>edge[i].length>>status;if(status==1) edge[i].length=0;}int res=kruskal(n,edgeNumber);cout<<res<<endl; }return 0;
}ex11.4 Freckles(北京大学复试上机题）
（并查集的细节以及点到边的转换小细节非常多）
//Freckles
#include <bits/stdc++.h>
using namespace std;
const int N=100;
struct Point{double x,y;
};
struct Edge{int from,to;double length;
};
int father[N];
int height[N];
Point point[N];
Edge edge[N*N];
bool cmp(Edge e1,Edge e2)
{return e1.length<e2.length;
}
void init(int n)
{for(int i=0;i<=n;i++){father[i]=i;height[i]=0; }
}
int find(int x)
{if(x!=father[x])father[x]=find(father[x]);return father[x];
}
void Union(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy){if(height[fx]<height[fy]) father[fx]=fy;else if(height[fy]<height[fx]) father[fy]=fx;else{father[fy]=fx;height[fx]++;}}
}
double kruskal(int n,int edgeNumber)
{init(n);double sum=0.0;sort(edge,edge+edgeNumber,cmp);for(int i=0;i<edgeNumber;i++){Edge cur=edge[i];if(find(cur.from)!=find(cur.to)){Union(cur.from,cur.to);sum+=cur.length;}} return sum;
}
int main()
{ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0);int n;while(cin>>n){if(n==0) break;int edgeNumber=n*(n-1)/2;for(int i=1;i<=n;i++) cin>>point[i].x>>point[i].y;int k=0;for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){edge[k].from=i;edge[k].to=j;edge[k].length=sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-point[j].y));k++;}}double res=kruskal(n,edgeNumber);printf("%.2lf\\n",res);}return 0;
} ex11.5 Jungle Roads
//Jungle Roads考查最小生成树以及字符串的处理
#include <bits/stdc++.h>
using namespace std;
const int N=100;
struct Edge{int from,to,length;
};
int father[N];
int height[N];
Edge edge[N*N];
bool cmp(Edge e1,Edge e2)
{return e1.length<e2.length;
}
void init(int n)
{for(int i=0;i<=n;i++){father[i]=i;height[i]=0;}
}
int find(int x)
{if(x!=father[x])father[x]=find(father[x]);return father[x];
}
void Union(int x,int y)
{int fx=find(x);int fy=find(y);if(fx!=fy){if(height[fx]<height[fy]) father[fx]=fy;else if(height[fy]<height[fx]) father[fy]=fx;else{father[fy]=fx;height[fx]++;}}
}
int kruskal(int n,int edgeNumber)
{init(n);int sum=0;sort(edge,edge+edgeNumber,cmp);for(int i=0;i<edgeNumber;i++){Edge cur=edge[i];if(find(cur.from)!=find(cur.to)){Union(cur.from,cur.to);sum+=cur.length;}}return sum;
}
int main()
{ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0);int n;int num,dis;char c1,c2;while(cin>>n){if(n==0) break;int edgeNumber=n*(n-1)/2;int k=0; for(int i=0;i<n-1;i++){cin>>c1>>num;for(int j=0;j<num;j++){cin>>c2>>dis;edge[k].from=c1-'A'+1;edge[k].to=c2-'A'+1;edge[k].length=dis;k++; } }int res=kruskal(n,edgeNumber);cout<<res<<endl;}return 0;
} 最短路径问题：Dijkstra算法在运行过程中将顶点集合V分成两个集合S和T
S是已确定的顶点集合，初始只含源点s
T=V-S表示尚未确定的顶点集合
算法反复从集合T中选择当前到源点s最近的顶点u，将u加入集合S，然后对所有从u发出的边进行松弛操作
eg11.6 畅通工程续（浙江大学复试上机题）
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N=200;
const int INF=INT_MAX;
struct Edge{int to,length;Edge(int t,int l):to(t),length(l){}
};
struct Point{int number,distance;Point(int n,int d):number(n),distance(d){}bool operator<(const Point& p) const{return distance>p.distance; }
};
vector<Edge> graph[N];//用邻接表存储图
int dis[N];
void Dijkstra(int s)
{priority_queue<Point> mq;dis[s]=0;mq.push(Point(s,dis[s]));while(!mq.empty()){int u=mq.top().number;mq.pop();for(int i=0;i<graph[u].size();i++){int v=graph[u][i].to;int d=graph[u][i].length;if(dis[v]>dis[u]+d){dis[v]=dis[u]+d;mq.push(Point(v,dis[v]));}}}return;
}
int main()
{int n,m;while(cin>>n>>m){memset(graph,0,sizeof graph);fill(dis,dis+n,INF);while(m--){int from,to,length;cin>>from>>to>>length;graph[from].push_back(Edge(to,length));graph[to].push_back(Edge(from,length));}int s,t;cin>>s>>t;Dijkstra(s);if(dis[t]==INF) cout<<"-1"<<endl;else cout<<dis[t]<<endl;}return 0;
}eg11.7 最短路径问题（浙江大学复试上机题）图的边上还带有价格这一变量
#include <bits/stdc++.h>
using namespace std;
const int N=1000;
const int INF=INT_MAX;
struct Edge{int to,length,price;Edge(int t,int l,int p):to(t),length(l),price(p){}
};
struct Point{int number,distance;Point(int n,int d):number(n),distance(d){}bool operator<(const Point& p)const{return distance>p.distance;//距离短的优先级大 }
};
vector<Edge> graph[N];
int dis[N];
int price[N];
void Dijkstra(int s)
{priority_queue<Point> mq;dis[s]=0;price[s]=0;mq.push(Point(s,dis[s]));while(!mq.empty()){int u=mq.top().number;mq.pop();for(int i=0;i<graph[u].size();i++){int v=graph[u][i].to;int d=graph[u][i].length;int p=graph[u][i].price;if((dis[v]>dis[u]+d)||(dis[v]==dis[u]+d&&price[v]>price[u]+p)){dis[v]=dis[u]+d;price[v]=price[u]+p;mq.push(Point(v,dis[v]));}}} return;
}
int main()
{ios_base::sync_with_stdio(0);cin.tie(0),cout.tie(0); int n,m;while(cin>>n>>m){if(n==0&&m==0) break;memset(graph,0,sizeof graph);fill(dis,dis+n+1,INF);fill(price,price+n+1,INF); while(m--){int a,b,d,p;cin>>a>>b>>d>>p;graph[a].push_back(Edge(b,d,p));graph[b].push_back(Edge(a,d,p));}int s,t;cin>>s>>t;Dijkstra(s);if(dis[t]==-1) cout<<"-1"<<endl;else cout<<dis[t]<<" "<<price[t]<<endl;}return 0;
}ex11.6 最短路径（上海交通大学复试上机题）
ex11.7 I Wanna Go Home（北京大学复试上机题）
