3. Szélességi keresés

A Kombinatorika és gráfelmélet 1. tárgyból megismert szélességi keresés algoritmussal megtalálhatunk egy lehető legkevesebb élből álló utat egy gráfban két adott csúcs között. A feladat ennek az algoritmusnak a beprogramozása.
Az algoritmus bemenete egy irányított egyszerű gráf, amit a következő módon adunk meg egy szöveges (.text) fájlban:
1. A fájl első sorában az \(N\), \(M\), \(S\) és \(T\) természetes számok találhatóak szóközökkel elválasztva.
  - A \(\vec{G} = (V, \vec{E})\) irányított egyszerű gráf csúcsai a \(V = \{0, 1, 2, \ldots, N-1\}\) számok.
  - Az élek száma \(\left| \vec{E} \right| = M\).
  - Az \(S \in V\) csúcsból szeretnénk egy legkevesebb élből álló utat keresni a \(T \in V\) csúcsba (\(S \ne T\)).
2. A fájl további \(M\) sora rendre \(U_i\), \(V_i\) számpárokat tartalmaz. Egy ilyen számpár megfelel egy \((U_i, V_i) \in \vec{E}\) élnek. Egy él csak egyszer szerepel a fájlban.
3. A program, ha létezik út az \(S\) és \(T\) csúcsok között, akkor az \(S\) csúccsal kezdve sorban megadja annak csúcsait a \(T\) csúcsig. Ha nincs út, akkor kiírja, hogy „Nem létezik út!”.
Segítségképp megadjuk a graph.py fájlban a gráfot beolvasó és a megtalált utat kiíró függvényt, így csak magát a keresést kell megvalósítani az utat_keres függvényben.
1. A függvény első, graf paramétere a gráf éllistás ábrázolása. Az éllistát egy szótárral (dictionary) adjuk meg, melyben minden csúcshoz egy lista tartozik. A lista elemei a kimenő éleken elérhető csúcsok. Például az alábbi fájlban leírt gráfhoz
```
6 8 2 5
1 0
2 1
3 2
1 3
0 5
2 4
4 5
4 3
	
```
  tartozó éllista
```
graf = {0: [5], 1: [0, 3], 2: [1, 4], 3: [2], 4: [5, 3], 5: []}
	
```
2. A honnan paraméter az út első, \(S\) csúcsát, míg a hova paraméter az út utolsó, \(T\) csúcsát adja meg.
3. A megoldáshoz felhasználható az utat_kiolvas függvény, ami egy (nem feltétlenül teljes) szélességi fából kiolvas egy utat a honnan és hova csúcsok között. A szélességi fát a szulo szótárban kell megadni, ahol az egyes csúcsokhoz rendelt érték a szülőjük azonosítója a szélességi fában. Például
```
szulo = {1: 2, 4: 2, 0: 1, 3: 1, 5: 4}
honnan = 2
hova = 5
	
```
  esetén egy legrövidebb út [2, 4, 5].
4. Az algoritmus megvalósításánál nem szükséges az éleket fa-, előre-, vissza- és keresztélekre bontani, mivel ezek nélkül is kiolvasható egy legrövidebb út. Az egész gráfot sem kell bejárni, elég akkora részét, hogy meg lehessen találni egy legrövidebb utat.
5. Várakozási sor megvalósítására alkalmasak a beépített listák append és pop(0) függvényei, de ki lehet próbálni a Python 3 queue modulját is.
Próbáljuk ki az elkészült programot a graph1.text és graph2.text bemenetekre, de teszteljük más, saját készítésű teszbemeneteken is!