数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究弗洛伊算法
弗洛伊算法用于显示图中的欧拉回路或欧拉道路。此算法从一条边开始，通过移除前一个顶点，尝试移动其他相邻顶点。利用此技巧，便于针对每一步中的图形实现欧拉回路或欧拉道路。
我们必须检查一些规则来获得回路或道路 -
此图必须为欧拉图。
当存在两条边，一条是桥，另一条是非桥时，我们必须首先选择非桥。
选择开始顶点也是一种技巧，我们不能使用任何顶点作为开始顶点，如果图中没有奇数度顶点，我们可以选择任何顶点作为开始点，否则当一个顶点的度为奇数时，我们必须首先选择一个顶点。
算法
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 //it will not initialize in next recursion call v_count = number of nodes //this will not initialize in next recursion call 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
更新时间： 16-6 月-2020
6000+ 阅读次数
广告