Для орієнтованого ейлерового графа завдання полягає в тому, щоб надрукувати Схема Ейлера . Схема Ейлера — це шлях, який проходить кожне ребро графа рівно один раз і закінчується на початковій вершині.
Примітка: Даний граф містить схему Ейлера.
приклад:
Вхід: орієнтований граф
Вихід: 0 3 4 0 2 1 0
Передумови:
- Ми обговорили завдання з'ясувати, чи є даний граф ейлеровим чи ні для неорієнтованого графа
- Умови для ейлерового контуру в орієнтованому групі: (1) Усі вершини належать одній сильно зв’язній компоненті. (2) Усі вершини мають однаковий внутрішній і зовнішній ступінь. Зверніть увагу, що для неорієнтованого графа умова інша (усі вершини мають парний ступінь)
Підхід:
- Виберіть будь-яку початкову вершину v і дотримуйтеся сліду ребер від цієї вершини до повернення до v. Неможливо застрягти на будь-якій вершині, окрім v, тому що вхідний і відступний ступінь кожної вершини мають бути однаковими, коли слід входить в іншу вершину w, має залишатися невикористане ребро, виходячи з w. Тур, сформований таким чином, є закритим туром, але може не охоплювати всі вершини та ребра початкового графа.
- Поки існує вершина 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).
Створіть вікторину