一、主要内容：
介绍图论中两大经典问题：最小生成树问题以及最短路径问题，以及给出解决每个问题的两种不同算法。
其中最小生成树问题可参考以下题目：
题目1012：畅通工程 http://ac.jobdu.com/problem.php?pid=1012
题目1017：还是畅通工程 http://ac.jobdu.com/problem.php?pid=1017
题目1024：畅通工程 http://ac.jobdu.com/problem.php?pid=1024
题目1028：继续畅通工程 http://ac.jobdu.com/problem.php?pid=1028
其中最短路径问题可参考一下题目：
题目1447：最短路 题目链接：http://ac.jobdu.com/problem.php?pid=1447
题目1008：最短路径问题 题目链接：http://ac.jobdu.com/problem.php?pid=1008
二、最小生成树与最短路径的定义与区别
带权图分为有向图和无向图。
无向图的最短路径又叫做最小生成树，有prime算法（普里姆算法）和kruskal算法（克鲁斯卡尔算法）；
有向图的最短路径算法有floyd算法（弗洛伊德算法）和dijkstra算法（迪杰斯特拉）。
生成树的概念：连通图G的一个子图如果是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的极小连通子图。所谓极小是指：若在树中任意增加一条边，则 将出现一个回路；若去掉一条边，将会使之变成非连通图。生成树各边的权值总和称为生成树的权。
权最小的生成树称为最小生成树，常用的算法有prime算法和kruskal算法。
最短路径问题旨在寻找图中两节点之间的最短路径，常用的算法有：floyd算法和dijkstra算法。
三、构造最小生成树的算法
构造最小生成树一般使用贪心策略，有prime算法和kruskal算法。
prime算法的基本思想：
1. 清空生成树，任取一个顶点加入生成树
2. 在那些一个端点在生成树里，另一个端点不在生成树里的边中，选取一条权最小的边，将它和另一个端点加进生成树
3. 重复步骤2，直到所有的顶点都进入了生成树为止，此时的生成树就是最小生成树.
int prime(int cur)
{
int index = cur;
int sum = ;
memset(visit, false, sizeof(visit));
visit[cur] = true;
for(int i = ; i < m; i ++){
dist[i] = graph[cur][i];
} for(int i = ; i < m; i ++){ int mincost = INF;
for(int j = ; j < m; j ++){
if(!visit[j] && dist[j] < mincost){
mincost = dist[j];
index = j;
}
} visit[index] = true;
sum += mincost; for(int j = ; j < m; j ++){
if(!visit[j] && dist[j] > graph[index][j]){
dist[j] = graph[index][j];
}
}
}
return sum;
}
Prime 算法
kruskal算法的基本思想：
1. 首先我们把所有的边按照权值先从小到大排列；
2. 接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。
其中用到了数据结构中的并查集。有关并查集的操作可以参考博客 http://blog.csdn.net/luomingjun12315/article/details/47373345
kruskal算法讲解推荐博客 http://www.cnblogs.com/skywang12345/p/3711500.html#anchor6
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
#define MAX_SIZE 1010 using namespace std; int n, m;
int Tree[MAX_SIZE]; int findRoot(int x){//find the root of x
if(Tree[x]==-) return x;
else{
int tmp = findRoot(Tree[x]);//continue the find
Tree[x] = tmp;//change the root of x to tmp
return tmp;
} }
int main(){
while(scanf("%d",&n)!=EOF && n!=){//when n==0 and jump out of the loop
scanf("%d",&m);
for(int i = ; i <= n ; i++)//init
Tree[i] = -; while(m--){
int a,b;
scanf("%d%d",&a,&b);
a = findRoot(a);//find the root of a
b = findRoot(b);//find the root of b
if(a!=b) Tree[a]=b;//merge those two sets to the same aggregates
} int ans = ;
for(int i = ; i <= n ; i++){
if(Tree[i]==-) ans++;//calculate the total numbers of aggregates
}
printf("%d\n",ans-);
}
return ;
}
kruskal 算法
四、最短路径算法
最短路径问题旨在寻找图中两节点之间的最短路径，常用的算法有：floyd算法和dijkstra算法。
floyd算法是最简单的最短路径算法，可以计算图中任意两点间的最短路径;
folyd算法的时间复杂度是O(N3),如果是一个没有边权的图，把相连的两点之间的距离设为dist[i][j] = 1，不相连的两点设为无穷大，用 floyd算法可以判断i,j两点是否有路径相连。
void floyd()
{
for(int k = ; k < n; k ++){ //作为循环中间点的k必须放在最外一层循环
for(int i = ; i < n; i ++){
for(int j = ; j < n; j ++){
if(dist[i][j] > dist[i][k] + dist[k][j]){
dist[i][j] = dist[i][k] + dist[k][j]; //dist[i][j]得出的是i到j的最短路径
}
}
}
}
}
Floyd 算法
dijkstra算法用来计算从一个点到其他所有点的最短路径的算法，复杂度O(N2)。
void dijkstra(int s) //s是起点
{
memset(visit, false, sizeof(visit));
visit[s] = true;
for(int i = ; i < n; i ++){
dist[i] = graph[s][i];
} int index;
for(int i = ; i < n; i ++){
int mincost = INF;
for(int j = ; j < n; j ++){
if(!visit[j] && dist[j] < mincost){
mincost = dist[j];
index = j;
}
}
visit[index] = true;
for(int j = ; j < n; j ++){
if(!visit[j] && dist[j] > dist[index] + graph[index][j]){
dist[j] = dist[index] + graph[index][j];
}
}
}
}
dijkstra 算法
五、图论大礼包