C++에서 오일러 경로 또는 회로를 인쇄하기 위한 Fleury의 알고리즘

Fleury의 알고리즘은 주어진 그래프에서 오일러 경로 또는 오일러 회로를 표시하는 데 사용됩니다. 이 알고리즘에서는 한 모서리에서 시작하여 이전 정점을 제거하여 다른 인접 정점을 이동하려고 합니다. 이 트릭을 사용하면 그래프가 오일러 ​​경로 또는 회로를 찾기 위한 각 단계에서 더 간단해집니다.

경로 또는 회로를 얻으려면 몇 가지 규칙을 확인해야 합니다.

• 그래프는 오일러 그래프여야 합니다.
• 에지가 두 개일 때 하나는 브리지이고 다른 하나는 비 브리지이므로 처음에는 비 브리지를 선택해야 합니다.

시작 정점을 선택하는 것도 까다롭습니다. 어떤 정점도 시작 정점으로 사용할 수 없습니다. 그래프에 홀수 차수 정점이 없으면 아무 정점이나 시작점으로 선택할 수 있습니다. 그렇지 않으면 한 정점에 홀수 차수가 있으면 먼저 그 정점을 선택해야 합니다. .

입력 − 그래프의 인접 행렬

출력 − 오일러 경로 또는 회로: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