# 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.
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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 ` `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[], ``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; ` `    ``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 edges[], ``int` `u, ` `                                  ``int` `v, ``int` `n) ` `    ``{ ` `        ``// visited[n] for keeping track of visited ` `        ``// node in BFS ` `        ``Vector visited = ``new` `Vector(n); ` `         `  `        ``for` `(``int` `i = ``0``; i < n; i++) { ` `            ``visited.addElement(``false``); ` `        ``} ` `      `  `        ``// Initialize distances as 0 ` `        ``Vector distance = ``new` `Vector(n); ` `         `  `        ``for` `(``int` `i = ``0``; i < n; i++) { ` `            ``distance.addElement(``0``); ` `        ``} ` `      `  `        ``// queue to do BFS. ` `        ``Queue 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[], ``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 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``] ``*` `n  ` ` `  `    ``# 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
```

## tags:

Graph BFS Graph BFS