Número mínimo de aristas entre dos vértices de un gráfico usando DFS

Dado un grafo no dirigido G(V, E) con N vértices y M aristas. Necesitamos encontrar el número mínimo de aristas entre un par dado de vértices (u, v) . 
Ya hemos discutido este problema usando el enfoque BFS , aquí usaremos el enfoque DFS.

Ejemplos:

Entrada: para el siguiente gráfico dado, encuentre el número mínimo de aristas entre el par de vértices (0, 4) 
 

Salida: 1
Hay tres rutas de 0 a 4: 
0 -> 1 -> 2 -> 4 
0 -> 1 -> 2 -> 3 -> 4 
0 -> 4 
Solo la tercera ruta da como resultado un número mínimo de aristas. 

Enfoque: en este enfoque, recorreremos el gráfico de manera DFS , comenzando desde el vértice dado y explorando todos los caminos desde ese vértice hasta nuestro vértice de destino. 

Usaremos dos variables, edge_count y min_num_of_edges . Mientras explora todos los caminos, entre estos vértices, edge_count almacenará el número total de aristas entre ellos, si la cantidad de aristas es menor que la cantidad mínima de aristas, actualizaremos min_num_of_edges .

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

// C++ program to find minimum
// number of edges between any two
// vertices of the graph
 
#include <bits/stdc++.h>
using namespace std;
 
// Class to represent a graph
class Graph {
 
    // No. of vertices
    int V;
 
    // Pointer to an array containing
    // adjacency lists
    list<int>* adj;
 
    // A function used by minEdgeDFS
    void minEdgeDFSUtil(vector<bool>& visited,
                        int src, int des, int& min_num_of_edges,
                        int& edge_count);
 
public:
    // Constructor
    Graph(int V);
 
    // Function to add an edge to graph
    void addEdge(int src, int des);
 
