フルーリーのアルゴリズム

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

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

• グラフはオイラーグラフである必要があります。

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

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

アルゴリズム

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