유향 그래프에 오일러 경로가 포함되어 있는지 확인하는 C++ 프로그램

오일러 경로는 경로입니다. 이를 통해 모든 가장자리를 정확히 한 번 방문할 수 있습니다. 같은 정점을 여러 번 사용할 수 있습니다. 이 경우 오일러 경로도 포함하므로 오일러 회로를 포함하는 하나의 그래프도 고려됩니다.

방향 그래프에 오일러 경로가 있는지 여부를 확인하려면 다음 조건을 확인해야 합니다. -

• 단 하나의 정점 a_n이 있어야 합니다. 여기서 (in-degree + 1 =out_degree)
• 단 하나의 꼭짓점 b_n이 있어야 합니다. 여기서 (in-degree =out_degree + 1)
• Rest 모든 정점은 (in-degree =out_degree) 이러한 경우 중 하나라도 실패하면 그래프에 오일러 경로가 없습니다.
  

꼭짓점 b는 (안 차수 1, 바깥 차수 2)를 가지고, 꼭짓점 c는 (안 차수 2, 바깥 차수 1)을 갖습니다. 그리고 나머지 정점 a, d는 (내차 2, 외차 2), e는 (내차 1, 외차 1)을 가집니다.

입력

그래프의 인접 행렬입니다.

출력

오일러 경로를 찾았습니다.

알고리즘

traverse(u, 방문)

시작 노드 u와 방문한 노드를 입력하여 방문한 노드를 표시합니다.

출력은 연결된 모든 정점을 순회합니다.

Begin
   mark u as visited
   for all vertex v, if it is adjacent with u, do
      if v is not visited, then
      traverse(v, visited)
   done
End

연결됨(그래프)

입력 :그래프.

출력:그래프가 연결된 경우 True입니다.

Begin
   define visited array
   for all vertices u in the graph, do
      make all nodes unvisited
      traverse(u, visited)
      if any unvisited node is still remaining, then
         return false
      done
   return true
End

hasEulerPath(그래프)

주어진 그래프를 입력하세요.

하나의 오일러 회로가 발견되면 True를 출력합니다.

Begin
   an := 0
   bn := 0
   if isConnected() is false, then
      return false
   define list for inward and outward edge count for each node
   for all vertex i in the graph, do
      sum := 0
      for all vertex j which are connected with i, do
         inward edges for vertex i increased
         increase sum
      done
      number of outward of vertex i is sum
   done
   if inward list and outward list are same, then
      return true
   for all vertex i in the vertex set V, do
      if inward[i] ≠ outward[i], then
         if inward[i] + 1 = outward[i], then
            an := an + 1
         else if inward[i] = outward[i] + 1, then
            bn := bn + 1
      done
      if an and bn both are 1, then
          return true
      otherwise return false
End

예시 코드

#include<iostream>
#include<vector>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {{0, 0, 1, 1, 0},
   {1, 0, 1, 0, 0},
   {0, 0, 0, 1, 0},
   {0, 1, 0, 0, 1},
   {1, 0, 0, 0, 0}};
void traverse(int u, bool visited[]) {
   visited[u] = true; //mark v as visited
   for(int v = 0; v<NODE; v++) {
      if(graph[u][v]) {
         if(!visited[v])
            traverse(v, visited);
      }
   }
}
bool isConnected() {
   bool *vis = new bool[NODE];
   //for all vertex u as start point, check whether all nodes are visible or not
   for(int u; u < NODE; u++) {
      for(int i = 0; i<NODE; i++)
         vis[i] = false; //initialize as no node is visited
         traverse(u, vis);
      for(int i = 0; i<NODE; i++) {
         if(!vis[i]) //if there is a node, not visited by traversal, graph is not connected
            return false;
      }
   }
   return true;
}
bool hasEulerPath() {
   int an = 0, bn = 0;
   if(isConnected() == false){ //when graph is not connected
      return false;
   }
   vector<int> inward(NODE, 0), outward(NODE, 0);
   for(int i = 0; i<NODE; i++) {
      int sum = 0;
      for(int j = 0; j<NODE; j++) {
         if(graph[i][j]) {
            inward[j]++; //increase inward edge for destination vertex
            sum++; //how many outward edge
         }
      }
      outward[i] = sum;
   }
   //check the condition for Euler paths
   if(inward == outward) //when number inward edges and outward edges for each node is same
      return true; //Euler Circuit, it has Euler path
   for(int i = 0; i<NODE; i++) {
      if(inward[i] != outward[i]) {
         if((inward[i] + 1 == outward[i])) {
            an++;
         } else if((inward[i] == outward[i] + 1)) {
            bn++;
         }
      }
   }
   if(an == 1 && bn == 1) { //if there is only an, and bn, then this has euler path
      return true;
   }
   return false;
}
int main() {
   if(hasEulerPath())
      cout << "Euler Path Found.";
   else
   cout << "There is no Euler Circuit.";
}

출력

Euler Path Found.