Dado un gráfico , la tarea es imprimir el recorrido DFS de un gráfico que incluye cada paso, incluido el retroceso.
1st step:- 0 -> 1 2nd step:- 1 -> 5 3rd step:- 5 -> 1 (backtracking step) 4th step:- 1 -> 6... and so on till all the nodes are visited. Dfs step-wise(including backtracking) is: 0 1 5 1 6 7 8 7 6 1 0 2 4 2 9 3 10
Nota: En este diagrama anterior, se acaba de agregar el peso entre los bordes. No tiene ningún papel en DFS-transversal.
Enfoque: Aquí se utilizará DFS con Backtracking . Primero, visite cada Node usando DFS simultáneamente y realice un seguimiento del borde utilizado anteriormente y el Node principal. Si llega un Node donde se han visitado todos los Nodes adyacentes, retroceda utilizando el último borde utilizado e imprima los Nodes. Continúe con los pasos y, en cada paso, el Node principal se convertirá en el Node actual. Continúe con los pasos anteriores para encontrar el recorrido DFS completo del gráfico.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to print the complete // DFS-traversal of graph // using back-tracking #include <bits/stdc++.h> using namespace std; const int N = 1000; vector<int> adj[N]; // Function to print the complete DFS-traversal void dfsUtil(int u, int node, bool visited[], vector<pair<int, int> > road_used, int parent, int it) { int c = 0; // Check if all th node is visited or not // and count unvisited nodes for (int i = 0; i < node; i++) if (visited[i]) c++; // If all the node is visited return; if (c == node) return; // Mark not visited node as visited visited[u] = true; // Track the current edge road_used.push_back({ parent, u }); // Print the node cout << u << " "; // Check for not visited node and proceed with it. for (int x : adj[u]) { // call the DFs function if not visited if (!visited[x]) dfsUtil(x, node, visited, road_used, u, it + 1); } // Backtrack through the last // visited nodes for (auto y : road_used) if (y.second == u) dfsUtil(y.first, node, visited, road_used, u, it + 1); } // Function to call the DFS function // which prints the DFS-traversal stepwise void dfs(int node) { // Create a array of visited node bool visited[node]; // Vector to track last visited road vector<pair<int, int> > road_used; // Initialize all the node with false for (int i = 0; i < node; i++) visited[i] = false; // call the function dfsUtil(0, node, visited, road_used, -1, 0); } // Function to insert edges in Graph void insertEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); } // Driver Code int main() { // number of nodes and edges in the graph int node = 11, edge = 13; // Function call to create the graph insertEdge(0, 1); insertEdge(0, 2); insertEdge(1, 5); insertEdge(1, 6); insertEdge(2, 4); insertEdge(2, 9); insertEdge(6, 7); insertEdge(6, 8); insertEdge(7, 8); insertEdge(2, 3); insertEdge(3, 9); insertEdge(3, 10); insertEdge(9, 10); // Call the function to print dfs(node); return 0; }
Java
// Java program to print the complete // DFS-traversal of graph // using back-tracking import java.io.*; import java.util.*; class GFG { static int N = 1000; static ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(); // Function to print the complete DFS-traversal static void dfsUtil(int u, int node, boolean visited[], ArrayList<ArrayList<Integer>> road_used, int parent, int it) { int c = 0; // Check if all th node is visited or not // and count unvisited nodes for (int i = 0; i < node; i++) if (visited[i]) c++; // If all the node is visited return; if (c == node) return; // Mark not visited node as visited visited[u] = true; // Track the current edge road_used.add(new ArrayList<Integer>(Arrays.asList( parent, u ))); // Print the node System.out.print(u + " "); // Check for not visited node and proceed with it. for (int x : adj.get(u)) { // call the DFs function if not visited if (!visited[x]) { dfsUtil(x, node, visited, road_used, u, it + 1); } } // Backtrack through the last // visited nodes for(int y = 0; y < road_used.size(); y++) { if(road_used.get(y).get(1) == u) { dfsUtil(road_used.get(y).get(0), node, visited,road_used, u, it + 1); } } } // Function to call the DFS function // which prints the DFS-traversal stepwise static void dfs(int node) { // Create a array of visited node boolean[] visited = new boolean[node]; // Vector to track last visited road ArrayList<ArrayList<Integer>> road_used = new ArrayList<ArrayList<Integer>>(); // Initialize all the node with false for (int i = 0; i < node; i++) { visited[i] = false; } // call the function dfsUtil(0, node, visited, road_used, -1, 0); } // Function to insert edges in Graph static void insertEdge(int u, int v) { adj.get(u).add(v); adj.get(v).add(u); } // Driver Code public static void main (String[] args) { // number of nodes and edges in the graph int node = 11, edge = 13; for(int i = 0; i < N; i++) { adj.add(new ArrayList<Integer>()); } // Function call to create the graph insertEdge(0, 1); insertEdge(0, 2); insertEdge(1, 5); insertEdge(1, 6); insertEdge(2, 4); insertEdge(2, 9); insertEdge(6, 7); insertEdge(6, 8); insertEdge(7, 8); insertEdge(2, 3); insertEdge(3, 9); insertEdge(3, 10); insertEdge(9, 10); // Call the function to print dfs(node); } } // This code is contributed by avanitrachhadiya2155
Python3
# Python3 program to print the # complete DFS-traversal of graph # using back-tracking N = 1000 adj = [[] for i in range(N)] # Function to print the complete DFS-traversal def dfsUtil(u, node,visited, road_used, parent, it): c = 0 # Check if all th node is visited # or not and count unvisited nodes for i in range(node): if (visited[i]): c += 1 # If all the node is visited return if (c == node): return # Mark not visited node as visited visited[u] = True # Track the current edge road_used.append([parent, u]) # Print the node print(u, end = " ") # Check for not visited node # and proceed with it. for x in adj[u]: # Call the DFs function # if not visited if (not visited[x]): dfsUtil(x, node, visited, road_used, u, it + 1) # Backtrack through the last # visited nodes for y in road_used: if (y[1] == u): dfsUtil(y[0], node, visited, road_used, u, it + 1) # Function to call the DFS function # which prints the DFS-traversal stepwise def dfs(node): # Create a array of visited node visited = [False for i in range(node)] # Vector to track last visited road road_used = [] # Initialize all the node with false for i in range(node): visited[i] = False # Call the function dfsUtil(0, node, visited, road_used, -1, 0) # Function to insert edges in Graph def insertEdge(u, v): adj[u].append(v) adj[v].append(u) # Driver Code if __name__ == '__main__': # Number of nodes and edges in the graph node = 11 edge = 13 # Function call to create the graph insertEdge(0, 1) insertEdge(0, 2) insertEdge(1, 5) insertEdge(1, 6) insertEdge(2, 4) insertEdge(2, 9) insertEdge(6, 7) insertEdge(6, 8) insertEdge(7, 8) insertEdge(2, 3) insertEdge(3, 9) insertEdge(3, 10) insertEdge(9, 10) # Call the function to print dfs(node) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { static int N = 1000; static List<List<int> > adj = new List<List<int> >(); // Function to print the complete DFS-traversal static void dfsUtil(int u, int node, bool[] visited, List<List<int> > road_used, int parent, int it) { int c = 0; // Check if all th node is visited or not // and count unvisited nodes for (int i = 0; i < node; i++) if (visited[i]) c++; // If all the node is visited return; if (c == node) return; // Mark not visited node as visited visited[u] = true; // Track the current edge road_used.Add(new List<int>() { parent, u }); // Print the node Console.Write(u + " "); // Check for not visited node and proceed with it. foreach(int x in adj[u]) { // call the DFs function if not visited if (!visited[x]) { dfsUtil(x, node, visited, road_used, u, it + 1); } } // Backtrack through the last // visited nodes for (int y = 0; y < road_used.Count; y++) { if (road_used[y][1] == u) { dfsUtil(road_used[y][0], node, visited, road_used, u, it + 1); } } } // Function to call the DFS function // which prints the DFS-traversal stepwise static void dfs(int node) { // Create a array of visited node bool[] visited = new bool[node]; // Vector to track last visited road List<List<int> > road_used = new List<List<int> >(); // Initialize all the node with false for (int i = 0; i < node; i++) { visited[i] = false; } // call the function dfsUtil(0, node, visited, road_used, -1, 0); } // Function to insert edges in Graph static void insertEdge(int u, int v) { adj[u].Add(v); adj[v].Add(u); } static public void Main() { // number of nodes and edges in the graph int node = 11; for (int i = 0; i < N; i++) { adj.Add(new List<int>()); } // Function call to create the graph insertEdge(0, 1); insertEdge(0, 2); insertEdge(1, 5); insertEdge(1, 6); insertEdge(2, 4); insertEdge(2, 9); insertEdge(6, 7); insertEdge(6, 8); insertEdge(7, 8); insertEdge(2, 3); insertEdge(3, 9); insertEdge(3, 10); insertEdge(9, 10); // Call the function to print dfs(node); } } // This code is contributed by rag2127
Javascript
<script> // Javascript program to print the complete // DFS-traversal of graph // using back-tracking let N = 1000; let adj =[]; // Function to print the complete DFS-traversal function dfsUtil(u,node,visited,road_used,parent,it) { let c = 0; // Check if all th node is visited or not // and count unvisited nodes for (let i = 0; i < node; i++) if (visited[i]) c++; // If all the node is visited return; if (c == node) return; // Mark not visited node as visited visited[u] = true; // Track the current edge road_used.push([ parent, u ]); // Print the node document.write(u + " "); // Check for not visited node and proceed with it. for (let x=0;x<adj[u].length;x++) { // call the DFs function if not visited if (!visited[adj[u][x]]) { dfsUtil(adj[u][x], node, visited, road_used, u, it + 1); } } // Backtrack through the last // visited nodes for(let y = 0; y < road_used.length; y++) { if(road_used[y][1] == u) { dfsUtil(road_used[y][0], node, visited,road_used, u, it + 1); } } } // Function to call the DFS function // which prints the DFS-traversal stepwise function dfs(node) { // Create a array of visited node let visited = new Array(node); // Vector to track last visited road let road_used = []; // Initialize all the node with false for (let i = 0; i < node; i++) { visited[i] = false; } // call the function dfsUtil(0, node, visited, road_used, -1, 0); } // Function to insert edges in Graph function insertEdge(u,v) { adj[u].push(v); adj[v].push(u); } // Driver Code let node = 11, edge = 13; for(let i = 0; i < N; i++) { adj.push([]); } // Function call to create the graph insertEdge(0, 1); insertEdge(0, 2); insertEdge(1, 5); insertEdge(1, 6); insertEdge(2, 4); insertEdge(2, 9); insertEdge(6, 7); insertEdge(6, 8); insertEdge(7, 8); insertEdge(2, 3); insertEdge(3, 9); insertEdge(3, 10); insertEdge(9, 10); // Call the function to print dfs(node); // This code is contributed by unknown2108 </script> 9
0 1 5 1 6 7 8 7 6 1 0 2 4 2 9 3 10
Publicación traducida automáticamente
Artículo escrito por AkashDutta y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA