Dado un gráfico dirigido y dos vértices en él, compruebe si hay un camino desde el primer vértice dado hasta el segundo.
Ejemplo:
Consider the following Graph: Input : (u, v) = (1, 3) Output: Yes Explanation: There is a path from 1 to 3, 1 -> 2 -> 3 Input : (u, v) = (3, 6) Output: No Explanation: There is no path from 3 to 6
Enfoque: Se puede utilizar la búsqueda primero en amplitud (BFS) o la búsqueda primero en profundidad (DFS) para encontrar la ruta entre dos vértices. Tome el primer vértice como fuente en BFS (o DFS), siga el BFS estándar (o DFS). Si el segundo vértice se encuentra en nuestro recorrido, devuelve verdadero; de lo contrario, devuelve falso.
Algoritmo BFS:
- La implementación a continuación utiliza BFS.
- Cree una cola y una array visitada inicialmente rellena con 0, de tamaño V, donde V es un número de vértices.
- Inserte el Node inicial en la cola, es decir, presione u en la cola y márquelo como visitado.
- Ejecute un bucle hasta que la cola no esté vacía.
- Dequeue el elemento frontal de la cola. Iterar todos sus elementos adyacentes. Si alguno de los elementos adyacentes es el destino, devuelve verdadero. Empuje todos los vértices adyacentes y no visitados en la cola y márquelos como visitados.
- Devuelve false ya que no se alcanza el destino en BFS.
Implementación: códigos C++, Java y Python que usan BFS para encontrar la accesibilidad del segundo vértice desde el primer vértice.
C++
// C++ program to check if there is exist a path between two vertices // of a graph. #include<iostream> #include <list> using namespace std; // This class represents a directed graph using adjacency list // representation class Graph { int V; // No. of vertices list<int> *adj; // Pointer to an array containing adjacency lists public: Graph(int V); // Constructor void addEdge(int v, int w); // function to add an edge to graph bool isReachable(int s, int d); }; Graph::Graph(int V) { this->V = V; adj = new list<int>[V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Add w to v’s list. } // A BFS based function to check whether d is reachable from s. bool Graph::isReachable(int s, int d) { // Base case if (s == d) return true; // Mark all the vertices as not visited bool *visited = new bool[V]; for (int i = 0; i < V; i++) visited[i] = false; // Create a queue for BFS list<int> queue; // Mark the current node as visited and enqueue it visited[s] = true; queue.push_back(s); // it will be used to get all adjacent vertices of a vertex list<int>::iterator i; while (!queue.empty()) { // Dequeue a vertex from queue and print it s = queue.front(); queue.pop_front(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it visited // and enqueue it for (i = adj[s].begin(); i != adj[s].end(); ++i) { // If this adjacent node is the destination node, then // return true if (*i == d) return true; // Else, continue to do BFS if (!visited[*i]) { visited[*i] = true; queue.push_back(*i); } } } // If BFS is complete without visiting d return false; } // Driver program to test methods of graph class int main() { // Create a graph given in the above diagram Graph g(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); int u = 1, v = 3; if(g.isReachable(u, v)) cout<< "\n There is a path from " << u << " to " << v; else cout<< "\n There is no path from " << u << " to " << v; u = 3, v = 1; if(g.isReachable(u, v)) cout<< "\n There is a path from " << u << " to " << v; else cout<< "\n There is no path from " << u << " to " << v; return 0; }
Java
// Java program to check if there is exist a path between two vertices // of a graph. import java.io.*; import java.util.*; import java.util.LinkedList; // This class represents a directed graph using adjacency list // representation class Graph { private int V; // No. of vertices private LinkedList<Integer> adj[]; //Adjacency List //Constructor Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i<v; ++i) adj[i] = new LinkedList(); } //Function to add an edge into the graph void addEdge(int v,int w) { adj[v].add(w); } //prints BFS traversal from a given source s Boolean isReachable(int s, int d) { LinkedList<Integer>temp; // Mark all the vertices as not visited(By default set // as false) boolean visited[] = new boolean[V]; // Create a queue for BFS LinkedList<Integer> queue = new LinkedList<Integer>(); // Mark the current node as visited and enqueue it visited[s]=true; queue.add(s); // 'i' will be used to get all adjacent vertices of a vertex Iterator<Integer> i; while (queue.size()!=0) { // Dequeue a vertex from queue and print it s = queue.poll(); int n; i = adj[s].listIterator(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it while (i.hasNext()) { n = i.next(); // If this adjacent node is the destination node, // then return true if (n==d) return true; // Else, continue to do BFS if (!visited[n]) { visited[n] = true; queue.add(n); } } } // If BFS is complete without visited d return false; } // Driver method public static void main(String args[]) { // Create a graph given in the above diagram Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); int u = 1; int v = 3; if (g.isReachable(u, v)) System.out.println("There is a path from " + u +" to " + v); else System.out.println("There is no path from " + u +" to " + v);; u = 3; v = 1; if (g.isReachable(u, v)) System.out.println("There is a path from " + u +" to " + v); else System.out.println("There is no path from " + u +" to " + v);; } } // This code is contributed by Aakash Hasija
Python3
# program to check if there is exist a path between two vertices # of a graph from collections import defaultdict #This class represents a directed graph using adjacency list representation class Graph: def __init__(self,vertices): self.V= vertices #No. of vertices self.graph = defaultdict(list) # default dictionary to store graph # function to add an edge to graph def addEdge(self,u,v): self.graph[u].append(v) # Use BFS to check path between s and d def isReachable(self, s, d): # Mark all the vertices as not visited visited =[False]*(self.V) # Create a queue for BFS queue=[] # Mark the source node as visited and enqueue it queue.append(s) visited[s] = True while queue: #Dequeue a vertex from queue n = queue.pop(0) # If this adjacent node is the destination node, # then return true if n == d: return True # Else, continue to do BFS for i in self.graph[n]: if visited[i] == False: queue.append(i) visited[i] = True # If BFS is complete without visited d return False # Create a graph given in the above diagram g = Graph(4) g.addEdge(0, 1) g.addEdge(0, 2) g.addEdge(1, 2) g.addEdge(2, 0) g.addEdge(2, 3) g.addEdge(3, 3) u =1; v = 3 if g.isReachable(u, v): print("There is a path from %d to %d" % (u,v)) else : print("There is no path from %d to %d" % (u,v)) u = 3; v = 1 if g.isReachable(u, v) : print("There is a path from %d to %d" % (u,v)) else : print("There is no path from %d to %d" % (u,v)) #This code is contributed by Neelam Yadav
C#
// C# program to check if there is // exist a path between two vertices // of a graph. using System; using System.Collections; using System.Collections.Generic; // This class represents a directed // graph using adjacency list // representation class Graph { private int V; // No. of vertices private LinkedList<int>[] adj; //Adjacency List // Constructor Graph(int v) { V = v; adj = new LinkedList<int>[v]; for (int i = 0; i < v; ++i) adj[i] = new LinkedList<int>(); } // Function to add an edge into the graph void addEdge(int v, int w) { adj[v].AddLast(w); } // prints BFS traversal from a given source s bool isReachable(int s, int d) { // LinkedList<int> temp = new LinkedList<int>(); // Mark all the vertices as not visited(By default set // as false) bool[] visited = new bool[V]; // Create a queue for BFS LinkedList<int> queue = new LinkedList<int>(); // Mark the current node as visited and enqueue it visited[s] = true; queue.AddLast(s); // 'i' will be used to get all adjacent vertices of a vertex IEnumerator i; while (queue.Count != 0) { // Dequeue a vertex from queue and print it s = queue.First.Value; queue.RemoveFirst(); int n; i = adj[s].GetEnumerator(); // Get all adjacent vertices of the dequeued vertex s // If a adjacent has not been visited, then mark it // visited and enqueue it while (i.MoveNext()) { n = (int)i.Current; // If this adjacent node is the destination node, // then return true if (n == d) return true; // Else, continue to do BFS if (!visited[n]) { visited[n] = true; queue.AddLast(n); } } } // If BFS is complete without visited d return false; } // Driver method public static void Main(string[] args) { // Create a graph given in the above diagram Graph g = new Graph(4); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 2); g.addEdge(2, 0); g.addEdge(2, 3); g.addEdge(3, 3); int u = 1; int v = 3; if (g.isReachable(u, v)) Console.WriteLine("There is a path from " + u + " to " + v); else Console.WriteLine("There is no path from " + u + " to " + v); u = 3; v = 1; if (g.isReachable(u, v)) Console.WriteLine("There is a path from " + u + " to " + v); else Console.WriteLine("There is no path from " + u + " to " + v); } } // This code is contributed by sanjeev2552
Javascript
<script> // Javascript program to check if there is exist a path between two vertices // of a graph. let V; let adj; function Graph( v) { V = v; adj = new Array(v); for (let i = 0; i < v; ++i) adj[i] = []; } // Function to add an edge into the graph function addEdge(v,w) { adj[v].push(w); } // prints BFS traversal from a given source s function isReachable(s,d) { let temp; // Mark all the vertices as not visited(By default set // as false) let visited = new Array(V); for(let i = 0; i < V; i++) visited[i] = false; // Create a queue for BFS let queue = []; // Mark the current node as visited and enqueue it visited[s] = true; queue.push(s); while (queue.length != 0) { // Dequeue a vertex from queue and print it n = queue.shift(); if(n == d) return true; for(let i = 0; i < adj[n].length; i++) { if (visited[adj[n][i]] == false) { queue.push(adj[n][i]); visited[adj[n][i]] = true; } } } // If BFS is complete without visited d return false; } // Driver method Graph(4); addEdge(0, 1); addEdge(0, 2); addEdge(1, 2); addEdge(2, 0); addEdge(2, 3); addEdge(3, 3); let u = 1; let v = 3; if (isReachable(u, v)) document.write("There is a path from " + u +" to " + v+"<br>"); else document.write("There is no path from " + u +" to " + v+"<br>"); u = 3; v = 1; if (isReachable(u, v)) document.write("There is a path from " + u +" to " + v+"<br>"); else document.write("There is no path from " + u +" to " + v+"<br>"); // This code is contributed by avanitrachhadiya2155 </script>
There is a path from 1 to 3 There is no path from 3 to 1
Análisis de Complejidad:
- Complejidad de tiempo: O(V+E) donde V es el número de vértices en el gráfico y E es el número de aristas en el gráfico.
- Complejidad espacial: O(V).
Puede haber como máximo V elementos en la cola. Entonces el espacio necesario es O(V).
Algoritmo DFS:
- if start==end devuelve 1 ya que tenemos que llegar a nuestro destino.
- Marcar inicio como visitado .
- Atraviese los vértices de inicio conectados directamente y repita la función dfs para cada vértice inexplorado.
- devuelve 0 si no llegamos a nuestro destino.
Implementación :
C++14
#include <bits/stdc++.h> using namespace std; typedef long long ll; vector<ll> adj[100000]; bool visited[100000]; bool dfs(int start, int end) { if (start == end) return true; visited[start] = 1; for (auto x : adj[start]) { if (!visited[x]) if (dfs(x, end)) return true; } return false; } int main() { int V = 4; vector<ll> members = { 2, 5, 7, 9 }; int E = 4; vector<pair<ll, ll> > connections = { { 2, 9 }, { 7, 2 }, { 7, 9 }, { 9, 5 } }; for (int i = 0; i < E; i++) adj[connections[i].first].push_back( connections[i].second); int sender = 7, receiver = 9; if (dfs(sender, receiver)) cout << "1"; else cout << "0"; return 0; } // this code is contributed by prophet1999
1
Análisis de Complejidad:
Complejidad de tiempo: O(V+E) donde V es el número de vértices en el gráfico y E es el número de aristas en el gráfico.
Complejidad espacial: O(V).
Puede haber como máximo V elementos en la pila. Entonces el espacio necesario es O(V).
Compensaciones entre BFS y DFS:
La búsqueda primero en amplitud puede ser útil para encontrar el camino más corto entre Nodes, y la búsqueda primero en profundidad puede atravesar un Node adyacente muy profundamente antes de llegar a los vecinos inmediatos.
Como ejercicio, pruebe una versión extendida del problema donde también se necesita el camino completo entre dos vértices.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA