3. Breadth first search (BFS)

Loading [MathJax]/extensions/Safe.js

3. Breadth first search (BFS)

Using the Breadth first search (BFS) algorithm known from the subject Combinatorics 1, we can find the shortest possible path in a graph between two given vertices. The task is to program this algorithm.
The input of the algorithm is a simple directed graph, which is defined as follows in a text (.text) file:
1. The first line of the file contains the natural numbers \(N\), \(M\), \(S\), \(T\) separated by spaces.
  - The set of vertices of the simple directed graph \(\vec{G} = (V, \vec{E})\) is \(V = \{0, 1, 2, \ldots, N-1\}\).
  - The number of edges is \(\left| \vec{E} \right| = M\).
  - We would like to find the shortest directed path from the vertex \(S \in V\) to the vertex \(T \in V\) (\(S \ne T\)).
2. The next \(M\) lines contain "\(U_i\) \(V_i\)" pairs of numbers. Such a pair represent the edge \((U_i, V_i) \in \vec{E}\). An edge appears only once in the file.
3. If there is a path from \(S\) to \(T\), the program lists the vertices starting with \(S\) and finished with \(T\). If there is no path, it prints out "no path".
As a help we give a file graph.py, where we provide the input function of the graph and the output function of the path. So the search function search_path has to be written.
1. The first parameter of this funcion is graph. This is the edge-list representation of the graph. The edge-list is given in a dictionary, where a list is belonging to every vertex. The elements in the list are vertices available by the outgoing edges. For example look at the graph of 6 vertices and 8 edges given in the next file
```
6 8 2 5
1 0
2 1
3 2
1 3
0 5
2 4
4 5
4 3
	
```
  The next edge-list belongs to this graph
```
graph = {0: [5], 1: [0, 3], 2: [1, 4], 3: [2], 4: [5, 3], 5: []}
	
```
2. The next parameter of the function from_where gives the first vertex \(S\) and the third parameter to_where gives the last vertex \(T\).
3. You may use the read_path function, which read out a path from a (not necessarily complete) BFS-tree between the from_where and to_where vertices. The BFS-tree is given in the parent dictionary, where the value assigned to a vertex is the number of its parent in the tree. For example in the case of
```
parent = {1: 2, 4: 2, 0: 1, 3: 1, 5: 4}
from_where = 2
to_where = 5
	
```
  the shortest path is [2, 4, 5].
4. When implementing the algorithm, it is not necessary to split the edges into classes (forward, backward,...), and not necessary to search in the whole graph, it is enough to find one shortest path.
5. Buil-in list functions like append and pop(0) can be used to implement a queue. (But one may try the modul queue in Python 3.)
Test your program on the files graph1.text and graph2.text files, but also on other self-made input files!