欢迎辞欢迎来到“笃志以砺，决起而飞”！ 如果您是第一次来到本站，建议访问 本站导读以便更快地了解本站。 如果您喜欢本站， 欢迎订阅。 | 欧拉回路 【定义】 图G的一个回路，若它恰通过G中每条边一次,则称该回路为欧拉(Euler)回路。 具有欧拉回路的图称为欧拉图（简称E图）。 【相关结论】 定理： 一个无向图是欧拉图，当且仅当该图所有顶点度数都是偶数或只有两个定点的度数为奇。 一个有向图是欧拉图，当且仅当该图所有顶点度数都是0。 求欧拉回路的一种解法 下面是无向图的欧拉回路输出代码：注意输出的前提是已经判断图确实是欧拉回路。 int num = 0;//标记输出队列 int match[MAX];//标志节点的度，无向图，不区分入度和出度 void solve(int x) { if(match[x] == 0) Record[num++] = x; else { for(int k =0;k<=500;k++) { if(Array[x][k] !=0 ) { Array[x][k]–; Array[k][x]–; match[x]–; match[k]–; solve(k); } } Record[num++] = x; } } 注意record中的点的排列是输出的到序，因此，如果要输出欧拉路径，需要将record倒过来输出。 求欧拉回路的思路： 循环的找到出发点。从某个节点开始，然后查出一个从这个出发回到这个点的环路径。这种方法保证每个边都被遍历。如果有某个点的边没有被遍历就让这个点为起点，这条边为起始边，把它和当前的环衔接上。这样直至所有的边都被遍历。这样，整个图就被连接到一起了。 具体步骤： 1。如果此时与该点无相连的点，那么就加入路径中 2。如果该点有相连的点，那马就列一张表，遍历这些点，知道没有相连的点。 3。处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的操作，并把删除的点加入到路径中去。 [...] 【本文由 Ceeji 原创，转载请注明出处并保留本注释。】 Bellman-Ford算法（根据发明者 Richard Bellman 和 Lester Ford 命名）是求解单源最短路径问题的一种算法。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为 Edward F. Moore 也为这个算法的发展做出了贡献。 单源点的最短路径问题是指：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。 与迪杰斯特拉算法，（另一种著名的求最短路径的算法）不同的是，在 Bellman-Ford 算法中，路径的权值可以为负数。 设想从我们可以从图中找到一个环路（即从v出发，经过若干个点之后又回到v）且这个环路中所有路径的权值之和为负。那么通过这个环路，环路中任意两点的最 短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。 算法描述 设G为加权有向图 V是所有结点的集合 E是所有路径的集合 S表示源点 n表示V中所有结点的数目 weight(u,v)表示从结点u到结点v的路径的权值。 Distanz(v)表示从源点s出发到结点v的最短路径的距离，（或者说是从s到v所有的路径中权值的最小值）。【Predecessor(v)表示节 点v的父结点。】在Bellman-Ford算法结束之后，可以输出，G是不是包含一个负环路。如果G不包含负环路，那么Distanz就存储了从s出发 到所有结点的距离。 Bellman-Ford 算法是 SPFA 算法的基础算法。SPFA 算法是 Bellman-Ford 算法的加强版，时间复杂度和适用面都优于 Dijkstra 算法。设G = (V,E,W) 为某一有向带权图（W 即 weight，权值），s，t 分别代表源点和终点，Distance(v) 代表 v 在算法当前阶段中暂定的从源点出发的最短权和，则算法的核心思想是进行至多 |V|-1 次的迭代处理，每次从 s 出发扩展一层路径，逐渐逼近最短路径。 [...] | |
近期评论