Fleury 算法用于在 C++ 中打印欧拉路径或电路
c++server side programmingprogramming
Fleury 算法用于显示给定图中的欧拉路径或欧拉电路。在此算法中，它从一条边开始，尝试通过移除先前的顶点来移动其他相邻顶点。使用这个技巧，图形在寻找欧拉路径或电路的每个步骤中都变得更简单。
我们必须检查一些规则才能获得路径或电路 −
- 该图必须是欧拉图。
- 当有两条边时，一条是桥，另一条是非桥，我们必须首先选择非桥。
选择起始顶点也很棘手，我们不能使用任何顶点作为起始顶点，如果图中没有奇数度顶点，我们可以选择任何顶点作为起点，否则当一个顶点有奇数度时，我们必须选择那个首先。
输入 − 图的邻接矩阵
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |
输出 − 欧拉路径或回路:1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2
算法
findStartVert(graph) Input: The given graph. Output: Find the starting vertex to start algorithm. Begin for all vertex i, in the graph, do deg := 0 for all vertex j, which are adjacent with i, do deg := deg + 1 done if deg is odd, then return i done when all degree is even return 0 End isBridge(u, v) Input: The start and end node. Output: True when u and v are forming a bridge. Begin deg := 0 for all vertex i which are adjacent with v, do deg := deg + 1 done if deg > 1, then return false return true End fleuryAlgorithm(start) Input: The starting vertex. Output: Display the Euler path or circuit. Begin edge := get the number of edges in the graph //它不会在下一次初始化 recursion call for all vertex v, which are adjacent with start, do if edge <= 1 OR isBridge(start, v) is false, then display path from start and v remove edge (start,v) from the graph decrease edge by 1 fleuryAlgorithm(v) done End
示例
#include<iostream>
#include<vector>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {{0, 1, 1, 1, 1},
{1, 0, 1, 1, 0},
{1, 1, 0, 1, 0},
{1, 1, 1, 0, 1},
{1, 0, 0, 1, 0}
};
int tempGraph[NODE][NODE];
int findStartVert(){
for(int i = 0; i<NODE; i++){
int deg = 0;
for(int j = 0; j<NODE; j++){
if(tempGraph[i][j])
deg++; //当找到连通边时，增加度数
}
if(deg % 2 != 0) //当顶点度数为奇数时
return i; //i 为具有奇数度数的节点
}
return 0; //当所有顶点的度数为偶数时，从 0 开始
}
bool isBridge(int u, int v){
int deg = 0;
for(int i = 0; i<NODE; i++)
if(tempGraph[v][i])
deg++;
if(deg>1){
return false; //边未形成桥
}
return true; //边形成桥
}
int edgeCount(){
int count = 0;
for(int i = 0; i<NODE; i++)
for(int j = i; j<NODE; j++)
if(tempGraph[i][j])
count++;
return count; //计算图中边的数量
}
void fleuryAlgorithm(int start){
static int edge = edgeCount();
for(int v = 0; v<NODE; v++){
if(tempGraph[start][v]){ //当 (u,v) 边存在且未形成桥时
if(edge <= 1 || !isBridge(start, v)){
cout << start << &";--&" << v << &"; &";;
tempGraph[start][v] = tempGraph[v][start] = 0; //从图中删除边
edge--; //减少边
fleuryAlgorithm(v);
}
}
}
}
int main(){
for(int i = 0; i<NODE; i++) //将主图复制到 tempGraph
for(int j = 0; j<NODE; j++)
tempGraph[i][j] = graph[i][j];
cout << "欧拉路径或回路:";
fleuryAlgorithm(findStartVert());
}
输出
欧拉路径或回路:1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2
