資料結構
網路
RDBMS
作業系統
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
更新於： 2020 年 6 月 16 日
6K+ 檢視
廣告