Gegeven een gerichte Euleriaanse grafiek is het de taak om een Euler-circuit . Een Euler-circuit is een pad dat elke rand van een grafiek precies één keer doorkruist en het pad eindigt op het startpunt.
Opmerking: De gegeven grafiek bevat een Euler-circuit.
Voorbeeld:
Invoer: gerichte grafiek
Uitgang: 0 3 4 0 2 1 0
Vereisten:
- Wij hebben gesproken over de probleem om erachter te komen of een bepaalde grafiek Euleriaans is of niet voor een ongerichte grafiek
- Voorwaarden voor Euleriaans circuit in een gerichte Grpag: (1) Alle hoekpunten behoren tot een enkele sterk verbonden component. (2) Alle hoekpunten hebben dezelfde in- en uit-graad. Merk op dat voor een ongerichte grafiek de voorwaarde anders is (alle hoekpunten hebben een even graad)
Benadering:
- Kies een startpunt v en volg een spoor van randen vanaf dat hoekpunt totdat je terugkeert naar v. Het is niet mogelijk om vast te komen te zitten op een ander hoekpunt dan v, omdat de indegree en outdegree van elk hoekpunt hetzelfde moeten zijn wanneer het pad een ander hoekpunt binnengaat w er moet een ongebruikte rand zijn die w verlaat. De op deze manier gevormde tour is een gesloten tour, maar bestrijkt mogelijk niet alle hoekpunten en randen van de initiële grafiek.
- Zolang er een hoekpunt u bestaat dat tot de huidige tour behoort, maar aangrenzende randen heeft die geen deel uitmaken van de tour, begint u een ander pad vanaf u en volgt u ongebruikte randen totdat u terugkeert naar u en sluit u aan bij de tour die op deze manier is gevormd met de vorige tour.
Illustratie:
Als voorbeeld nemen van de bovenstaande grafiek met 5 knooppunten: adj = {{2 3} {0} {1} {4} {0}}.
- Begin bij hoekpunt 0 :
- Huidig pad: [0]
- Circuit: []
- Hoekpunt 0 → 3 :
- Huidig pad: [0 3]
- Circuit: []
- Hoekpunt 3 → 4 :
- Huidig pad: [0 3 4]
- Circuit: []
- Hoekpunt 4 → 0 :
- Huidig pad: [0 3 4 0]
- Circuit: []
- Hoekpunt 0 → 2 :
- Huidig pad: [0 3 4 0 2]
- Circuit: []
- Hoekpunt 2 → 1 :
- Huidig pad: [0 3 4 0 2 1]
- Circuit: []
- Hoekpunt 1 → 0 :
- Huidig pad: [0 3 4 0 2 1 0]
- Circuit: []
- Ga terug naar hoekpunt 0 : Voeg 0 toe aan circuit.
- Huidig pad: [0 3 4 0 2 1]
- Circuit: [0]
- Terug naar hoekpunt 1 : Voeg 1 toe aan circuit.
- Huidig pad: [0 3 4 0 2]
- Circuit: [0 1]
- Terug naar hoekpunt 2 : Voeg 2 toe aan circuit.
- Huidig pad: [0 3 4 0]
- Circuit: [0 1 2]
- Ga terug naar hoekpunt 0 : Voeg 0 toe aan circuit.
- Huidig pad: [0 3 4]
- Circuit: [0 1 2 0]
- Terug naar hoekpunt 4 : Voeg 4 toe aan het circuit.
- Huidig pad: [0 3]
- Circuit: [0 1 2 0 4]
- Terug naar hoekpunt 3 : Voeg 3 toe aan het circuit.
- Huidig pad: [0]
- Circuit: [0 1 2 0 4 3]
- Ga terug naar hoekpunt 0 : Voeg 0 toe aan circuit.
- Huidig pad: []
- Circuit: [0 1 2 0 4 3 0]
Hieronder vindt u de implementatie van de bovenstaande aanpak:
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 ' '); }
Uitvoer
0 3 4 0 2 1 0
Tijdcomplexiteit: O(V + E) waarbij V het aantal hoekpunten is en E het aantal randen in de grafiek. De reden hiervoor is dat het algoritme een diepte-eerst-zoekopdracht (DFS) uitvoert en elk hoekpunt en elke rand precies één keer bezoekt. Dus voor elk hoekpunt kost het O(1) tijd om het te bezoeken en voor elke rand kost het O(1) tijd om er doorheen te gaan.
Complexiteit van de ruimte: O(V + E) omdat het algoritme een stapel gebruikt om het huidige pad op te slaan en een lijst om het laatste circuit op te slaan. De maximale grootte van de stapel kan in het slechtste geval V + E zijn, dus de ruimtecomplexiteit is O(V + E).
Quiz maken