Longitud del camino más largo que termina en el vértice V en un gráfico

Dada una array binaria mat[][] que representa la representación de array de adyacencia de un gráfico , donde mat[i][j] como 1 representa que hay un borde entre los vértices i y j y un vértice V , la tarea es encontrar el camino más largo desde cualquier Node al vértice X tal que cada vértice en el camino ocurre solo una vez. 

Ejemplos:

Entrada: gráfico[][] = {{0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 0}, {0, 1, 0, 0}}, V = 2
Salida: 2
Explicación:
El gráfico dado es el siguiente:
    0
    |
   1
 / \
2 3
El camino más largo que termina en el vértice 2 es 3 -> 1 -> 2 . Por lo tanto, la longitud de este camino es 2.

Entrada: gráfico[][] = {{0, 1, 1, 1}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0}}, V = 1
Salida: 2

Enfoque: el problema dado se puede resolver realizando DFS Traversal en el gráfico dado desde el Node de origen como V y encontrando la longitud máxima de la ruta que tiene el Node más profundo desde el Node V .

Siga los pasos a continuación para resolver el problema:

• Inicialice una lista de adyacencia , digamos Adj[], a partir de la representación gráfica dada en la array mat[][] .
• Inicialice un vector auxiliar , digamos visitado [], para realizar un seguimiento de si se visita o no un vértice.
• Inicialice una variable, digamos distancia como 0 , para almacenar la longitud máxima de la ruta resultante desde cualquier Node de origen hasta el vértice V dado .
• Realice DFS Traversal en el gráfico dado desde el Node V y realice los siguientes pasos:
  • Marque el Node actual V como visitado, es decir, visited[V] = true .
  • Actualice el valor de la distancia al máximo de distancia y nivel .
  • Atraviese la lista de adyacencia del Node fuente actual V . Si el Node secundario no es el mismo que el Node principal y aún no se ha visitado, realice DFS transversal recursivamente como dfs(child, Adj,visited, level + 1, distance) .
  • Después de completar los pasos anteriores, marque el Node actual V como no visitado para incluir la ruta si el ciclo existe en el gráfico dado .
• Después de completar los pasos anteriores, imprima el valor de la distancia como la distancia máxima resultante entre cualquier Node fuente y el Node dado V .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to perform DFS Traversal from
// source node to the deepest node and
// update maximum distance to the deepest node
void dfs(int src, vector<int> Adj[],
         vector<bool>& visited, int level,
         int& distance)
{
 
    // Mark source as visited
    visited[src] = true;
 
    // Update the maximum distance
    distance = max(distance, level);
 
    // Traverse the adjacency list
    // of the current source node
    for (auto& child : Adj[src]) {
 
        // Recursively call
        // for the child node
        if (child != src
            and visited[child] == false) {
            dfs(child, Adj, visited,
                level + 1, distance);
        }
    }
 
    // Backtracking step
    visited[src] = false;
}
 
// Function to calculate maximum length
// of the path ending at vertex V from
// any source node
int maximumLength(vector<vector<int> >& mat,
                  int V)
{
 
    // Stores the maximum length of
    // the path ending at vertex V
    int distance = 0;
 
    // Stores the size of the matrix
    int N = (int)mat.size();
 
    // Stores the adjacency list
    // of the given graph
    vector<int> Adj[N];
 
    vector<bool> visited(N, false);
 
    // Traverse the matrix to
    // create adjacency list
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (mat[i][j] == 1) {
                Adj[i].push_back(j);
            }
        }
    }
 
    // Perform DFS Traversal to
    // update the maximum distance
    dfs(V, Adj, visited, 0, distance);
 
    return distance;
}
 
// Driver Code
int main()
{
    vector<vector<int> > mat = { { 0, 1, 0, 0 },
                                 { 1, 0, 1, 1 },
                                 { 0, 1, 0, 0 },
                                 { 0, 1, 0, 0 } };
    int V = 2;
 
    cout << maximumLength(mat, V);
 
    return 0;
}

