資料結構
網路連線
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚研究
法律研究Fleury 的演算法在 C++ 中用於列印尤拉路徑或尤拉環
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 //it will not initialize in next 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++; //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
}
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; //count nunber of edges in the graph
}
void fleuryAlgorithm(int start){
static int edge = edgeCount();
for(int v = 0; v<NODE; v++){
if(tempGraph[start][v]){ //when (u,v) edge is presnt and not forming bridge
if(edge <= 1 || !isBridge(start, v)){
cout << start << "--" << v << " ";
tempGraph[start][v] = tempGraph[v][start] = 0; //remove edge from graph
edge--; //reduce 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: 1--0 0--2 2--1 1--3 3--0 0--4 4--3 3—2
更新於： 25-9-2019
2K+ 次瀏覽
廣告