    // Prints the minimum number of edges
    void minEdgeDFS(int u, int v);
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
void Graph::addEdge(int src, int des)
{
    adj[src].push_back(des);
    adj[des].push_back(src);
}
 
// Utility function for finding minimum number
// of edges using DFS
void Graph::minEdgeDFSUtil(vector<bool>& visited,
                           int src, int des, int& min_num_of_edges,
                           int& edge_count)
{
    // For keeping track of visited
    // nodes in DFS
    visited[src] = true;
 
    // If we have found the destination vertex
    // then check whether count of total number of edges
    // is less than the minimum number of edges or not
    if (src == des) {
        if (min_num_of_edges > edge_count)
            min_num_of_edges = edge_count;
    }
 
    // If current vertex is not destination
    else {
 
        // Recur for all the vertices
        // adjacent to current vertex
        list<int>::iterator i;
 
        for (i = adj[src].begin(); i != adj[src].end(); i++) {
            int v = *i;
 
            if (!visited[v]) {
                edge_count++;
 
                minEdgeDFSUtil(visited, v, des, min_num_of_edges,
                               edge_count);
            }
        }
    }
 
    // Decrement the count of number of edges
    // and mark current vertex as unvisited
    visited[src] = false;
    edge_count--;
}
 
// Function to print minimum number of edges
// It uses recursive minEdgeDFSUtil
void Graph::minEdgeDFS(int u, int v)
{
    // To keep track of all the
    // visited vertices
    vector<bool> visited(V, false);
 
    // To store minimum number of edges
    int min_num_of_edges = INT_MAX;
 
    // To store total number of
    // edges in each path
    int edge_count = 0;
 
    minEdgeDFSUtil(visited, u, v, min_num_of_edges,
                   edge_count);
 
    // Print the minimum number of edges
    cout << min_num_of_edges;
}
 
// Driver Code
int main()
{
    // Create a graph
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(2, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
 
    int u = 0;
    int v = 3;
    g.minEdgeDFS(u, v);
 
    return 0;
}

// Java program to find minimum
// number of edges between any two
// vertices of the graph
import java.io.*;
import java.util.*;
 
class GFG
{
 
    static int min_num_of_edges = 0, edge_count = 0;
 
    // Class to represent a graph
    static class Graph
    {
 
        // No. of vertices
        int V;
 
        // Pointer to an array containing
        // adjacency lists
        Vector<Integer>[] adj;
 
        // A function used by minEdgeDFS
 
        // Utility function for finding minimum number
        // of edges using DFS
        private void minEdgeDFSUtil(boolean[] visited,
                                    int src, int des)
        {
 
            // For keeping track of visited
            // nodes in DFS
            visited[src] = true;
 
            // If we have found the destination vertex
            // then check whether count of total number of edges
            // is less than the minimum number of edges or not
            if (src == des)
            {
                if (min_num_of_edges > edge_count)
                    min_num_of_edges = edge_count;
            }
 
            // If current vertex is not destination
            else
            {
                for (int i : adj[src])
                {
                    int v = i;
 
                    if (!visited[v])
                    {
                        edge_count++;
                        minEdgeDFSUtil(visited, v, des);
                    }
                }
            }
 
            // Decrement the count of number of edges
            // and mark current vertex as unvisited
            visited[src] = false;
            edge_count--;
        }
 
        // Constructor
        @SuppressWarnings("unchecked")
        Graph(int V) {
            this.V = V;
            adj = new Vector[V];
 
            for (int i = 0; i < V; i++)
                adj[i] = new Vector<>();
        }
 
        // Function to add an edge to graph
        void addEdge(int src, int des)
        {
            adj[src].add(des);
            adj[des].add(src);
        }
 
        // Function to print minimum number of edges
        // It uses recursive minEdgeDFSUtil
        void minEdgeDFS(int u, int v)
        {
 
            // To keep track of all the
            // visited vertices
            boolean[] visited = new boolean[this.V];
            Arrays.fill(visited, false);
 
            // To store minimum number of edges
            min_num_of_edges = Integer.MAX_VALUE;
 
            // To store total number of
            // edges in each path
            edge_count = 0;
 
            minEdgeDFSUtil(visited, u, v);
 
            // Print the minimum number of edges
            System.out.println(min_num_of_edges);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Create a graph
        Graph g = new Graph(5);
        g.addEdge(0, 1);
        g.addEdge(0, 4);
        g.addEdge(1, 2);
        g.addEdge(2, 4);
        g.addEdge(2, 3);
        g.addEdge(3, 4);
 
        int u = 0;
        int v = 3;
        g.minEdgeDFS(u, v);
    }
}
 
// This code is contributed by
// sanjeev2552

# Python3 program to find minimum
# number of edges between any two
# vertices of the graph
 
# Class to represent a graph
class Graph: 
 
    def __init__(self, V):
        self.V = V
        self.adj = [[] for i in range(V)]
         
    def addEdge(self, src, des):
  
        self.adj[src].append(des)
        self.adj[des].append(src)
  
    # Utility function for finding
    # minimum number of edges using DFS
    def minEdgeDFSUtil(self, visited, src, des, min_num_of_edges, edge_count):
      
        # For keeping track of visited nodes in DFS
        visited[src] = True
     
        # If we have found the destination vertex
        # then check whether count of total number of edges
        # is less than the minimum number of edges or not
        if src == des:
            if min_num_of_edges > edge_count:
                min_num_of_edges = edge_count
          
        # If current vertex is not destination
        else: 
     
            # Recur for all the vertices
            # adjacent to current vertex
            for v in self.adj[src]: 
                 
                if not visited[v]: 
                    edge_count += 1
     
                    min_num_of_edges, edge_count = \
                    self.minEdgeDFSUtil(visited, v, des, min_num_of_edges, edge_count)
                  
        # Decrement the count of number of edges
        # and mark current vertex as unvisited
        visited[src] = False
        edge_count -= 1
        return min_num_of_edges, edge_count
      
    # Function to print minimum number of
    # edges. It uses recursive minEdgeDFSUtil
    def minEdgeDFS(self, u, v):
      
        # To keep track of all the
        # visited vertices
        visited = [False] * self.V
     
        # To store minimum number of edges
        min_num_of_edges = float('inf')
     
        # To store total number of
        # edges in each path
        edge_count = 0
     
        min_num_of_edges, edge_count = \
        self.minEdgeDFSUtil(visited, u, v, min_num_of_edges, edge_count)
     
        # Print the minimum number of edges
        print(min_num_of_edges)
  
# Driver Code
if __name__ == "__main__":
  
    # Create a graph
    g = Graph(5)
    g.addEdge(0, 1)
    g.addEdge(0, 4)
    g.addEdge(1, 2)
    g.addEdge(2, 4)
    g.addEdge(2, 3)
    g.addEdge(3, 4)
 
    u, v = 0, 3
    g.minEdgeDFS(u, v)
 
# This code is contributed by Rituraj Jain

// C# program to find minimum
// number of edges between any two
// vertices of the graph
using System;
using System.Collections;
 
class GFG{
 
static int min_num_of_edges = 0,
                 edge_count = 0;
 
// Class to represent a graph
class Graph
{
     
    // No. of vertices
    public int V;
 
    // Pointer to an array containing
    // adjacency lists
    public ArrayList []adj;
 
    // A function used by minEdgeDFS
 
    // Utility function for finding
    // minimum number of edges using DFS
    public void minEdgeDFSUtil(bool[] visited,
                               int src, int des)
    {
         
        // For keeping track of visited
        // nodes in DFS
        visited[src] = true;
 
        // If we have found the destination
        // vertex then check whether count
        // of total number of edges is less
        // than the minimum number of edges or not
        if (src == des)
        {
            if (min_num_of_edges > edge_count)
                min_num_of_edges = edge_count;
        }
 
        // If current vertex is not destination
        else
        {
            foreach(int i in adj[src])
            {
                int v = i;
 
                if (!visited[v])
                {
                    edge_count++;
                    minEdgeDFSUtil(visited, v, des);
                }
            }
        }
 
        // Decrement the count of number of edges
        // and mark current vertex as unvisited
        visited[src] = false;
        edge_count--;
    }
 
    public Graph(int V)
    {
        this.V = V;
        adj = new ArrayList[V];
 
        for(int i = 0; i < V; i++)
            adj[i] = new ArrayList();
    }
 
    // Function to add an edge to graph
    public void addEdge(int src, int des)
    {
        adj[src].Add(des);
        adj[des].Add(src);
    }
 
    // Function to print minimum number of edges
    // It uses recursive minEdgeDFSUtil
    public void minEdgeDFS(int u, int v)
    {
 
        // To keep track of all the
        // visited vertices
        bool[] visited = new bool[this.V];
        Array.Fill(visited, false);
 
        // To store minimum number of edges
        min_num_of_edges = Int32.MaxValue;
 
        // To store total number of
        // edges in each path
        edge_count = 0;
 
        minEdgeDFSUtil(visited, u, v);
 
        // Print the minimum number of edges
        Console.Write(min_num_of_edges);
    }
}
 
// Driver Code
public static void Main(string[] args)
{
 
    // Create a graph
    Graph g = new Graph(5);
    g.addEdge(0, 1);
    g.addEdge(0, 4);
    g.addEdge(1, 2);
    g.addEdge(2, 4);
    g.addEdge(2, 3);
    g.addEdge(3, 4);
 
    int u = 0;
    int v = 3;
     
    g.minEdgeDFS(u, v);
}
}
 
// This code is contributed by rutvik_56

2

Complejidad temporal : O(V + E) donde V y E son los números de vértices y aristas en el gráfico respectivamente.
Espacio Auxiliar : O(V).