图论算法_.ppt

ACM/ICPC程序设计图论-算法图的遍历BFS思想—遍历篇BFS程序基本结构BFS示例：DFS思想—遍历篇DFS程序基本结构DFS示例最小生成树(MinimumSpanningTree)Prim思想—最小生成树篇Prime程序基本结构Prim示例：Kruskal思想：—最小生成树篇Kruskal程序基本结构：Kruscal示例：最短路径(ShortestPath):Dijkstra思想：—最短路径篇Dijkstra程序基本结构：Dijkstra逐步求解的过程Bellman-Ford思想：—最短路径篇Bellman-Ford程序基本结构：Floyd-Warshall思想：—最短路径篇Floyd-Warshall程序基本结构：Floyd示例：ExerciseBFS：zoj(1091)跳马的规则BFS：BFS：voidproc(){
intx,y,nx,ny,sx,sy,dx,dy,step=0;
sx=c1-'a';sy=d1-'1';dx=c2-'a';dy=d2-'1';
queue<int>tq;
tq.push(sx);tq.push(sy);tq.push(step);
m[sx][sy]=1;
while(!tq.empty()){
x=tq.front();tq.pop();
y=tq.front();tq.pop();
step=tq.front();tq.pop();
if(x==dx&&y==dy)break;
for(inti=0;i<8;i++){
nx=x+d[i][0];ny=y+d[i][1];
if(nx<0||nx>=8||ny<0||ny>=8||m[nx][ny])continue;
tq.push(nx);tq.push(ny);tq.push(step+1);
m[nx][ny]=1;
}
}
cout<<"Togetfrom"<<c1<<d1<<"to"<<c2<<d2<<"takes"<<step<<"knightmoves."<<endl;
}
双向BFSDFS：pku2258青蛙(zju1942)Prim:zju1942Prim:Prim:Kruscal:zju1942Kruscal:（并查集的操作）Kruscal:Kruscal:Bellman-Ford:HomeWorkBellman-Ford:Dijkstra:pku2387Dijkstra:Floyd-Warshall:zju1942（青蛙）Floyd-Warshall相关题目：