弗勒里的算法
Fleury算法用于显示给定图的欧拉路径或欧拉电路。在此算法中，从一条边开始，它尝试通过删除先前的顶点来移动其他相邻的顶点。使用此技巧，在查找欧拉路径或电路的每一步中，图形都会变得更加简单。
我们必须检查一些规则以获得路径或电路-
该图必须是欧拉图。
当有两个边时，一个是桥，另一个是非桥，我们必须首先选择非桥。
选择起始顶点也很棘手，我们不能使用任何顶点作为起始顶点，如果图形没有奇数个顶点，我们可以选择任何一个顶点作为起始点，否则当一个顶点具有奇数个顶点时，我们必须先选择一个顶点。
算法
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
dfs(prev, start, visited)
Input: The pervious and start vertex to perform DFS, and visited list.
Output: Count the number of nodes after DFS.
Begin
count := 1
visited[start] := true
for all vertex b, in the graph, do
if prev is not u, then
if u is not visited, then
if start and u are connected, then
count := count + dfs(start, u, visited)
end if
end if
end if
done
return count
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
v_count = number of nodes
//这不会在下一个递归调用中初始化
for all vertex v, which are adjacent with start, do
make visited array and will with false value
if isBridge(start, v), then decrease v_count by 1
cnt = dfs(start, v, visited)
if difference between cnt and v_count <= 2, then
print the edge (start →‡ v)
if isBridge(v, start), then decrease v_count by 1
remove edge from start and v
decrease edge by 1
fleuryAlgorithm(v)
end if
done
End示例
#include<iostream>
#include<vector>
#include<cmath>
#define NODE 8
using namespace std;
int graph[NODE][NODE] = {
{0,1,1,0,0,0,0,0},
{1,0,1,1,1,0,0,0},
{1,1,0,1,0,1,0,0},
{0,1,1,0,0,0,0,0},
{0,1,0,0,0,1,1,1},
{0,0,1,0,1,0,1,1},
{0,0,0,0,1,1,0,0},
{0,0,0,0,1,1,0,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++; //increase degree, when connected edge found
}
if(deg % 2 != 0) //when degree of vertices are odd
return i; //i is node with odd degree
}
return 0; //when all vertices have even degree, start from 0
}
int dfs(int prev, int start, bool visited[]){
int count = 1;
visited[start] = true;
for(int u = 0; u<NODE; u++){
if(prev != u){
if(!visited[u]){
if(tempGraph[start][u]){
count += dfs(start, u, visited);
}
}
}
}
return count;
}
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; //the edge is not forming bridge
}
return true; //edge forming a bridge
}
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();
static int v_count = NODE;
for(int v = 0; v<NODE; v++) {
if(tempGraph[start][v]) {
bool visited[NODE] = {false};
if(isBridge(start, v)){
v_count--;
}
int cnt = dfs(start, v, visited);
if(abs(v_count-cnt) <= 2){
cout << start << "--" << v << " ";
if(isBridge(v, start)){
v_count--;
}
tempGraph[start][v] = tempGraph[v][start] = 0; //remove edge from graph
edge--;
fleuryAlgorithm(v);
}
}
}
}
int main() {
for(int i = 0; i<NODE; i++) //copy main graph to tempGraph
for(int j = 0; j<NODE; j++)
tempGraph[i][j] = graph[i][j];
cout << "Euler Path Or Circuit: ";
fleuryAlgorithm(findStartVert());
}输出结果
Euler Path Or Circuit: 0--1 1--2 2--3 3--1 1--4 4--5 5--6 6--4 4--7 7--5 5--2 2--0