// Java program for the above approach
import java.util.ArrayList;
 
class GFG{
     
static int distance;
 
// Function to perform DFS Traversal from source node to
// the deepest node and update maximum distance to the
// deepest node
private static void dfs(int src, ArrayList<ArrayList<Integer>> Adj,
                                 ArrayList<Boolean> visited, int level)
{
     
    // Mark source as visited
    visited.set(src, true);
 
    // Update the maximum distance
    distance = Math.max(distance, level);
 
    // Traverse the adjacency list of the current
    // source node
    for(int child : Adj.get(src))
    {
         
        // Recursively call for the child node
        if ((child != src) &&
            (visited.get(child) == false))
        {
            dfs(child, Adj, visited, level + 1);
        }
    }
     
    // Backtracking step
    visited.set(src, false);
}
 
// Function to calculate maximum length of the path
// ending at vertex v from any source node
private static int maximumLength(int[][] mat, int v)
{
     
    // Stores the maximum length of the path ending at
    // vertex v
    distance = 0;
 
    // Stores the size of the matrix
    int N = mat[0].length;
 
    ArrayList<Boolean> visited = new ArrayList<Boolean>();
 
    for(int i = 0; i < N; i++)
    {
        visited.add(false);
    }
 
    // Stores the adjacency list of the given graph
    ArrayList<
    ArrayList<Integer>> Adj = new ArrayList<
                                  ArrayList<Integer>>(N);
 
    for(int i = 0; i < N; i++)
    {
        Adj.add(new ArrayList<Integer>());
    }
 
    int i, j;
 
    // Traverse the matrix to create adjacency list
    for(i = 0; i < mat[0].length; i++)
    {
        for(j = 0; j < mat.length; j++)
        {
            if (mat[i][j] == 1)
            {
                Adj.get(i).add(j);
            }
        }
    }
     
    // Perform DFS Traversal to update
    // the maximum distance
    dfs(v, Adj, visited, 0);
    return distance;
}
 
// Driver code
public static void main(String[] args)
{
    int[][] mat = { { 0, 1, 0, 0 },
                    { 1, 0, 1, 1 },
                    { 0, 1, 0, 0 },
                    { 0, 1, 0, 0 } };
    int v = 2;
     
    System.out.print(maximumLength(mat, v));
}
}
 
// This code is contributed by abhinavjain194

# Python3 program for the above approach
visited = [False for i in range(4)]
 
# Function to perform DFS Traversal from
# source node to the deepest node and
# update maximum distance to the deepest node
def dfs(src, Adj, level, distance):
     
    global visited
     
    # Mark source as visited
    visited[src] = True
 
    # Update the maximum distance
    distance = max(distance, level)
 
    # Traverse the adjacency list
    # of the current source node
    for child in Adj[src]:
         
        # Recursively call
        # for the child node
        if (child != src and visited[child] == False):
            dfs(child, Adj, level + 1, distance)
 
    # Backtracking step
    visited[src] = False
 
# Function to calculate maximum length
# of the path ending at vertex V from
# any source node
def maximumLength(mat, V):
     
    # Stores the maximum length of
    # the path ending at vertex V
    distance = 0
 
    # Stores the size of the matrix
    N = len(mat)
 
    # Stores the adjacency list
    # of the given graph
    Adj = [[] for i in range(N)]
 
    # Traverse the matrix to
    # create adjacency list
    for i in range(N):
        for j in range(N):
            if (mat[i][j] == 1):
                Adj[i].append(j)
 
    # Perform DFS Traversal to
    # update the maximum distance
    dfs(V, Adj, 0, distance)
 
    return distance + 2
 
# Driver Code
if __name__ == '__main__':
     
    mat = [ [ 0, 1, 0, 0 ],
            [ 1, 0, 1, 1 ],
            [ 0, 1, 0, 0 ],
            [ 0, 1, 0, 0 ] ]
 
    V = 2
     
    print(maximumLength(mat, V))
 
# This code is contributed by ipg2016107

// C# program for the above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG{
     
