C++でオイラーパスまたは回路を印刷するためのFleuryのアルゴリズム

Fleuryのアルゴリズムは、特定のグラフからオイラーパスまたはオイラー回路を表示するために使用されます。このアルゴリズムでは、1つのエッジから開始して、前の頂点を削除することにより、他の隣接する頂点を移動しようとします。このトリックを使用すると、オイラー経路または回路を見つけるための各ステップでグラフが簡単になります。

パスまたは回路を取得するには、いくつかのルールを確認する必要があります-

• グラフはオイラーグラフである必要があります。
• 2つのエッジがあり、1つはブリッジ、もう1つは非ブリッジの場合、最初に非ブリッジを選択する必要があります。s

開始頂点の選択も注意が必要です。開始頂点として頂点を使用することはできません。グラフに奇数次数の頂点がない場合は、開始点として任意の頂点を選択できます。それ以外の場合、1つの頂点の次数が奇数の場合は、最初にその頂点を選択する必要があります。 。

入力 −グラフの隣接行列

出力 −オイラー経路または回路：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