图论的基本算法-朱全民.ppt

图论图图的存储结构拓扑排序FUNCtoporder(vardig:adjlisttp):boolean;
init(top2);m:=0;ve[1..n]:=0
whileNotempty(top1)do
[j:=pop(top1);push(top2,j);m:=m+1;
k:=firstadj(dig,j);
whilek<>0do
[入度(k):=入度(k)-1;
if入度(k)=0thenpush(top1,k);
ifve[j]+dut(<j,k>)>ve[k]thenve[k]:=ve[j]+dut(<j,k>);
k:=nextadj(dig,j,k)
]
]
ifm<nthenreturn(false)elsereturn(true);
endF;拓扑排序欧拉道路和回路欧拉道路和回路怎样找欧拉回路分析另一个例子分析最小生成树问题Prim算法Prim算法的正确性快速找到最小代价Prim算法框架Kruskal算法Kruskal算法的正确性子集优化问题子集优化问题的贪心算法快速判断是否产生圈并查集的操作并查集的实现Kruskal算法框架最短路问题SSSP(Dijkstra算法)PROCshort_DIJ(da:adjmatrix;v0:vtxptr)
vardist:array[vtxptr]ofweighttype;{存储路径长度}
path:array[vtxptr]ofset;{存储路径}
fori:=1tovxtmundo[dist[i]:=da.cost[v0,i];
ifdist[i]<maxthenpath[i]:=[v0]+[i]elsepath[i]:=[];
s:=[v0];{s存储被标号的顶点}
fork:=1tovtxnum-1do
[wm:=max;j:=v0;
fori:=1tovtxnumdo
ifnot(iins)and(dist[i]<wm)then[j:=i;wm:=dist[i]]
s:=s+[j]
fori:=1tovtxnumdo
ifnot(iins)and(dist[j]+da.cost[j,i]<wmthen
[dist[i]:=dist[j]+da.cost[j,i];
path[i]:=path[j]+path[i]
]
]
endPCar的旅行路线约束条件分析SSSP：权非负的情形一个例子SSSP：权任意的情形SSSP：bellman-ford算法一个例子分析APSP:基本分析floyd-warshall算法一个例子瘦陀陀正专注地看回家的地图
地图上标有n（n≤200）个城市和某些城市间直达的道路
以及每条道路的过路费
瘦陀陀还知道在每一座城市举办宴会的花费。
给出地图和A、B的位置
请你告诉瘦陀陀回家的最小费用
你的程序会接收到多次询问
即对于每对城市(c1,c2)，你的程序应该立刻给出瘦陀陀从c1到c2的最小花费。分析关键工程示例1约束条件求有向图的关键路径分析算法求关键路径