图论的基本算法.ppt

图论基本算法图过河解：用四维0-1向量表示(人,狼,羊,菜)在河西岸的状态(在河西岸则分量取1,否则取0),共有24=16种状态.在河东岸的状态类似记作.(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)
(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)图的矩阵表示权矩阵关联矩阵邻接表邻接表拓扑排序BFUNCtoporder(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;拓扑排序神经网络神经网络公式中的Wji（可能为负值）表示连接j号神经元和i号神经元的边的权值。当Ci大于0时，该神经元处于兴奋状态，否则就处于平静状态。当神经元处于兴奋状态时，下一秒它会向其他神经元传送信号，信号的强度为Ci。如此．在输入层神经元被激发之后，整个网络系统就在信息传输的推动下进行运作。现在，给定一个神经网络，及当前输入层神经元的状态（Ci），要求你的程序运算出最后网络输出层的状态。
【输入格式】
第一行是两个整数n（1≤n≤20）和p。接下来n行，每行两个整数，第i＋1行是神经元i最初状态和其阈值（Ui），非输入层的神经元开始时状态必然为0。再下面P行，每行由两个整数i，j及一个整数Wij，表示连接神经元i、j的边权值为Wij。
【输出格式】
输出包含若干行，每行有两个整数，分别对应一个神经元的编号，及其最后的状态，两个整数间以空格分隔。仅输出最后状态非零的输出层神经元状态，并且按照编号由小到大顺序输出！
若输出层的神经元最后状态均为0，则输出NULL。
分析可行算法欧拉道路和回路欧拉道路和回路幼儿园的粉刷另一个例子分析最小生成树问题Prim算法Prim算法的正确性快速找到最小代价Prim算法框架Kruskal算法Kruskal算法的正确性子集优化问题子集优化问题的贪心算法快速判断是否产生圈并查集的操作并查集的实现Kruskal算法框架最短路问题SSSP(Dijkstra算法)Dijkstra算法Dijkstra算法Bellman-Ford算法Bellman-Ford算法Bellman-Ford算法SPFA(ShortestPathFasterAlgorithm)定理4在平均情况下，SPFA算法的期望时间复杂度为O(E)。
证明：上述算法每次取出队首结点u，并访问u的所有临结点的复杂度为O(d)，其中d为点u的出度。运用均摊分析的思想，对于|V|个点|E|条边的图，点的平均出度为E/V，所以每处理一个点的复杂度为O(E/V)。假设结点入队次数为h，显然h随图的不同而不同。但它仅与边权值分布有关。我们设h=kV，则算法SPFA的时间复杂度为在平均的情况下，可以将k看成一个比较小的常数，所以SPFA算法在一般情况下的时间复杂度为O(E)。（证毕）SPFA算法Car的旅行路线约束条件分析SSSP：权非负的情形一个例子SSSP：权任意的情形SSSP：bellman-ford算法APSP:基本分析floyd-warshall算法选址问题--中心问题解析关键工程示例1约束条件求有向图的关键路径分析算法求关键路径