Given an undirected graph G(V, E) with N vertices and M edges. We need to find the minimum number of edges between a given pair of vertices (u, v).
We have already discussed this problem using the BFS approach, here we will use the DFS approach.
Examples:
Input: For the following given graph, find the minimum number of edges between vertex pair (0, 4)
Output:1
There are three paths from 0 to 4:
0 -> 1 -> 2 -> 4
0 -> 1 -> 2 -> 3 -> 4
0 -> 4
Only the third path results in minimum number of edges.
Approach: In this approach we will traverse the graph in a DFS manner, starting from the given vertex and explore all the paths from that vertex to our destination vertex.
We will use two variables, edge_count and min_num_of_edges. While exploring all the paths, between these vertices, edge_count will store count of total number of edges among them, if number of edges is less than the minimum number of edges we will update min_num_of_edges.
Below is the implementation of the above approach:
C++
// 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 graphclass 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 DFSvoid 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 minEdgeDFSUtilvoid 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 Codeint 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
// 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
# 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#
// 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 |
Javascript
// Class to represent a graphclass Graph {constructor(V) {this.V = V;this.adj = [];for (let i = 0; i < V; i++) {this.adj[i] = [];}}addEdge(src, des) {this.adj[src].push(des);this.adj[des].push(src);}// Utility function for finding// minimum number of edges using DFSminEdgeDFSUtil(visited, src, des, min_num_of_edges, edge_count) {// For keeping track of visited nodes in DFSvisited[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; }} else { // Recur for all the vertices // adjacent to current vertex for (let v of this.adj[src]) { if (!visited[v]) { edge_count++; const result = this.minEdgeDFSUtil(visited, v, des, min_num_of_edges, edge_count); min_num_of_edges = result[0]; edge_count = result[1]; } }}// Decrement the count of number of edges // and mark current vertex as unvisited visited[src] = false;edge_count--;return [min_num_of_edges, edge_count];}// Function to print minimum number of// edges. It uses recursive minEdgeDFSUtilminEdgeDFS(u, v) {// To keep track of all the// visited verticeslet visited = [];for (let i = 0; i < this.V; i++) {visited[i] = false;}// To store minimum number of edges let min_num_of_edges = Number.POSITIVE_INFINITY;// To store total number of // edges in each path let edge_count = 0;const result = this.minEdgeDFSUtil(visited, u, v, min_num_of_edges, edge_count);min_num_of_edges = result[0];edge_count = result[1];// Print the minimum number of edges console.log(min_num_of_edges);}}// Driver Code// Create a graphconst 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);const u = 0;const v = 3;g.minEdgeDFS(u, v); |
Output
2
Complexity Analysis:
- Time Complexity: O(V + E) where V and E are the numbers of vertices and edges in the graph respectively.
- Auxiliary Space: O(V).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
