무방향 그래프에 오일러 주기가 포함되어 있는지 확인하는 C++ 프로그램

오일러 회로에 대해 알기 위해 오일러 경로에 대한 아이디어가 있습니다. 오일러 경로는 경로입니다. 이를 통해 모든 노드를 정확히 한 번 방문할 수 있습니다. 같은 모서리를 여러 번 사용할 수 있습니다. 오일러 회로는 특수한 유형의 오일러 경로입니다. 오일러 경로의 시작 꼭짓점도 해당 경로의 끝 꼭짓점과 연결되어 있는 경우입니다.

회로를 감지하려면 다음 조건을 따라야 합니다.

• 그래프가 연결되어 있어야 합니다.
• 무방향 그래프의 정점이 홀수 차수를 가지지 않으면 오일러 회로입니다.

입력

출력

그래프에는 오일러 회로가 있습니다.

알고리즘

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

연결됨(그래프)

입력 :그래프.

출력 :그래프가 연결되면 참.

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

hasEulerianCircuit(그래프)

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

출력은 오일러 회로가 없으면 0을 반환하고 오일러 회로가 있으면 1을 반환합니다.

Begin
   if isConnected() is false, then
   return false
   define list of degree for each node
   oddDegree := 0
   for all vertex i in the graph, do
      for all vertex j which are connected with i, do
         increase degree
      done
      if degree of vertex i is odd, then
         increase oddDegree
      done
      if oddDegree is 0, then
      return 1
   else return 0
End

예시 코드

#include<iostream>
#include<vector>
#define NODE 5
using namespace std;
/*int graph[NODE][NODE] = {{0, 1, 1, 1, 0},
   {1, 0, 1, 0, 0},
   {1, 1, 0, 0, 0},
   {1, 0, 0, 0, 1},
   {0, 0, 0, 1, 0}};*/ //No Euler circuit, but euler path is present
int graph[NODE][NODE] = {{0, 1, 1, 1, 1},
   {1, 0, 1, 0, 0},
   {1, 1, 0, 0, 0},
   {1, 0, 0, 0, 1},
   {1, 0, 0, 1, 0}}; //uncomment to check Euler Circuit as well as path
/*int graph[NODE][NODE] = {{0, 1, 1, 1, 0},
   {1, 0, 1, 1, 0},
   {1, 1, 0, 0, 0},
   {1, 1, 0, 0, 1},
   {0, 0, 0, 1, 0}};*/ //Uncomment to check Non Eulerian Graph
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;
}
int hasEulerianCircuit() {
   if(isConnected() == false) //when graph is not connected
   return 0;
   vector<int> degree(NODE, 0);
   int oddDegree = 0;
   for(int i = 0; i<NODE; i++) {
      for(int j = 0; j<NODE; j++) {
         if(graph[i][j])
            degree[i]++; //increase degree, when connected edge found
      }
      if(degree[i] % 2 != 0) //when degree of vertices are odd
      oddDegree++; //count odd degree vertices
   }
   if(oddDegree == 0) { //when oddDegree is 0, it is Euler circuit
      return 1;
   }
   return 0;
}
int main() {
   if(hasEulerianCircuit()) {
      cout << "The graph has Eulerian Circuit." << endl;
   } else {
      cout << "The graph has No Eulerian Circuit." << endl;
   }
}

출력

The graph has Eulerian Circuit.