الگوریتمهای گراف (BFS)
Graph Algorithms (BFS)
الگوریتمهای گراف؛ جستوجوی اولسطح (BFS).
طراحی الگوریتم کنکور ارشد علوم کامپیوتر
کارتها · 5
On adjacency lists, BFS touches every undirected edge twice (once per endpoint), giving total work Θ(V+E) .
Kruskal sorts edges by weight and accepts an edge only if its endpoints lie in different components; otherwise it would close a cycle and is rejected.
Greedily build a cheapest set of edges that connects all vertices with no cycle, using exactly n-1 edges.
In any flow network the value of a maximum s - t flow equals the capacity of a minimum s - t cut; a flow is maximum exactly when its residual graph has no augmenting path, which is how Ford-Fulkerson finds it.
Trace BFS (queue) and DFS (stack/recursion) deterministically by breaking every tie in alphabetical order — and read off the first/last vertex visited.