图的基本算法知识分享.ppt

图的基本算法目录图的基本概念图的基本概念图的表示方法邻接矩阵邻接表邻接表的实现最小生成树问题prim算法的基本思想intprim(ints)//s为初始加入的点
{
inti,j,sum=0;
for(i=1;i<=n;i++)
closest[i]=10000000;
for(i=1;i<=n;i++)
closest[i]=map[s][i];
closest[s]=0;
intnow;
for(i=1;i<n;i++)
{
intmin=INT_MAX;
for(j=1;j<=n;j++)
if(closest[j]&&closest[j]<min)
{
min=closest[j];
now=j;
}
sum+=min;
closest[now]=0;
for(j=1;j<=n;j++)
if(map[now][j]&&map[now][j]<closest[j])
closest[j]=map[now][j];
}
returnsum;
}kruskal算法的基本思想kruskal算法实现的数据结构并查集的处理过程·MST-KRUSKAL(G,w)
1.A←Ф
2.for每个结点v∈V[G]
3.doMAKE-SET(v)
4.根据权w的非递减顺序对E的边进行排序
5.for每条边(u,v)∈E，按权的非递减次序
6.doifFIND-SET(u)≠FIND-SET(v)
7.thenA←A∪{(u,v)}
8.UNION(u,v)
9.returnA
复杂度E*logE
例题POJ3522思路：练习最短路问题单源最短路径松弛技术Bellman-Ford算法
对bellman-ford算法的说明：
如果没有负权回路，运行一次bellmanford算法，将得到源点到任意点的最短路：
由于源点到任意一点至多n-1条边，我们经过n-1次循环，每重循环对所有的边进行松弛，能保证每次至少得到一个d[i]，其值为源点到i点的最短路，最终n-1次循环之后就能求得所有的d[i]。

如果包含负权回路，那么n-1次循环之后还会存在点u，v，使得d[v]>d[u]+w[u,v]，这样我们就能判断是否存在负权回路。例题：POJ3259题目分析：此题题意是判断有向图中是否存在负权回路，怎样构造图呢？对于双向路径(u,v),可以构造成两条边(u,v,t)和(v,u,t)，对于虫洞单向路径(u,v)，可以构造一条边(u,v,-t)，这样运行bellman-ford算法就可以判断出是否存在负权回路。
代码附后

Dijkstra算法算法执行过程intdijkstra(ints,intn)
{
inti,j;
intv[MAX];
intd[MAX];
for(i=1;i<=n;i++)
d[i]=map[1][i];
v[1]=1;
for(i=1;i<n;i++)
{
intnow,min=INT_MAX;
for(j=1;j<=n;j++)//选最小的加入集合
{
if(!v[j]&&min>d[j])
{
min=d[j];
now=j;
}
}
v[now]=1;
for(j=1;j<=n;j++)//松弛
if(!v[j]&&d[now]+map[now][j]<d[j])
d[j]=d[now]+map[now][j];
}
return0;
}spfa算法例题：看晴子大牛的体型
知道他一定又馋又懒，他有n-1个小弟，每天都让他的n-1个小弟去n-1个不同的饭馆给他买回山珍海味，已知饭馆之间是以有向图连接起来的，我们可以保证每两个饭馆之间可以互相可达，问他的小弟帮他买回饭来总共走的最短路程是多少（假设晴子大牛所在顶点为点1，饭馆为2~n）？n<=m<=1000000由于数据范围很大，Dijkstra算法和Bellman-Ford超时，我们可以用spfa算法求得由点1到其他点的距离，那么怎么求从其他点到点1的距离呢？
我们可以把每条有向边反向，这样再用spfa在反向的图中求一次源点到其他的点的距离就求出了从每个点到源点的距离。
代码附后单源最短路问题小结每对顶点的最短路径floyd-washall算法的基本思想递推过程----动态规划floyd计算图的传递闭包例题：POJ1975拓扑排序拓扑排序晴子大牛穿衣服的例子课后练习题Relax(u,v){
IfF(v)>F(u)+W_Cost(u,v)then
F(v)=F(u)+W_Cost(u,v);
}SPFA则使用队列进行了优化！ 在上图的例子中，每个节点只进队一次，
只需N次运算。
相比Be