Adatstrukt 06 Gráfalgoritmusok

Question 1

Hogyan működik a szélességi keresés (BFS)?

Answer 1

Sorral működik, szintek szerint járja be a gráfot, és megtalálja a legrövidebb utat.

Question 2

Hogyan működik a mélységi keresés (DFS)?

Answer 2

Veremmel vagy rekurzívan működik, amíg lehet, mélyre megy, majd visszalép.

Question 3

Mi a különbség a BFS és a DFS között?

Answer 3

BFS szintenként, DFS mélység szerint járja be a gráfot.

Question 4

Mi a minimális feszítőfa?

Answer 4

Olyan fa, ami összeköti a gráf összes csúcsát minimális élösszeggel, kör nélkül.

Question 5

Hogyan működik a Prim algoritmus?

Answer 5

Mohó algoritmus, egy csúcsból indul, mindig a legkisebb éllel bővít.

Question 6

Hogyan működik a Kruskal algoritmus?

Answer 6

Mohó algoritmus, éleket súly szerint sorba rendez, körmentesen építi a fát.

Question 7

Mi a Dijkstra algoritmus lényege?

Answer 7

Negatív él nélkül működik, kupaccal és relaxálással keresi a legrövidebb utat.

Question 8

Miben különbözik a Bellman-Ford algoritmus a Dijkstrától?

Answer 8

Negatív éleket is kezel, lassabb, de fokozatosan közelít.

Question 9

Hogyan működik a Ford-Fulkerson módszer?

Answer 9

Reziduális hálózatban javítóutakat keres, és addig növeli a folyamot, amíg lehet.

Question 10

Mi az Edmonds-Karp algoritmus?

Answer 10

A Ford-Fulkerson BFS-alapú változata, ami javítóutakat BFS-sel keres.