CE205 Data Structures¶
Week-6¶
Graph MST, Backtracking, Topological Sorting, Shortest Paths, Connectivity,Max Flow and Cycle Detection Algorithms.¶
Graph Isomorphism and canonization¶
Graph Cuts¶
Download PDF,DOCX, SLIDE, PPTX
Outline-1¶
- Graph Topological Sorting
- Graph MST
- Graph Backtracking
- Tug of War
- n-Queen's Problem
- m Coloring Problem
- Euler & Hamiltonian Path
Outline-2¶
- Graph Sortest Paths
- Graph Connectivity - SCC
- Graph Max Flow
- Graph Isomorphism
- Graph canonization
- Graph Cuts
- Min Cut
- Max Cut
Outline-3¶
- Alpha-Beta Pruning
- Hasse Diagrams
- Petri Nets
- Bipartite Graphs
- Cycle Detection
- Brent’s Algorithm
- Hare and Tortoise Algorithm
- Bayesian Network
Graph Topological Sorting¶
- CE100
- https://ucoruh.github.io/ce100-algorithms-and-programming-II/week-10/ce100-week-10-graphs/?h=topolo#directed-acyclic-graphs-dag
- Geeks for Geeks
- https://www.geeksforgeeks.org/topological-sorting/
Graph MST¶
- CE100
- https://ucoruh.github.io/ce100-algorithms-and-programming-II/week-10/ce100-week-10-graphs/?h=mst#minimum-spanning-tree-mst
- Geeks for Geeks
- https://www.geeksforgeeks.org/prims-minimum-spanning-tree-mst-greedy-algo-5/
Graph Backtracking¶
- Tug of War
- Geeks for Geeks
Graph Backtracking¶
- n-Queen's Problem
- Geeks for Geeks
Graph Backtracking¶
- m Coloring Problem
- Geeks for Geeks
- Tutorials Point
Graph Backtracking¶
- Euler & Hamiltonian Path
- https://www.geeksforgeeks.org/mathematics-euler-hamiltonian-paths/
Graph Sortest Paths¶
- Single-Source Shortest Paths (SSSP)
- https://ucoruh.github.io/ce100-algorithms-and-programming-II/week-11/ce100-week-11-shortestpath/
- https://visualgo.net/en/sssp?slide=1
Graph Connectivity¶
- Strongly Connected Components
- https://ucoruh.github.io/ce100-algorithms-and-programming-II/tr/week-10/ce100-week-10-graphs/?h=scc#strongly-connected-components-scc
Graph Max Flow¶
- Geeks for Geeks
- https://www.geeksforgeeks.org/max-flow-problem-introduction/
Graph Isomorphism¶
- https://www.sciencedirect.com/science/article/pii/S0747717113001193
- https://www3.cs.stonybrook.edu/~algorith/implement/nauty/implement.shtml
- https://github.com/Mith13/Graphs-isomorphism
Graph Cuts¶
- Min Cuts
-
Max Cuts
-
Wikipedia
- https://en.wikipedia.org/wiki/Cut_(graph_theory)#:~:text=In%20graph%20theory%2C%20a%20cut,said%20to%20cross%20the%20cut.
Graph canonization¶
- Wikipedia
- https://en.wikipedia.org/wiki/ Graph_canonization
Cycle Detection¶
Graph Coloring¶
Alpha-Beta Pruning¶
- Geeks for Geeks
- https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-4-alpha-beta-pruning/
Hasse Diagrams¶
Petri Nets¶
- Wikipedia
- https://en.wikipedia.org/wiki/Petri_net
Bipartite Graphs¶
- CE100
- https://ucoruh.github.io/ce100-algorithms-and-programming-II/week-10/ce100-week-10-graphs/?h=bipartite#biparitite-checker
- Geeks for Geeks
- https://www.geeksforgeeks.org/bipartite-graph/
Cycle Detection¶
- Brent’s Algorithm
- Geeks for Geeks
- Hare and Tortoise Algorithm
- Geeks for Geeks
Cycle Detection¶
Bayesian Network¶
\[ End-Of-Week-6 \]