static int distance;
 
// Function to perform DFS Traversal from
// source node to the deepest node and
// update maximum distance to the deepest node
static void dfs(int src, List<List<int>> Adj,
                List<bool> visited, int level)
{
     
    // Mark source as visited
    visited[src] = true;
  
    // Update the maximum distance
    distance = Math.Max(distance, level);
  
    // Traverse the adjacency list of
    // the current source node
    foreach(int child in Adj[src])
    {
         
        // Recursively call for the child node
        if ((child != src) &&
            (visited[child] == false))
        {
            dfs(child, Adj, visited, level + 1);
        }
    }
      
    // Backtracking step
    visited[src] = false;
}
  
// Function to calculate maximum length of the path
// ending at vertex v from any source node
static int maximumLength(int[,] mat, int v)
{
     
    // Stores the maximum length of the path
    // ending at vertex v
    distance = 0;
  
    // Stores the size of the matrix
    int N = mat.GetLength(0);
  
    List<bool> visited = new List<bool>();
  
    for(int i = 0; i < N; i++)
    {
        visited.Add(false);
    }
  
    // Stores the adjacency list of the given graph
    List<List<int>> Adj = new List<List<int>>(N);
  
    for(int i = 0; i < N; i++)
    {
        Adj.Add(new List<int>());
    }
  
    // Traverse the matrix to create adjacency list
    for(int i = 0; i < mat.GetLength(0); i++)
    {
        for(int j = 0; j < mat.GetLength(0); j++)
        {
            if (mat[i, j] == 1)
            {
                Adj[i].Add(j);
            }
        }
    }
     
    // Perform DFS Traversal to update
    // the maximum distance
    dfs(v, Adj, visited, 0);
    return distance;
}
 
// Driver code
static void Main()
{
    int[,] mat = { { 0, 1, 0, 0 },
                   { 1, 0, 1, 1 },
                   { 0, 1, 0, 0 },
                   { 0, 1, 0, 0 } };
    int v = 2;
      
    Console.Write(maximumLength(mat, v));
}
}
 
// This code is contributed by mukesh07

<script>
// Javascript program for the above approach
     
var distance = 0;
 
// Function to perform DFS Traversal from source node to
// the deepest node and update maximum distance to the
// deepest node
function dfs(src, Adj, visited, level)
{
     
    // Mark source as visited
    visited[src] = true;
 
    // Update the maximum distance
    distance = Math.max(distance, level);
 
    // Traverse the adjacency list of the current
    // source node
    for(var child of Adj[src])
    {
         
        // Recursively call for the child node
        if ((child != src) &&
            (visited[child] == false))
        {
            dfs(child, Adj, visited, level + 1);
        }
    }
     
    // Backtracking step
    visited[src] = false;
}
 
// Function to calculate maximum length of the path
// ending at vertex v from any source node
function maximumLength(mat, v)
{
     
    // Stores the maximum length of the path ending at
    // vertex v
    distance = 0;
 
    // Stores the size of the matrix
    var N = mat[0].length;
 
    var visited = [];
 
    for(var i = 0; i < N; i++)
    {
        visited.push(false);
    }
 
    // Stores the adjacency list of the given graph
    var Adj = Array.from(Array(N), ()=>Array());
 
    var i, j;
 
    // Traverse the matrix to create adjacency list
    for(i = 0; i < mat[0].length; i++)
    {
        for(j = 0; j < mat.length; j++)
        {
            if (mat[i][j] == 1)
            {
                Adj[i].push(j);
            }
        }
    }
     
    // Perform DFS Traversal to update
    // the maximum distance
    dfs(v, Adj, visited, 0);
    return distance;
}
 
// Driver code
var mat = [ [ 0, 1, 0, 0 ],
                [ 1, 0, 1, 1 ],
                [ 0, 1, 0, 0 ],
                [ 0, 1, 0, 0 ] ];
var v = 2;
 
document.write(maximumLength(mat, v));
 
// This code is contributed by rutvik_56.
</script>

2

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)