유향 오일러 그래프가 주어지면 작업은 다음을 인쇄하는 것입니다. 오일러 회로 . 오일러 회로는 그래프의 모든 모서리를 정확히 한 번만 통과하고 시작 꼭지점에서 끝나는 경로입니다.
메모: 주어진 그래프에는 오일러 회로가 포함되어 있습니다.
예:
입력 : 방향성 그래프
산출: 0 3 4 0 2 1 0
전제 조건:
- 우리는 주어진 그래프가 오일러 그래프인지 아닌지 알아내는 문제 무방향 그래프의 경우
- Directed Grpag의 오일러 회로 조건: (1) 모든 정점은 하나의 강하게 연결된 구성 요소에 속합니다. (2) 모든 정점은 동일한 진입차수와 진출차수를 갖습니다. 무방향 그래프의 경우 조건이 다릅니다(모든 정점의 차수가 짝수임).
접근하다:
- 임의의 시작 정점 v를 선택하고 v로 돌아올 때까지 해당 정점에서 가장자리의 트레일을 따라갑니다. 트레일이 다른 정점 w에 들어갈 때 모든 정점의 내각과 외차가 동일해야 하기 때문에 w를 떠나는 사용되지 않은 가장자리가 있어야 하기 때문에 v가 아닌 다른 정점에서 멈추는 것은 불가능합니다. 이렇게 형성된 투어는 닫힌 투어이지만 초기 그래프의 꼭지점과 가장자리를 모두 포함하지 않을 수 있습니다.
- 현재 투어에 속하지만 투어의 일부가 아닌 인접한 가장자리가 있는 정점 u가 존재하는 한 u로 돌아올 때까지 사용되지 않은 가장자리를 따라 u에서 다른 트레일을 시작하고 이러한 방식으로 형성된 투어를 이전 투어에 결합합니다.
삽화:
5개의 노드가 있는 위 그래프의 예를 들면 다음과 같습니다. adj = {{2 3} {0} {1} {4} {0}}.
- 정점 0에서 시작 :
- 현재 경로: [0]
- 회로: []
- 정점 0 → 3 :
- 현재 경로: [0 3]
- 회로: []
- 정점 3 → 4 :
- 현재 경로: [0 3 4]
- 회로: []
- 정점 4 → 0 :
- 현재 경로: [0 3 4 0]
- 회로: []
- 정점 0 → 2 :
- 현재 경로: [0 3 4 0 2]
- 회로: []
- 정점 2 → 1 :
- 현재 경로: [0 3 4 0 2 1]
- 회로: []
- 정점 1 → 0 :
- 현재 경로: [0 3 4 0 2 1 0]
- 회로: []
- 정점 0으로 역추적 : 회로에 0을 추가합니다.
- 현재 경로: [0 3 4 0 2 1]
- 회로: [0]
- 정점 1로 역추적 : 회로에 1을 더합니다.
- 현재 경로: [0 3 4 0 2]
- 회로: [0 1]
- 정점 2로 역추적 : 회로에 2를 추가합니다.
- 현재 경로: [0 3 4 0]
- 회로: [0 1 2]
- 정점 0으로 역추적 : 회로에 0을 추가합니다.
- 현재 경로: [0 3 4]
- 회로: [0 1 2 0]
- 정점 4로 역추적 : 회로에 4를 추가합니다.
- 현재 경로: [0 3]
- 회로: [0 1 2 0 4]
- 정점 3으로 역추적 : 회로에 3을 추가합니다.
- 현재 경로: [0]
- 회로: [0 1 2 0 4 3]
- 정점 0으로 역추적 : 회로에 0을 추가합니다.
- 현재 경로: []
- 회로: [0 1 2 0 4 3 0]
다음은 위의 접근 방식을 구현한 것입니다.
C++// C++ program to print Eulerian circuit in given // directed graph using Hierholzer algorithm #include
// Java program to print Eulerian circuit in given // directed graph using Hierholzer algorithm import java.util.*; class GfG { // Function to print Eulerian circuit static List<Integer> printCircuit(List<List<Integer>> adj) { int n = adj.size(); if (n == 0) return new ArrayList<>(); // Maintain a stack to keep vertices // We can start from any vertex here we start with 0 List<Integer> currPath = new ArrayList<>(); currPath.add(0); // list to store final circuit List<Integer> circuit = new ArrayList<>(); while (currPath.size() > 0) { int currNode = currPath.get(currPath.size() - 1); // If there's remaining edge in adjacency list // of the current vertex if (adj.get(currNode).size() > 0) { // Find and remove the next vertex that is // adjacent to the current vertex int nextNode = adj.get(currNode).get(adj.get(currNode).size() - 1); adj.get(currNode).remove(adj.get(currNode).size() - 1); // Push the new vertex to the stack currPath.add(nextNode); } // back-track to find remaining circuit else { // Remove the current vertex and // put it in the circuit circuit.add(currPath.get(currPath.size() - 1)); currPath.remove(currPath.size() - 1); } } // reverse the result vector Collections.reverse(circuit); return circuit; } public static void main(String[] args) { List<List<Integer>> adj = new ArrayList<>(); adj.add(new ArrayList<>(Arrays.asList(2 3))); adj.add(new ArrayList<>(Arrays.asList(0))); adj.add(new ArrayList<>(Arrays.asList(1))); adj.add(new ArrayList<>(Arrays.asList(4))); adj.add(new ArrayList<>(Arrays.asList(0))); List<Integer> ans = printCircuit(adj); for (int v : ans) System.out.print(v + ' '); System.out.println(); } }
# Python program to print Eulerian circuit in given # directed graph using Hierholzer algorithm # Function to print Eulerian circuit def printCircuit(adj): n = len(adj) if n == 0: return [] # Maintain a stack to keep vertices # We can start from any vertex here we start with 0 currPath = [0] # list to store final circuit circuit = [] while len(currPath) > 0: currNode = currPath[-1] # If there's remaining edge in adjacency list # of the current vertex if len(adj[currNode]) > 0: # Find and remove the next vertex that is # adjacent to the current vertex nextNode = adj[currNode].pop() # Push the new vertex to the stack currPath.append(nextNode) # back-track to find remaining circuit else: # Remove the current vertex and # put it in the circuit circuit.append(currPath.pop()) # reverse the result vector circuit.reverse() return circuit if __name__ == '__main__': adj = [[2 3] [0] [1] [4] [0]] ans = printCircuit(adj) for v in ans: print(v end=' ') print()
// C# program to print Eulerian circuit in given // directed graph using Hierholzer algorithm using System; using System.Collections.Generic; class GfG { // Function to print Eulerian circuit static List<int> printCircuit(List<List<int>> adj) { int n = adj.Count; if (n == 0) return new List<int>(); // Maintain a stack to keep vertices // We can start from any vertex here we start with 0 List<int> currPath = new List<int> { 0 }; // list to store final circuit List<int> circuit = new List<int>(); while (currPath.Count > 0) { int currNode = currPath[currPath.Count - 1]; // If there's remaining edge in adjacency list // of the current vertex if (adj[currNode].Count > 0) { // Find and remove the next vertex that is // adjacent to the current vertex int nextNode = adj[currNode][adj[currNode].Count - 1]; adj[currNode].RemoveAt(adj[currNode].Count - 1); // Push the new vertex to the stack currPath.Add(nextNode); } // back-track to find remaining circuit else { // Remove the current vertex and // put it in the circuit circuit.Add(currPath[currPath.Count - 1]); currPath.RemoveAt(currPath.Count - 1); } } // reverse the result vector circuit.Reverse(); return circuit; } static void Main(string[] args) { List<List<int>> adj = new List<List<int>> { new List<int> { 2 3 } new List<int> { 0 } new List<int> { 1 } new List<int> { 4 } new List<int> { 0 } }; List<int> ans = printCircuit(adj); foreach (int v in ans) { Console.Write(v + ' '); } Console.WriteLine(); } }
// JavaScript program to print Eulerian circuit in given // directed graph using Hierholzer algorithm // Function to print Eulerian circuit function printCircuit(adj) { let n = adj.length; if (n === 0) return []; // Maintain a stack to keep vertices // We can start from any vertex here we start with 0 let currPath = [0]; // list to store final circuit let circuit = []; while (currPath.length > 0) { let currNode = currPath[currPath.length - 1]; // If there's remaining edge in adjacency list // of the current vertex if (adj[currNode].length > 0) { // Find and remove the next vertex that is // adjacent to the current vertex let nextNode = adj[currNode].pop(); // Push the new vertex to the stack currPath.push(nextNode); } // back-track to find remaining circuit else { // Remove the current vertex and // put it in the circuit circuit.push(currPath.pop()); } } // reverse the result vector circuit.reverse(); return circuit; } let adj = [[2 3] [0] [1] [4] [0]]; let ans = printCircuit(adj); for (let v of ans) { console.log(v ' '); }
산출
0 3 4 0 2 1 0
시간 복잡도: O(V + E) 여기서 V는 정점 수이고 E는 그래프의 간선 수입니다. 그 이유는 알고리즘이 깊이 우선 탐색(DFS)을 수행하고 각 정점과 각 가장자리를 정확히 한 번씩 방문하기 때문입니다. 따라서 각 정점에 대해 방문하는 데 O(1) 시간이 걸리고 각 모서리에 대해 통과하는 데 O(1) 시간이 걸립니다.
공간 복잡도 : O(V + E) 알고리즘은 스택을 사용하여 현재 경로를 저장하고 목록을 사용하여 최종 회로를 저장합니다. 스택의 최대 크기는 최악의 경우 V + E가 될 수 있으므로 공간 복잡도는 O(V + E)입니다.
퀴즈 만들기