Dado un grafo dirigido G con N vértices y M aristas . La tarea es encontrar la longitud del camino dirigido más largo en Graph.
Nota: La longitud de un camino dirigido es el número de aristas que tiene.
Ejemplos:
Entrada: N = 4, M = 5
Salida: 3
El camino dirigido 1->3->2->4
Entrada: N = 5, M = 8
Salida: 3
Enfoque simple: un enfoque ingenuo es calcular la longitud de la ruta más larga desde cada Node utilizando DFS .
La complejidad temporal de este enfoque es O(N 2 ).
Enfoque eficiente : un enfoque eficiente es usar la programación dinámica y DFS juntos para encontrar la ruta más larga en el gráfico.
Sea dp[i] la longitud del camino más largo a partir del Node i . Inicialmente, todas las posiciones de dp serán 0. Podemos llamar a la función DFS desde cada Node y recorrer todos sus hijos. La fórmula recursiva será:
dp[Node] = max(dp[Node], 1 + max(dp[hijo1], dp[hijo2], dp[hijo3]..))
Al final, verifique el valor máximo en la array dp[], que será la ruta más larga en el DAG.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the longest
// path in the DAG
#include <bits/stdc++.h>
using namespace std;
// Function to traverse the DAG
// and apply Dynamic Programming
// to find the longest path
void dfs(int node, vector<int> adj[], int dp[], bool vis[])
{
// Mark as visited
vis[node] = true;
// Traverse for all its children
for (int i = 0; i < adj[node].size(); i++) {
// If not visited
if (!vis[adj[node][i]])
dfs(adj[node][i], adj, dp, vis);
// Store the max of the paths
dp[node] = max(dp[node], 1 + dp[adj[node][i]]);
}
}
// Function to add an edge
void addEdge(vector<int> adj[], int u, int v)
{
adj[u].push_back(v);
}
// Function that returns the longest path
int findLongestPath(vector<int> adj[], int n)
{
// Dp array
int dp[n + 1];
memset(dp, 0, sizeof dp);
// Visited array to know if the node
// has been visited previously or not
bool vis[n + 1];
memset(vis, false, sizeof vis);
// Call DFS for every unvisited vertex
for (int i = 1; i <= n; i++) {
if (!vis[i])
dfs(i, adj, dp, vis);
}
int ans = 0;
// Traverse and find the maximum of all dp[i]
for (int i = 1; i <= n; i++) {
ans = max(ans, dp[i]);
}
return ans;
}
// Driver Code
int main()
{
int n = 5;
vector<int> adj[n + 1];
// Example-1
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 3, 2);
addEdge(adj, 2, 4);
addEdge(adj, 3, 4);
cout << findLongestPath(adj, n);
return 0;
}
Java
// Java program to find the longest
// path in the DAG
import java.util.ArrayList;
// graph class
class Graph
{
int vertices;
ArrayList<Integer> edge[];
Graph(int vertices)
{
this.vertices = vertices;
edge = new ArrayList[vertices+1];
for (int i = 0; i <= vertices; i++)
{
edge[i] = new ArrayList<>();
}
}
void addEdge(int a,int b)
{
edge[a].add(b);
}
void dfs(int node, ArrayList<Integer> adj[], int dp[],
boolean visited[])
{
// Mark as visited
visited[node] = true;
// Traverse for all its children
for (int i = 0; i < adj[node].size(); i++)
{
// If not visited
if (!visited[adj[node].get(i)])
dfs(adj[node].get(i), adj, dp, visited);
// Store the max of the paths
dp[node] = Math.max(dp[node], 1 + dp[adj[node].get(i)]);
}
}
// Function that returns the longest path
int findLongestPath( int n)
{
ArrayList<Integer> adj[] = edge;
// Dp array
int[] dp = new int[n+1];
// Visited array to know if the node
// has been visited previously or not
boolean[] visited = new boolean[n + 1];
// Call DFS for every unvisited vertex
for (int i = 1; i <= n; i++)
{
if (!visited[i])
dfs(i, adj, dp, visited);
}
int ans = 0;
// Traverse and find the maximum of all dp[i]
for (int i = 1; i <= n; i++)
{
ans = Math.max(ans, dp[i]);
}
return ans;
}
}
public class Main
{
// Driver code
public static void main(String[] args)
{
int n = 5;
Graph graph = new Graph(n);
// Example-1
graph.addEdge( 1, 2);
graph.addEdge( 1, 3);
graph.addEdge( 3, 2);
graph.addEdge( 2, 4);
graph.addEdge( 3, 4);
graph.findLongestPath(n);
System.out.println( graph.findLongestPath( n));
}
}
// This code is contributed by SumanSaurav
Python3
# Python3 program to find the # longest path in the DAG # Function to traverse the DAG # and apply Dynamic Programming # to find the longest path def dfs(node, adj, dp, vis): # Mark as visited vis[node] = True # Traverse for all its children for i in range(0, len(adj[node])): # If not visited if not vis[adj[node][i]]: dfs(adj[node][i], adj, dp, vis) # Store the max of the paths dp[node] = max(dp[node], 1 + dp[adj[node][i]]) # Function to add an edge def addEdge(adj, u, v): adj[u].append(v) # Function that returns the longest path def findLongestPath(adj, n): # Dp array dp = [0] * (n + 1) # Visited array to know if the node # has been visited previously or not vis = [False] * (n + 1) # Call DFS for every unvisited vertex for i in range(1, n + 1): if not vis[i]: dfs(i, adj, dp, vis) ans = 0 # Traverse and find the maximum of all dp[i] for i in range(1, n + 1): ans = max(ans, dp[i]) return ans # Driver Code if __name__ == "__main__": n = 5 adj = [[] for i in range(n + 1)] # Example-1 addEdge(adj, 1, 2) addEdge(adj, 1, 3) addEdge(adj, 3, 2) addEdge(adj, 2, 4) addEdge(adj, 3, 4) print(findLongestPath(adj, n)) # This code is contributed by Rituraj Jain
C#
// C# program to find the longest
// path in the DAG
using System;
using System.Collections.Generic;
// graph class
class Graph
{
public int vertices;
public List<int> []edge;
public Graph(int vertices)
{
this.vertices = vertices;
edge = new List<int>[vertices + 1];
for (int i = 0; i <= vertices; i++)
{
edge[i] = new List<int>();
}
}
public void addEdge(int a, int b)
{
edge[a].Add(b);
}
public void dfs(int node, List<int> []adj,
int []dp, Boolean []visited)
{
// Mark as visited
visited[node] = true;
// Traverse for all its children
for (int i = 0; i < adj[node].Count; i++)
{
// If not visited
if (!visited[adj[node][i]])
dfs(adj[node][i], adj, dp, visited);
// Store the max of the paths
dp[node] = Math.Max(dp[node], 1 +
dp[adj[node][i]]);
}
}
// Function that returns the longest path
public int findLongestPath( int n)
{
List<int> []adj = edge;
// Dp array
int[] dp = new int[n + 1];
// Visited array to know if the node
// has been visited previously or not
Boolean[] visited = new Boolean[n + 1];
// Call DFS for every unvisited vertex
for (int i = 1; i <= n; i++)
{
if (!visited[i])
dfs(i, adj, dp, visited);
}
int ans = 0;
// Traverse and find the maximum of all dp[i]
for (int i = 1; i <= n; i++)
{
ans = Math.Max(ans, dp[i]);
}
return ans;
}
}
class GFG
{
// Driver code
public static void Main(String[] args)
{
int n = 5;
Graph graph = new Graph(n);
// Example-1
graph.addEdge( 1, 2);
graph.addEdge( 1, 3);
graph.addEdge( 3, 2);
graph.addEdge( 2, 4);
graph.addEdge( 3, 4);
graph.findLongestPath(n);
Console.WriteLine(graph.findLongestPath(n));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program to find the longest
// path in the DAG
// Function to traverse the DAG
// and apply Dynamic Programming
// to find the longest path
function dfs(node, adj, dp, vis)
{
// Mark as visited
vis[node] = true;
// Traverse for all its children
for (var i = 0; i < adj[node].length; i++) {
// If not visited
if (!vis[adj[node][i]])
dfs(adj[node][i], adj, dp, vis);
// Store the max of the paths
dp[node] = Math.max(dp[node], 1 + dp[adj[node][i]]);
}
}
// Function to add an edge
function addEdge(adj, u, v)
{
adj[u].push(v);
}
// Function that returns the longest path
function findLongestPath(adj, n)
{
// Dp array
var dp = Array(n+1).fill(0);
// Visited array to know if the node
// has been visited previously or not
var vis = Array(n+1).fill(false);
// Call DFS for every unvisited vertex
for (var i = 1; i <= n; i++) {
if (!vis[i])
dfs(i, adj, dp, vis);
}
var ans = 0;
// Traverse and find the maximum of all dp[i]
for (var i = 1; i <= n; i++) {
ans = Math.max(ans, dp[i]);
}
return ans;
}
// Driver Code
var n = 5;
var adj = Array.from(Array(n+1), ()=>Array());
// Example-1
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 3, 2);
addEdge(adj, 2, 4);
addEdge(adj, 3, 4);
document.write( findLongestPath(adj, n));
</script>
Producción:
3
Complejidad temporal: O(N+M)
Espacio auxiliar: O(N)
?list=PLqM7alHXFySEaZgcg7uRYJFBnYMLti-nh