nullACM/ICPC程序设计ACM/ICPC程序设计简单算法
计算机学院 张淑平图论-算法图论-算法图的遍历
BFS(广搜)
DFS(深搜)
最小生成树
Prim
Kruskal
最短路径
Bellman-Ford
Dijkstra
Floyd-Warshall
BFS练习
DFS练习
Prim练习
Kruskal练习
Bellman-Ford练习
Dijkstra练习
Floyd-Warshall练习图的遍历图的遍历遍历要访问到图中的每一个顶点。
BFS (Breadth-First Search)
DFS (Depth-First Search)
BFS思想 —遍历篇BFS思想 —遍历篇1.从图中某顶点v0出发，在访问了v0之后，搜索v0的(所有未被访问的)邻接顶点v1.v2…
2.依次从这些邻接顶点出发，广搜图中其它顶点，直至图中所有已被访问的顶点的邻接顶点都被访问到。
3.若此时图中还有未被访问到的顶点，则再选择其中之一作为v0重复上述过程。直到图中所有顶点均被访问到。
//搜索过程没有回溯，是一种牺牲空间换取时间的方法。时间复杂度：O(V+E)BFS程序基本结构BFS程序基本结构定义一个队列;
起始点加入队列;
while(队列不空){
取出队头结点;
若它是所求的目标状态,跳出循环;
否则，从它扩展出子结点,全都添加到队尾;
}
若循环中找到目标,输出结果;
否则输出无解;BFS示例：BFS示例：DFS思想 —遍历篇DFS思想 —遍历篇1.将图G中每个顶点标记为未被访问，选取一个顶点v作为搜索起点，标记其为已访问
2.递归地深搜v的每个未被访问过的邻接顶点，直到从v出发所有可达的顶点都已被访问过。
3.若此时图中还有未被访问到的顶点，则再选择其中之一作为v重复上述过程。直到图中所有顶点均被访问到。
//时间复杂度：O(V+E)DFS程序基本结构DFS程序基本结构void DFS(int step)
{
for(i=0; i
0) {
min=lowcost[j];//在v中找到最小的代价点k
k=j;
}
closest[k]=0;//k归入u中
for(j=2;j<=n;j++)
if(closest[j]&&c[k][j]0) {
lowcost[j]=c[k][j];
//以k点为起点进行新一轮的代价计算,更新lowcost[]和closest[]
closest[j]=k;
}
}
}Prim示例：Prim示例：U={v0}U={v0,v2}U={v0,v2,v5}U={v0,v2,v5,v3}U={v0,v2,v5,v3,v1}U={v0,v2,v5,v3,v1,v4}Kruskal思想： —最小生成树篇Kruskal思想： —最小生成树篇1.将边按边树由小到大排序。
2.每次加最小边 && 不构成回路。
3.加进了n-1条边就得到了最小生成树
//Kruskal算法并不保证每步生成的结果是连通的（中间结果可能不是树）。
Kruskal程序基本结构：Kruskal程序基本结构：优先队列+并查集Kruscal 示例：Kruscal 示例： 实例的执行过程12435661655563421、初始连通分量：{1},{2},{3},{4},{5},{6}
2、反复执行添加、放弃动作。条件：边数不等于 n-1时
边 动作 连通分量
(1,3) 添加 {1,3},{4},{5},{6},{2}
(4,6) 添加 {1,3},{4, 6},{2},{5}
(2,5) 添加 {1,3},{4, 6},{2,5}
(3,6) 添加 {1,3,4, 6},{2,5}
(1,4) 放弃 因构成回路
(3,4) 放弃 因构成回路
(2,3) 添加 {1,3,4,5,6,2}1243561534255最短路径 (Shortest Path):最短路径 (Shortest Path):最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
边上权值非负情形的单源最短路径问题
— Dijkstra算法
边上权值为任意值的单源最短路径问题
— Bellman-Ford算法
所有顶点之间的最短路径
— Floyd算法
Dijkstra思想： —最短路径篇Dijkstra思想： —最短路径篇 初始化：
S ← { v0 };dist[j] ← Edge[0][j], j = 1, 2, …, n-1;
1、求出最短路径的长度：
dist[k] ← min{ dist[i] }, i V- S ; S ← S U { k };
2、 修改：
dist[i] ←min{ dist[i], dist[k] + Edge[k][i] }, for iV- S ;
3、 判断：
若S = V, 则算法结束，否则转1。
引入一个辅助数组dist。dist[i]表示当前从源点v0到终点vi 的最短路径的长度。时间复杂度:O(V2)Dijkstra程序基本结构：Dijkstra程序基本结构：void disktra(int v)//原点是v {
bool s[maxn]; register int i,j,k;
for(i=1;i<=n;i++){
dist[i] = c[v][i];
s[i] = 0; // i不在集合S中
if(dist[i]==manint)//v to i没有边
prev[i] = 0;
else
prev[i] = v;
}
s[v] = 1; dist[v] = 0;
for(i=1;id[u]+w(u,v)) {
d[v]=d[u]+w(u,v);
par[v]=u;
}
}
for each edge(u,v)
if(d[v]>d[u]+w(u,v))
return false;
return true;
}nullFloyd-Warshall思想： —最短路径篇Floyd-Warshall思想： —最短路径篇定义一个n×n的方阵序列∶A0，A1…，An，其中Ak[i-1][j-1]表示从vi到vj允许k个顶点v0, v1,…,vk-1为中间顶点的最短路径长度（A0 是图的邻接矩阵）。A0[i][j]表示从vi到vj不经过任何中间顶点的最短路径长度。An[i][j]就是从vi到vj的最短路径长度。
A0[i][j]=arcs[i][j] 0≤i≤n-1, 0≤j≤n-1
Ak[i][j]=min{Ak-1[i][j],Ak-1[i][k-1]+Ak-1[k-1][j]} 1≤k≤n，加入第k个顶点vk-1为中间顶点。
//时间复杂度O(n3)Floyd-Warshall程序基本结构：Floyd-Warshall程序基本结构：for(k=0;kd[i][k]+d[k][j])
d[i][j]=d[i][k]+d[k][j];
( d[i][j]=Min(d[i][j], d[i][k]+d[k][j]) )Floyd示例：Floyd示例：执行Floyd算法后:ExerciseExercise Practice makes perfect!
The more, the better!BFS： zoj(1091)BFS： zoj(1091)国际象棋棋盘上有一个马，要跳到指定目标，最少跳几步？ a b c d e f g h1
2
3
4
5
6
7
8h8a1输入：
a1 h8
输出：
To get from a1 to h8 takes 6 knight moves. 跳马的规则跳马的规则 a b c d e f g h1
2
3
4
5
6
7
8在2×3的矩形里：BFS：BFS：例如：从a1到e4当目标出现在所扩展出的结点里，结果就找到了。To get from a1 to e4 takes 3 knight moves. BFS：BFS：int main(){
for(;;)
{
if(!(cin>>c1))
break;
cin>>d1>>c2>>d2; //输入起点、终点。
for(int i=0;i<8;i++)
for(int j=0;j<8;j++)m[i][j]=0;//所有点都标记为“没走”
proc();
}
return 0;
}
#include
#include
using namespace std;
int d[8][2]={{1,2},{1,-2},{2,-1},{2,1},
{-1,2},{-1,-2},{-2,-1},{-2,1}};
int m[8][8];//给走过的点标记
char c1,c2,d1,d2;
void proc();Knight Moves zoj(1091)程序实现void proc(){
int x,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(int i=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<<"To get from "<
记录
混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载
最长路径的长度，gr[i][j]i到j的边长为1，以每一个结点为源点进行深搜
#include #include
int gr[25][25],best,n,m;
void dfs(int p,int depth) //p为源点，depth为深度
{
int i;
bool flag=true;
for(i=0;ibest)
best=depth;
return;
}
}
青蛙(zju1942)青蛙(zju1942)湖中有一些石头露出水面。青蛙Freddy蹲在其中一块上面，他女朋友Fiona在另一块上。Freddy想跳到Fiona那里。
Freddy可以在两石头间跳跃，有不同的路径选择；他希望找到一条路，路上跳跃的最大距离最小。
输入这些石头的坐标，输出这个最小值。Prim: zju1942Prim: zju1942int main()
{
int n,i,j,k,x[200],y[200],T=1;
ifstream fin("frogger.in");
#define cin fin
while(cin>>n && n)
{
for(i=0;i>x[i]>>y[i];
for(j=0;j
#include
#include
using namespace std;
#define Min(a,b) ((a)>(b)?(b):(a))
#define Max(a,b) ((a)>(b)?(a):(b))
double d[201][201];Prim:Prim: double lowcost[200],min,answer;
memset(lowcost,0,sizeof(lowcost));
answer=d[0][1];
for(i=1;i>n && n){
L=0;
for(i=0;i>x[i]>>y[i];
for(j=0;j
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
库的函数，对边进行从小到大排序#include
#include
#include
#include
using namespace std;Kruscal:Kruscal: for(i=0;id[u]+w[u][v])
{
d[v]=d[u]+w[u][v];
Pa[v]=u;
}
}Bellman-Ford:Bellman-Ford:bool Bellman_Ford(int s)
{
Initialize_Single_Source(s);
for(i=1;id[j]+w[j][k] )
return false;
return true;
}
Dijkstra: pku2387Dijkstra: pku2387void Dijkstra(int n,int v)
{
for(int i=1;i<=n;i++)
{
dist[i]=c[v][i];
s[i]=false;
if(dist[i]==MAX) prev[i]=0;
else prev[i]=v;
}
dist[v]=0;s[v]=true;
for(i=1;i>t>>n;
int x,y,len;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i==j) continue;
c[i][j]=MAX;
}
for(i=1;i<=n;i++) c[i][i]=0;
for(i=0;i>x>>y>>len;
if(len
#include
#include
using namespace std;
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)>(b)?(b):(a))
int main(){
int n,i,j,k,x[201],y[201],T=1;
double d[201][201];
while(cin>>n && n){
for(i=0;i>x[i]>>y[i];
for(j=0;j
本文档为【ACM培训之5-图论算法1】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483