考研复习（9）-图的应用

1.最小生成树-普林姆算法
复杂度O（n^2）,适合稠密图
#include <iostream>
#include <fstream>
#include <climits>


using namespace std;
const int maxn=101;
void prim(int n,int dist[maxn],int map[maxn][maxn],int pre[maxn])
{
int i,j,k;
int min;
bool p[maxn];
for(i=2;i<=n;i++)
{
p[i]=false;
dist[i]=map[1][i];


}
dist[1]=0;
p[1]=true;


for(i=1;i<=n-1;i++)
{
min=INT_MAX;
k=0;
for(j=1;j<=n;j++)
{
if(!p[j]&&dist[j]<min)
{
min=dist[j];
k=j;
}
}
if(k==0) return;
p[k]=true;


for(j=1;j<=n;j++)
if(!p[j]&&map[k][j]!=INT_MAX&&dist[j]>map[k][j])
{
dist[j]=map[k][j];
pre[j]=k;
}
}


}
int main()
{
int n,m;
int a,b,w;
int map[maxn][maxn];
int dist[maxn];
int pre[maxn];
int sum=0;
int i,j;


freopen("input.txt","r",stdin);
cin>>n>>m;
for(i=1;i<=n;i++)
{
pre[i]=1;
for(j=1;j<=n;j++)
{
//if(i-j) map[i][j]=INT_MAX;
//else map[i][j]=0;
map[i][j]=INT_MAX;
}
}
for(i=1;i<=m;i++)
{
cin>>a>>b>>w;
if(w<map[a][b])//deal with the repeated edge
{
map[a][b]=w;
//map[b][a]=w;//for no-orient graph
}
}
prim(n,dist,map,pre);
for(i=1;i<=n;i++)
{
if(dist[i]==INT_MAX)
{
cout<<"Can't form a mini-spanning tree!"<<endl;
return 0;
}
sum+=dist[i];
}
cout<<sum<<endl;
for(i=2;i<=n;i++) cout<<pre[i]<<"----"<<i<<endl;
cout << "Hello world!" << endl;
return 0;
}
/*difference between prim arithmetic and dijkstra arithmetic:Prim's Greedy-heart content is finding the shortest edge and union it to solution-set.Dijkstra's Greedy-heart content is findng the shortest path to the source node and union it to solution-set.

The purpose and relax content is also different.*/

2.最小生成树-克鲁斯卡尔算法
复杂度O（n^2）,适合稀疏图
#include <iostream>
#include <algorithm>
#include <fstream>
using namespace std;
const int maxn=1010;//the number of node
const int maxe=100010;//the number of edge
//union and find set
struct node
{
int parent;
int depth;
}UFSTree[maxn];
struct enode
{
int a,b;//from....to...
int w;//weight
bool select;
}edge[maxe];
int find(int x)
{
if(UFSTree[x].parent!=x)
{
UFSTree[x].parent=find(UFSTree[x].parent);
}
return UFSTree[x].parent;
}
void merge(int x,int y)
{
int p,q;
p=find(x);
q=find(y);
if(p!=q)
{
if(UFSTree[p].depth>UFSTree[q].depth) UFSTree[q].parent=p;
else
{
UFSTree[p].parent=q;
if(UFSTree[p].depth==UFSTree[q].depth) UFSTree[q].depth++;
}
}
}
bool cmp(enode a,enode b)
{
if(a.w!=b.w) return a.w<b.w;
if(a.a!=b.b) return a.a<b.a;
return a.b<b.b;
}
void kruskal(enode *edge,int n,int m)
{
int k=0;//edge counter
int i,x,y;
sort(edge+1,edge+1+m,cmp);//sort edges by edge's weight at first


for(i=1;i<=m;i++)
{


if(k==n-1) break;
x=find(edge[i].a);
y=find(edge[i].b);
if(x!=y)
{
merge(x,y);
k++;
edge[i].select=true;
}
}


}
int main()
{
int i,n,m;
freopen("input.txt","r",stdin);
cin>>n>>m;
cout<<n<<m;
for(i=1;i<=m;i++)//init union&find set
{
UFSTree[i].parent=i;
UFSTree[i].depth=0;
}
for(i=1;i<=m;i++)
{
cin>>edge[i].a>>edge[i].b>>edge[i].w;
cout<<edge[i].a<<endl;
edge[i].select=false;
}
kruskal(edge,n,m);
for(i=0;i<=m;i++)
if(edge[i].select) cout<<edge[i].a<<' '<<edge[i].b<<' '<<edge[i].w<<endl;
cout << "Hello world!" << endl;
return 0;
}

