7.4 Graph theory
7.4 Graph theory — learning path connecting EDA fundamentals to open practice.
In this section
Floyd multi-source shortest paths
Freud's algorithm is a classic algorithm for finding the shortest path. Compared wit…
027.4.11 SCCs and Kosaraju
Recall that when we were working on undirected graphs, we used depth-first search to solv…
037.4.12 Min-cost flow
Given a network G = ( V , E ) G=(V,E) G = ( V , E ) , in addition to the capacity limit c…
047.4.1 Graph theory basics
If G G G is an undirected graph, then each element in E E E is an unordered tuple ( u , v…
057.4.2 Search & backtracking
The backtracking algorithm (DFS depth-first algorithm) is actually an enumeration-like se…
06DFS
The DFS algorithm is: Depth First Search, depth first search. The key to this algorithm i…
077.4.4 Networks with lower/upper bounds
The essence of upper and lower bound network flow is to set an upper traffic bound c (u, …
087.4.5 Maximum-weight bipartite matching
The Hungarian algorithm, also known as the KM algorithm, can find the maximum weight perf…
09Maximum bipartite matching
This article talks about maximum matching and perfect matching of unweighted bipartite gr…
107.4.7 Bidirectional search
The basic idea of two-way simultaneous search is to start wide search or deep search from…
11Hamiltonian cycles and paths
Source of the problem: In 1859, the Irish mathematician and astronomer Hamilton proposed …
12Graph coloring & Hungarian algorithm
Bipartite graph: Divide all points into two sets so that all edges only appear between th…