最近在总结图的有关算法，参考了一些博客，然后自己实现了一遍，汇总如下：
概念就不多总结了
1.有向无环图的拓扑排序
基本思路：
假设我们先统计了边的对应关系邻接表edge，以及对应每个node的入度数组in，并且因为是bfs来进行，使用queue来辅助，那么按照之前说的
1.先遍历in数组，选取一个入度为0的节点进queue
2.while(!myqueue.emepty())的情况下一直进行遍历，对于当前取到的node，我们遍历相连关系数组edge，找到所有相连的node,in数组中node相应的入度-1，同时判断如果这个node的入度已经为0了，进queue
3.记住，最终我们要判断ans和node节点个数的关系，如果不相等，说明出现了环，是不可能得到一个拓扑排序序列的
#include <bits/stdc++.h>
using namespace std;
int main(){
int v,e; //分别为顶点数+输入边的个数
cout<<"number of the nodes: "<<endl;
cin>>v;
cout<<"number of the edges: "<<endl;
cin>>e;
//现在开始初始化一个map
vector<vector<int>> map(v,vector<int>(v,0));
cout<<"please input the relations of the edges: "<<endl;
int a,b; //分别表示输入的两项，并且由于是有向图，指向为map[a][b],构建这个关系
for(int i=0;i<e;++i){
cin>>a>>b;
map[a][b]=1;
}
//可以打印这个邻接矩阵来看一下
cout<<"the realations of the edges: "<<endl;
cout<<endl;
for(int i=0;i<v;++i){
for(int j=0;j<v;++j){
cout<<map[i][j]<<" ";
}
cout<<endl;
}
//统计每个节点的入度
vector<int> in(v,0);
for(int i=0;i<v;++i){
for(int j=0;j<v;++j){
if(map[i][j]){ //i->j，因此j的入度应该+1
in[j]++;
}
}
}
//queue辅助，bfs遍历，先进一个入度为0的点
queue<int> Q;
for(int i=0;i<v;++i){
if(in[i]==0){
Q.push(i);
}
}
vector<int> res; //存储最终结果
while(!Q.empty()){
int cur=Q.front();
Q.pop();
res.push_back(cur);
in[cur]=-1; //注意对应当前节点使用过了，入度设置为-1
for(int i=0;i<v;++i){
if(map[cur][i]==1){ //具有相邻关系的点我们将其入度-1
in[i]--; //入度-1
if(in[i]==0){
Q.push(i);
}
}
}
}
if(res.size()<v){ //此时说明其中有一个地方存在环了，拓扑排序是不成功的
cout<<"can not sort the nodes!"<<endl;
return 0;
}
//否则我们按序打印即可
cout<<endl;
cout<<"the result after the sort: "<<endl;
for(auto it:res){
cout<<it<<" ";
}
system("pause");
return 0;
} 最小生成树
2.Prim算法
我们的基本思路如下：
1.先进行初始化,根据输入的行与列来进行二维数组初始化，此时i==j的时候为0，i!=j的时候我们设置成一个极大值表示不连通 2.进行边的对应关系输入，进行对应两个顶点之间的权值更新 3.此时开始我们的主程序，也就是Prim的过程 （1）我们要用到两个数组，一个是visit数组表示每个点是否已经取过了，假设我们先选取一个点i作为起点，另一个是dis数组，表示当前点到各个其他点的距离 （2）此时遍历完之后我们已经找到一个距离当前i点距离最近的点j，那么我们此时将j同样进行树的生成，并且此时，我们要更新dis数组，因为此时j也是树的一部分 ，每个点距离树的距离可能变小 （3）循环往复，直到我们取到了所有点，生成了一颗最小的树
int main(){
int n,m;
cout<<"input the number of the nodes: "<<endl;
cin>>n;
cout<<"input the number of the edges: "<<endl;
cin>>m;
//此时我们根据n个顶点先初始化一个关系数组
vector<vector<int>> vec(n,vector<int>(n,INT_MAX));
for(int i=0;i<n;++i){ //权值更新，自身为0，其余为一个INT_MAX
vec[i][i]=0;
}
cout<<"input the relations of the edges: "<<endl;
//根据每条边输入的权值进行更新，注意是无向图，因此两个方向都要更新
int a,b,value;
for(int i=0;i<m;++i){ //总共m条边的对应关系
cin>>a>>b>>value;
vec[a][b]=value;
vec[b][a]=value;
}
//假设我们取第一个节点作为起始点
int sum=0; //记录生成树的权值
int cnt=0; //记录访问了多少个节点了
vector<int> dis(n,INT_MAX); //记录每个点到树的权值距离
vector<int> visit(n,0); //0表示未访问过
vector<pair<int,int>> res; //结果数组，记录每次取的节点以及对应权值
visit[0]=1; //标记为已访问
//因为选成了树的节点，因此更新一波距离
for(int i=0;i<n;++i){
dis[i]=vec[0][i];
}
res.push_back({0,dis[0]}); //输入的是节点以及对应权值
cnt++;
while(cnt!=n){
int min_dis=INT_MAX,idx=0; //目标要选取当前dis中最小的那个节点
for(int i=0;i<n;++i){
if(visit[i]==0 && dis[i]<min_dis){
min_dis=dis[i];
idx=i;
}
}
visit[idx]=1; //选定的节点进行访问并入res
res.push_back({idx,min_dis});
sum+=min_dis;
cnt++;
//因此此时idx变为一部分，因此再更新一遍权值
for(int i=0;i<n;++i){
if(visit[i]==0 && dis[i]>vec[idx][i]){
dis[i]=vec[idx][i];
}
}
}
//到目前为止完成Prim算法，我们打印一遍结果来看一下
cout<<"the result sum is: "<<sum<<endl;
cout<<"the nodes are as below: "<<endl;
for(int i=0;i<res.size();++i){
cout<<"the"<<i<<"th node is: "<<res[i].first<<" "<<"the value is: "<<res[i].second<<endl;
}
system("pause");
return 0;
} 3.Kruskal
Kruskal与Prim的不同是，之前我们是不断的每次取一个点之后都要进行距离更新，然后取距离最短的。那现在我们在开始时进行一次距离的更新，依次来进行选取，在每次取得一个点之后，我们不再进行权值的更新。此时为了我们取对应长度最小的边较为方便，考虑使用vector>>的结构来存储，分别为x,y,value 我们此时需要的辅助函数为并查集的查找以及合并
vector<int> pre; //用于并查集的查找
int find(int x){
if(pre[x]==x){
return x;
}
pre[x]=find(pre[x]); //否则的话我们进行并查集的查找
return pre[x];
}
int merge(int x,int y){
int t1=find(x);
int t2=find(y);
if(t1!=t2){ //如果两个并不是相连的，我们修改状态为相连，并返回1
pre[t2]=t1;
return 1;
}
return 0;
}
int main(){
int n,m; //同样我们要先进行对应关系初始化，总共n个节点，m条边的关系
cout<<"input the number of the nodes: "<<endl;
cin>>n;
cout<<"input the number of the edges: "<<endl;
cin>>m;
vector<pair<int,pair<int,int>>> vec; //存储对应关系
int x,y,value;
cout<<"input the relations of the edges: "<<endl;
for(int i=0;i<m;++i){
cin>>x>>y>>value;
vec.push_back({x,{y,value}});
}
//我们要根据value值进行从小到大排序
auto cmp=[](const pair<int,pair<int,int>>&a,const pair<int,pair<int,int>>& b){
return a.second.second<b.second.second;
};
sort(vec.begin(),vec.end(),cmp);
//pre数组进行初始化
for(int i=0;i<n;++i){
pre.push_back(i);
}
vector<pair<int,pair<int,int>>> res; //存储最终的结果
int sum=0; //存储最终的权值之和
int cnt=0; //记录当前访问了多少条边，到m-1的时候退出循环，完成了构建
//我们此时根据每条边来进行列举
for(int i=0;i<m;++i){
int x=vec[i].first;
int y=vec[i].second.first;
int value=vec[i].second.second;
if(merge(x,y)){
cnt++;
sum+=value;
res.push_back({x,{y,value}}); //存储对应的x,y,value
}
if(cnt==m-1){ //已经取得了m-1条边的话退出
break;
}
}
cout<<"the result sum: "<<sum<<endl;
cout<<"the select nodes are as below: "<<endl;
for(int i=0;i<res.size();++i){
cout<<"the "<<i<<"th of the edges"<<res[i].first<<"->"<<res[i].second.first<<" ";
cout<<"the value is: "<<res[i].second.second<<endl;
}
system("pause");
return 0;
} 最短路径Dijkstra
Dijkstra最短路径
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
####注意这里与Prim的区别，同样是计算距离，但是Prim是计算点到树的距离，因此每次求一遍过后需要更新，而Dijkstra是求点到源点的距离，因此也要更新，但仍然是更新到源点的距离
//Dijkstra算法
/*
我们这样考虑：
使用distance作为距离数组统计每个节点到源点的记录
使用s和v分别存储对应取得的节点信息，以及未被选取的节点的信息
使用flag来标记每一个节点是否进行使用过
1.先进行对应关系的建立，同样可以选择无向图，那么邻接矩阵即可
2.选取一个点i作为源点，那么我们先进行每个节点到当前源点的距离统计，选取距离最小的节点。
此后进行距离的更新，注意，在这里与Prim不同的是，我们更新的是点到源点的距离（因此新选取的点只能作为一个中间板）
3.如此往复直到选取得到i个节点完毕
*/
int main(){
int n,m;
int max_dis=9999;
cout<<"input the number of the nodes: "<<endl;
cin>>n;
cout<<"input the number of the edges: "<<endl;
cin>>m;
vector<vector<int>> vec(n,vector<int>(n,max_dis=9999));
for(int i=0;i<n;++i){
vec[i][i]=0; //自身先修改成0
}
cout<<"input the relations of the edges: "<<endl;
int a,b,value; //分别为输入的a,b以及对应的距离长度value
for(int i=0;i<m;++i){
cin>>a>>b>>value;
vec[a][b]=value;
vec[b][a]=value; //无向图距离正反都需要更新
}
//打印一下邻接矩阵看一下
cout<<"the matrix of the nodes are as below: "<<endl;
for(int i=0;i<n;++i){
for(int j=0;j<n;++j){
cout<<vec[i][j]<<" ";
}
cout<<endl;
}
//现在来进行Dijkstra的核心部分
vector<pair<int,int>> s; //已经使用的节点，分别为node和dis
vector<pair<int,int>> v; //未被使用的节点，分别为node和dis
vector<int> dis(n,max_dis); //对应的距离矩阵
vector<int> flag(n,false); //标记节点是否访问过了
//我们选取第0个点作为源点
int pos=3;
int cnt=0; //表明当前选取了几个节点
flag[pos]=true;
s.push_back({pos,0}); //作为已经访问，进入s存储
//更新距离矩阵
for(int i=0;i<n;++i){
dis[i]=vec[pos][i];
}
//现在我们找一遍dis，选取距离最短的进行记录，之后再往复进行距离的更新
for(int i=0;i<n;++i){
if(flag[i]==false){
v.push_back({i,dis[i]}); //对应点记录为未访问
}
}
cnt++;
auto cmp=[](const pair<int,int>&a ,const pair<int,int>& b){ //根据距离从小到大排序
return a.second<b.second;
};
while(cnt!=n){
sort(v.begin(),v.end(),cmp);
int cur=v[0].first; //这是我们目前能够得到的距离最小的node的坐标
cnt++;
s.push_back({cur,v[0].second}); //记录到s中,此时的距离为dis[cur]
v.erase(v.begin());
//需要进行到源点距离的更新
for(int i=0;i<n;++i){
if(dis[i]>(dis[cur]+vec[i][cur])){ //使用中间板如果距离小了，进行更新，cur作为中间板
dis[i]=dis[cur]+vec[i][cur];
for(auto it=v.begin();it!=v.end();++it){
if(it->first==i){
it->second=dis[i]; //v中的距离需要更新
break;
}
}
}
}
flag[cur]=true; //标记为已访问
}
//现在s中应该有n个节点信息，输出一下check一下
cout<<"-----------------------"<<endl;
cout<<"after the Dijkstra operation, the result is as below: "<<endl;
for(int i=0;i<s.size();++i){
cout<<"the node is: "<<s[i].first<<" "<<"the distance is: "<<s[i].second<<endl;
}
system("pause");
return 0;
}
京公网安备 11010502036488号