//thought:A tipical greedy aruthmetic.The greedy purpose is to get the smallest edge from the rest of node to the solution-set if do not construct a circle as a result.

3。最短路-缔结思科啦算法
算单点的最短路，O（n^2）
#include <iostream>
#define INT_MAX 1000000
using namespace std;
const int maxn=1000;
void djk(int n,int dist[maxn],int map[maxn][maxn],int pre[maxn],int s)
{


int i,j,k;
int min;
bool p[maxn];
for(i=1;i<=n;i++)
{
p[i]=false;
if(i!=s) dist[i]=map[s][i];


}
dist[s]=0;
p[s]=true;


for(i=1;i<=n-1;i++)
{
min=INT_MAX;
k=0;
for(j=1;j<=n;j++)
{
if(!p[j]&&dist[j]<min)
{
min=dist[j];
k=j;


}
}


if(k==0) return;
if(i==1) pre[k]=s;
p[k]=true;
for(j=1;j<=n-1;j++)
{
if(!p[j]&&map[k][j]!=INT_MAX&&dist[j]>dist[k]+map[k][j])
{
dist[j]=dist[k]+map[k][j];//renew the distance of node j to the solution-set
pre[j]=k;
// cout<<j<<" :"<<dist[j]<<endl;
}
}


}


}
int main()
{
int i,j,s=2;
int n=6;
int dist[maxn]={0};
int pre[maxn]={0};
int map[maxn][maxn];
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) map[i][j]=INT_MAX;
for(i=1;i<=n;i++) map[i][i]=0;
map[1][2]=50;map[1][3]=10;
map[1][5]=45;map[2][3]=15;
map[2][4]=50;map[2][5]=10;
map[3][1]=20;map[3][4]=15;
map[4][2]=20;map[4][5]=35;
map[5][4]=30;map[6][4]=3;
djk(n,dist,map,pre,2);


for(j=1;j<=n;j++)
{
cout<<s<<"->"<<j<<": "<<dist[j]<<endl;
}
cout << "Hello world!" << endl;
return 0;

}

4.最短路-否罗衣得算法
复杂度O（n^3）
#include <iostream>
#include <climits>
#include <fstream>
#define INT_MAX 1000000000
using namespace std;
const int maxn=101;
void floyd(int n,int map[][maxn],int min[][maxn],int pre[][maxn])
{
int i,j,k;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
min[i][j]=map[i][j];
pre[i][j]=i;
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(k=1;k<=n;k++)
{
if(min[i][k]!=INT_MAX&&min[k][j]!=INT_MAX&&min[i][k]+min[k][j]<min[i][j])
{
min[i][j]=min[i][k]+min[k][j];
pre[i][j]=pre[k][j];
}
}
}
int main()
{
int n,m;
int a,b,w;
int map[maxn][maxn];
int min[maxn][maxn];
int pre[maxn][maxn];
int i,j;


freopen("input.txt","r",stdin);
cin>>n>>m;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i-j) map[i][j]=INT_MAX;
else map[i][j]=0;
}
}
for(i=1;i<=m;i++)
{
cin>>a>>b>>w;
if(w<map[a][b])//deal with the repeated edge
{
map[a][b]=w;
//map[b][a]=w;//for no-orient graph
}
}
floyd(n,map,min,pre);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++) cout <<i<<"->"<<j<<": "<<min[i][j]<<" ";
cout<<endl;
}
cout << "Hello world!" << endl;
return 0;
}
/*thought:A tipical Dp-question.The status transfer equation is map[i][j]=min{map[i,k]+map[k,j],map[i][j]}.So we just tranverse the edge between i and j.If fulfill the equation then relax the map[i][j];*/