Count the minimum number of edges between two vertices of a Graph

Algorithm

We will implement the minEdgeBFS(int x, int y, int n) function: 

Step 1: We will maintain a visited array and a distance array and initialize the distance array to 0 for all vertices.

Step 2: Now, we will maintain a Queue for doing the Breadth-first search.

Step 3: Pop vertex x from the queue.

Step 4: While pushing all adjacent non-visited vertices(i) back into the queue at the same time, update:

distance[i] = distance[u] + 1;

Step 5: Return distance[y], the minimum edges between x and y.

Let us see the implementation of this approach in the next section of this blog.

Implementation in 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;
@SuppressWarnings("unchecked")


class Test
{
	//counting minimum edges using BFS
	static int minEdgeBFS(Vector <Integer> edges[], int x,
	int y, int n)
	{
		// visited[n]: to keep track of visited nodes 
		Vector<Boolean> visited = new Vector<Boolean>(n);

		for (int i = 0; i < n; i++) {
			visited.addElement(false);
		}

		// Initializing distances to 0
		Vector<Integer> distance = new Vector<Integer>(n);

		for (int i = 0; i < n; i++) {
			distance.addElement(0);
		}

		// queue for doing BFS
		Queue<Integer> Q = new LinkedList<>();
		distance.setElementAt(0, x);

		Q.add(x);
		visited.setElementAt(true, x);
		while (!Q.isEmpty())
		{
			int u = Q.peek();
			Q.poll();

			for (int i=0; i<edges[u].size(); i++)
			{
				if (visited.elementAt(edges[u].get(i)))
					continue;

				// updating distance for i
				distance.setElementAt(distance.get(u) + 1,edges[u].get(i));
				Q.add(edges[u].get(i));
				visited.setElementAt(true,edges[u].get(i));
			}
		}
		return distance.get(y);
	}

	static void includeEdge(Vector <Integer> edges[], int x, int y)
	{
		edges[x].add(y);
		edges[y].add(x);
	}


	// Driver method
	public static void main(String args[])
	{
		// storing 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<>();
		}

		includeEdge(edges, 0, 1);
		includeEdge(edges, 0, 7);
		includeEdge(edges, 1, 7);
		includeEdge(edges, 1, 2);
		includeEdge(edges, 2, 3);
		includeEdge(edges, 2, 5);
		includeEdge(edges, 2, 8);
		includeEdge(edges, 3, 4);
		includeEdge(edges, 3, 5);
		includeEdge(edges, 4, 5);
		includeEdge(edges, 5, 6);
		includeEdge(edges, 6, 7);
		includeEdge(edges, 7, 8);
		int x = 2;
		int y = 4;
		System.out.println(minEdgeBFS(edges, x, y, n));
	}
}

You can also try this code with Online Java Compiler

Run Code

Output:

2

Implementation in C++

#include<bits/stdc++.h>
using namespace std;

//counting minimum edges using BFS
int minEdgeBFS(vector <int> edges[], int x,
int y, int n)
{
	// visited[n]: to keep track of visited nodes 
	vector<bool> visited(n, 0);


	// Initialize distances as 0
	vector<int> dist(n, 0);


	// queue to do BFS.
	queue <int> Queue;
	dist[x] = 0;


	Queue.push(x);
	visited[x] = true;
	while (!Queue.empty())
	{
		int u = Queue.front();
		Queue.pop();


		for (int i=0; i<edges[u].size(); i++)
		{
			if (visited[edges[u][i]])
			continue;


			// update distance for i
			dist[edges[u][i]] = dist[u] + 1;
			Queue.push(edges[u][i]);
			visited[edges[u][i]] = 1;
		}
	}
	return dist[y];
}


// function for addition of edge
void addEdge(vector <int> edges[], int x, int y)
{
	edges[x].push_back(y);
	edges[y].push_back(x);
}


// 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 x = 2;
	int y = 4;
	cout << minEdgeBFS(edges, x, y, n);
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

2

Implementation in Python

import queue

# finding minimum no. of edge using BFS
def minEdgeBFS(edges, x, y, n):

	# visited[n] to keep track of visited node
	visited = [0] * n


	# Initializing distance to 0
	dist = [0] * n


	# queue to do BFS.
	Q = queue.Queue()
	dist[x] = 0


	Q.put(x)
	visited[x] = True
	while (not Q.empty()):
		u = Q.get()

	for i in range(len(edges[u])):
		if (visited[edges[u][i]]):
			continue


		# updating distance for i
		dist[edges[u][i]] = dist[u] + 1
		Q.put(edges[u][i])
		visited[edges[u][i]] = 1
		return dist[y]


# function for addition of edge
def addEdge(edges, x, y):
	edges[x].append(y)
	edges[y].append(x)


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)
	x = 2
	y = 4
	print(minEdgeBFS(edges, x, y, n))

You can also try this code with Online Python Compiler

Run Code

Output:

2

Complexity Analysis

Time complexity

This approach will take O(V+E) times where V is vertices and E is the number of edges.

Space complexity: 

O(V), as V vertices can be present in the queue in the worst case.

Check out this problem - Queue Implementation

Frequently Asked Questions

Which is faster in terms of speed, BFS or DFS?

DFS is faster in terms of speed than BFS.

What is the maximum number of edges that a bipartite graph can have?

A bipartite graph can have most: (node with color 0) * (node with color 1) number of edges.

What is directed and undirected graphs?

Edges in directed graphs point from one end of the graph to the other. The edges in undirected networks merely link the nodes at each end.

Conclusion

In this blog, we discussed how to count the minimum number of edges between two vertices of a Graph. We understood this problem with the help of an example. Then we discussed its algorithm. After that, we discussed its implementations in other languages like C++ , Python3 and java. In the end, we saw the complexity analysis of the approach.  

Recommended Readings:

• Detect cycle in an undirected graph

For more content, Refer to our guided paths on Coding Ninjas Studio to upskill yourself.

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!