Tutorialspoint.dev

Minimum number of edges between two vertices of a Graph

You are given a 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).

Examples:

Input : For given graph G. Find minimum number
        of edges between (1, 5).

Output : 2
Explanation: (1, 2) and (2, 5) are the only
edges resulting into shortest path between 1
and 5.


The idea is to perform BFS from one of given input vertex(u). At the time of BFS maintain an array of distance[n] and initialize it to zero for all vertices. Now, suppose during BFS, vertex x is popped from queue and we are pushing all adjacent non-visited vertices(i) back into queue at the same time we should update distance[i] = distance[x] + 1;.
Finally distance[v] gives the minimum number of edges between u and v.
Algorithm:

int minEdgeBFS(int u, int v, int n)
{
    // visited[n] for keeping track of visited
    // node in BFS
    bool visited[n] = {0};

    // Initialize distances as 0
    int distance[n] = {0};
 
    // queue to do BFS.
    queue  Q;
    distance[u] = 0;
    
    Q.push(u);
    visited[u] = true;
    while (!Q.empty())
    {
        int x = Q.front();
        Q.pop();
 
        for (int i=0; i<edges[x].size(); i++)
        {
            if (visited[edges[x][i]])
                continue;

            // update distance for i
            distance[edges[x][i]] = distance[x] + 1;
            Q.push(edges[x][i]);
            visited[edges[x][i]] = 1;
        }
    }
    return distance[v];
}

C++

// C++ program to find minimum edge
// between given two vertex of Graph
#include<bits/stdc++.h>
using namespace std;
  
// function for finding minimum no. of edge
// using BFS
int minEdgeBFS(vector <int> edges[], int u,
                              int v, int n)
{
    // visited[n] for keeping track of visited
    // node in BFS
    vector<bool> visited(n, 0);
  
    // Initialize distances as 0
    vector<int> distance(n, 0);
  
    // queue to do BFS.
    queue <int> Q;
    distance[u] = 0;
  
    Q.push(u);
    visited[u] = true;
    while (!Q.empty())
    {
        int x = Q.front();
        Q.pop();
  
        for (int i=0; i<edges[x].size(); i++)
        {
            if (visited[edges[x][i]])
                continue;
  
            // update distance for i
            distance[edges[x][i]] = distance[x] + 1;
            Q.push(edges[x][i]);
            visited[edges[x][i]] = 1;
        }
    }
    return distance[v];
}
  
// function for addition of edge
void addEdge(vector <int> edges[], int u, int v)
{
   edges[u].push_back(v);
   edges[v].push_back(u);
}
  
// Driver function
int main()
{
    // To store adjacency list of graph
    int n = 9;
    vector <int> edges[9];
    addEdge(edges, 0, 1);
    addEdge(edges, 0, 7);
    addEdge(edges, 1, 7);
    addEdge(edges, 1, 2);
    addEdge(edges, 2, 3);
    addEdge(edges, 2, 5);
    addEdge(edges, 2, 8);
    addEdge(edges, 3, 4);
    addEdge(edges, 3, 5);
    addEdge(edges, 4, 5);
    addEdge(edges, 5, 6);
    addEdge(edges, 6, 7);
    addEdge(edges, 7, 8);
    int u = 0;
    int v = 5;
    cout << minEdgeBFS(edges, u, v, n);
    return 0;
}

Java

// Java program to find minimum edge
// between given two vertex of Graph
  
import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;
  
class Test
{
    // Method for finding minimum no. of edge
    // using BFS
    static int minEdgeBFS(Vector <Integer> edges[], int u,
                                  int v, int n)
    {
        // visited[n] for keeping track of visited
        // node in BFS
        Vector<Boolean> visited = new Vector<Boolean>(n);
          
        for (int i = 0; i < n; i++) {
            visited.addElement(false);
        }
       
        // Initialize distances as 0
        Vector<Integer> distance = new Vector<Integer>(n);
          
        for (int i = 0; i < n; i++) {
            distance.addElement(0);
        }
       
        // queue to do BFS.
        Queue<Integer> Q = new LinkedList<>();
        distance.setElementAt(0, u);
       
        Q.add(u);
        visited.setElementAt(true, u);
        while (!Q.isEmpty())
        {
            int x = Q.peek();
            Q.poll();
       
            for (int i=0; i<edges[x].size(); i++)
            {
                if (visited.elementAt(edges[x].get(i)))
                    continue;
       
                // update distance for i
                distance.setElementAt(distance.get(x) + 1,edges[x].get(i));
                Q.add(edges[x].get(i));
                visited.setElementAt(true,edges[x].get(i));
            }
        }
        return distance.get(v);
    }
      
    // method for addition of edge
    static void addEdge(Vector <Integer> edges[], int u, int v)
    {
       edges[u].add(v);
       edges[v].add(u);
    }
  
    // Driver method
    public static void main(String args[])
    {
        // To store adjacency list of graph
        int n = 9;
        Vector <Integer> edges[] = new Vector[9];
          
        for (int i = 0; i < edges.length; i++) {
            edges[i] = new Vector<>();
        }
          
        addEdge(edges, 0, 1);
        addEdge(edges, 0, 7);
        addEdge(edges, 1, 7);
        addEdge(edges, 1, 2);
        addEdge(edges, 2, 3);
        addEdge(edges, 2, 5);
        addEdge(edges, 2, 8);
        addEdge(edges, 3, 4);
        addEdge(edges, 3, 5);
        addEdge(edges, 4, 5);
        addEdge(edges, 5, 6);
        addEdge(edges, 6, 7);
        addEdge(edges, 7, 8);
        int u = 0;
        int v = 5;
        System.out.println(minEdgeBFS(edges, u, v, n));
    }
}
// This code is contributed by Gaurav Miglani

Python3

# Python3 program to find minimum edge 
# between given two vertex of Graph
import queue 
  
# function for finding minimum 
# no. of edge using BFS 
def minEdgeBFS(edges, u, v, n):
      
    # visited[n] for keeping track 
    # of visited node in BFS 
    visited = [0] *
  
    # Initialize distances as 0 
    distance = [0] * n
  
    # queue to do BFS. 
    Q = queue.Queue()
    distance[u] = 0
  
    Q.put(u) 
    visited[u] = True
    while (not Q.empty()):
        x = Q.get() 
          
        for i in range(len(edges[x])):
            if (visited[edges[x][i]]):
                continue
  
            # update distance for i 
            distance[edges[x][i]] = distance[x] + 1
            Q.put(edges[x][i]) 
            visited[edges[x][i]] = 1
    return distance[v]
  
# function for addition of edge 
def addEdge(edges, u, v):
    edges[u].append(v) 
    edges[v].append(u)
  
# Driver  Code
if __name__ == '__main__':
  
    # To store adjacency list of graph 
    n = 9
    edges = [[] for i in range(n)]
    addEdge(edges, 0, 1
    addEdge(edges, 0, 7
    addEdge(edges, 1, 7
    addEdge(edges, 1, 2
    addEdge(edges, 2, 3
    addEdge(edges, 2, 5
    addEdge(edges, 2, 8
    addEdge(edges, 3, 4
    addEdge(edges, 3, 5
    addEdge(edges, 4, 5
    addEdge(edges, 5, 6
    addEdge(edges, 6, 7
    addEdge(edges, 7, 8
    u = 0
    v = 5
    print(minEdgeBFS(edges, u, v, n))
  
# This code is contributed by PranchalK


Output:

3

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter