Adott egy irányított Euleri-gráf, a feladat egy Euler áramkör . Az Euler-kör egy olyan út, amely a gráf minden élét pontosan egyszer bejárja, és az út a kezdő csúcson ér véget.
Jegyzet: Az adott gráf egy Euler-kört tartalmaz.
Példa:
Bemenet: Irányított gráf
Kimenet: 0 3 4 0 2 1 0
Előfeltételek:
- Megbeszéltük a probléma annak megállapítása, hogy egy adott gráf Euleri-e vagy sem irányítatlan gráfhoz
- Az Euleri áramkör feltételei egy irányított grpagban: (1) Minden csúcs egyetlen erősen kapcsolódó komponenshez tartozik. (2) Minden csúcsnak ugyanaz a be- és kilépési foka. Vegye figyelembe, hogy egy irányítatlan gráf esetén a feltétel más (minden csúcsnak páros foka van)
Megközelítés:
- Válasszon ki egy v kezdőcsúcsot, és kövesse az élek nyomvonalát ettől a csúcstól a v-be való visszatérésig. Nem lehet elakadni a v-n kívül egyetlen más csúcsnál sem, mert minden csúcs infokának és külső fokának meg kell egyeznie, amikor a nyomvonal egy másik csúcsba lép be, ahol w-t elhagyó élnek kell lennie. Az így kialakított körút egy zárt körút, de előfordulhat, hogy nem fedi le a kezdeti gráf összes csúcsát és élét.
- Mindaddig, amíg létezik egy u csúcs, amely az aktuális túrához tartozik, de szomszédos élekkel rendelkezik, amelyek nem részei a túrának, indítsunk el egy másik nyomvonalat u-tól a nem használt éleket követve egészen az u-hoz való visszatérésig, és csatlakozzunk az így kialakított túrához az előző túrához.
Ábra:
Vegyünk példát a fenti grafikonra 5 csomóponttal: adj = {{2 3} {0} {1} {4} {0}}.
- Kezdje a 0 csúcsnál :
- Jelenlegi elérési út: [0]
- Áramkör: []
- Csúcs 0 → 3 :
- Jelenlegi elérési út: [0 3]
- Áramkör: []
- Csúcs 3 → 4 :
- Jelenlegi elérési út: [0 3 4]
- Áramkör: []
- 4. csúcs → 0 :
- Jelenlegi elérési út: [0 3 4 0]
- Áramkör: []
- Csúcs 0 → 2 :
- Jelenlegi elérési út: [0 3 4 0 2]
- Áramkör: []
- 2. csúcs → 1 :
- Jelenlegi elérési út: [0 3 4 0 2 1]
- Áramkör: []
- 1. csúcs → 0 :
- Jelenlegi útvonal: [0 3 4 0 2 1 0]
- Áramkör: []
- Visszalépés a 0. csúcsra : Adjon hozzá 0-t az áramkörhöz.
- Jelenlegi elérési út: [0 3 4 0 2 1]
- Áramkör: [0]
- Vissza az 1. csúcsra : Adjon hozzá 1-et az áramkörhöz.
- Jelenlegi elérési út: [0 3 4 0 2]
- Áramkör: [0 1]
- Visszatérés a 2. csúcshoz : Adjon hozzá 2-t az áramkörhöz.
- Jelenlegi elérési út: [0 3 4 0]
- Áramkör: [0 1 2]
- Visszalépés a 0. csúcsra : Adjon hozzá 0-t az áramkörhöz.
- Jelenlegi elérési út: [0 3 4]
- Áramkör: [0 1 2 0]
- Visszatérés a 4. csúcshoz : Adjon hozzá 4-et az áramkörhöz.
- Jelenlegi elérési út: [0 3]
- Áramkör: [0 1 2 0 4]
- Visszatérés a 3. csúcshoz : Adjon hozzá 3-at az áramkörhöz.
- Jelenlegi elérési út: [0]
- Áramkör: [0 1 2 0 4 3]
- Visszatérés a 0. csúcshoz : Adjon hozzá 0-t az áramkörhöz.
- Jelenlegi útvonal: []
- Áramkör: [0 1 2 0 4 3 0]
Az alábbiakban bemutatjuk a fenti megközelítés megvalósítását:
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 ' '); }
Kimenet
0 3 4 0 2 1 0
Időbeli összetettség: O(V + E) ahol V a csúcsok száma, E pedig a gráf éleinek száma. Ennek az az oka, hogy az algoritmus mélységi keresést (DFS) hajt végre, és minden csúcsot és élt pontosan egyszer keres fel. Tehát minden csúcshoz O(1) idő szükséges, hogy meglátogassa, és minden él esetében O(1) idő szükséges a bejáráshoz.
A tér összetettsége: Az O(V + E) mint az algoritmus egy verem segítségével tárolja az aktuális útvonalat és egy listát a végső áramkör tárolására. A verem maximális mérete legrosszabb esetben V + E lehet, így a tér összetettsége O(V + E).
Kvíz létrehozása