logo

TechCodeview

Având în vedere un grafic eulerian direcționat, sarcina este de a imprima un Circuitul Euler . Un circuit Euler este o cale care traversează fiecare margine a unui grafic exact o dată, iar calea se termină pe vârful de pornire.

Nota:

Exemplu:



Intrare: grafic direcționat

Algoritmul lui Hierholzer pentru graficul direcționat' title=

Ieșire: 0 3 4 0 2 1 0

Cerințe preliminare:

  • Am discutat despre problema de a afla dacă un graf dat este sau nu eulerian pentru un grafic nedirecționat
  • Condiții pentru circuitul eulerian într-un Grpag Dirijat: (1) Toate vârfurile aparțin unei singure componente puternic conectate. (2) Toate vârfurile au același grad în interior și în exterior. Rețineți că pentru un grafic nedirecționat condiția este diferită (toate vârfurile au grad par)

Abordare:

  1. Alegeți orice vârf de pornire v și urmați o urmă de muchii de la acel vârf până la întoarcerea la v. Nu este posibil să rămâneți blocat la alt vârf decât v, deoarece indegree și outdegree ale fiecărui vârf trebuie să fie aceleași atunci când traseul intră într-un alt vârf w trebuie să existe o muchie nefolosită care părăsește w. Turul format în acest fel este un tur închis, dar este posibil să nu acopere toate vârfurile și marginile graficului inițial.
  2. Atâta timp cât există un vârf u care aparține turului curent, dar care are margini adiacente care nu face parte din tur, porniți un alt traseu de la u urmând margini nefolosite până la întoarcerea la u și alăturați-vă turului astfel format la turul anterior.

Ilustrare:

Luând exemplu din graficul de mai sus cu 5 noduri: adj = {{2 3} {0} {1} {4} {0}}.

  1. Începeți de la vârful 0 :
    • Calea curentă: [0]
    • Circuit: []
  2. Vârful 0 → 3 :
    • Calea curentă: [0 3]
    • Circuit: []
  3. Vârful 3 → 4 :
    • Calea curentă: [0 3 4]
    • Circuit: []
  4. Vârful 4 → 0 :
    • Calea curentă: [0 3 4 0]
    • Circuit: []
  5. Vârful 0 → 2 :
    • Calea curentă: [0 3 4 0 2]
    • Circuit: []
  6. Vârful 2 → 1 :
    • Calea curentă: [0 3 4 0 2 1]
    • Circuit: []
  7. Vârful 1 → 0 :
    • Calea curentă: [0 3 4 0 2 1 0]
    • Circuit: []
  8. Revenire la vârful 0 : Adăugați 0 la circuit.
    • Calea curentă: [0 3 4 0 2 1]
    • Circuit: [0]
  9. Revenire la vârful 1 : Adăugați 1 la circuit.
    • Calea curentă: [0 3 4 0 2]
    • Circuit: [0 1]
  10. Revenire la vârful 2 : Adăugați 2 la circuit.
    • Calea curentă: [0 3 4 0]
    • Circuit: [0 1 2]
  11. Revenire la vârful 0 : Adăugați 0 la circuit.
    • Calea curentă: [0 3 4]
    • Circuit: [0 1 2 0]
  12. Revenire la vârful 4 : Adăugați 4 la circuit.
    • Calea curentă: [0 3]
    • Circuit: [0 1 2 0 4]
  13. Revenire la vârful 3 : Adăugați 3 la circuit.
    • Calea curentă: [0]
    • Circuit: [0 1 2 0 4 3]
  14. Revenire la vârful 0 : Adăugați 0 la circuit.
    • Calea curentă: []
    • Circuit: [0 1 2 0 4 3 0]

Mai jos este implementarea abordării de mai sus: 

C++ 
// C++ program to print Eulerian circuit in given // directed graph using Hierholzer algorithm #include    using namespace std; // Function to print Eulerian circuit vector<int> printCircuit(vector<vector<int>> &adj) {  int n = adj.size();  if (n == 0)  return {};  // Maintain a stack to keep vertices  // We can start from any vertex here we start with 0  vector<int> currPath;  currPath.push_back(0);  // list to store final circuit  vector<int> circuit;  while (currPath.size() > 0) {  int currNode = currPath[currPath.size() - 1];  // If there's remaining edge in adjacency list  // of the current vertex  if (adj[currNode].size() > 0) {    // Find and remove the next vertex that is  // adjacent to the current vertex  int nextNode = adj[currNode].back();  adj[currNode].pop_back();  // Push the new vertex to the stack  currPath.push_back(nextNode);  }  // back-track to find remaining circuit  else {  // Remove the current vertex and  // put it in the circuit  circuit.push_back(currPath.back());  currPath.pop_back();  }  }  // reverse the result vector   reverse(circuit.begin() circuit.end());    return circuit; } int main() {  vector<vector<int>> adj = {{2 3} {0} {1} {4} {0}};  vector<int> ans = printCircuit(adj);    for (auto v: ans) cout << v << ' ';  cout << endl;  return 0; }
Java 
// 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 
# 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# 
// 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 
// 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 ' '); }

Ieșire 
0 3 4 0 2 1 0

Complexitatea timpului:  O(V + E) unde V este numărul de vârfuri și E este numărul de muchii din grafic. Motivul pentru aceasta este că algoritmul efectuează o căutare în adâncime (DFS) și vizitează fiecare vârf și fiecare muchie exact o dată. Deci pentru fiecare vârf este nevoie de timp O(1) pentru a-l vizita și pentru fiecare muchie este nevoie de timp O(1) pentru a-l traversa.

Complexitatea spațiului : O(V + E), deoarece algoritmul folosește o stivă pentru a stoca calea curentă și o listă pentru a stoca circuitul final. Dimensiunea maximă a stivei poate fi V + E în cel mai rău caz, astfel încât complexitatea spațiului este O(V + E).

Creați un test