Last update: September 25, 2022  ce205 From: ref_link

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 DOC, 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
  • https://www.geeksforgeeks.org/tug-of-war/

---

Graph Backtracking

• n-Queen's Problem
• Geeks for Geeks
  • https://www.geeksforgeeks.org/n-queen-problem-backtracking-3/?ref=lbp

---

Graph Backtracking

• m Coloring Problem
• Geeks for Geeks
  • https://www.geeksforgeeks.org/m-coloring-problem-backtracking-5/
• Tutorials Point
  • https://www.tutorialspoint.com/M-Coloring-Problem#:~:text=The%20problem%20is%20to%20find,is%20assigned%20on%20which%20vertex.

---

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

1. Min Cuts

2. Max Cuts

3. Wikipedia

4. 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

• https://ucoruh.github.io/ce100-algorithms-and-programming-II/week-10/ce100-week-10-graphs/#cycle-detection

---

Graph Coloring

• https://ucoruh.github.io/ce100-algorithms-and-programming-II/week-10/ce100-week-10-graphs/#graph-coloring

---

Alpha-Beta Pruning

• Geeks for Geeks
• https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-4-alpha-beta-pruning/

---

Hasse Diagrams

• Geeks for Geeks
• https://www.geeksforgeeks.org/discrete-mathematics-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
  • https://www.geeksforgeeks.org/brents-cycle-detection-algorithm/
• Hare and Tortoise Algorithm
• Geeks for Geeks
  • https://www.geeksforgeeks.org/tag/tortoise-hare-approach/

---

Cycle Detection

• CE100
• https://ucoruh.github.io/ce100-algorithms-and-programming-II/week-10/ce100-week-10-graphs/?h=bipartite#cycle-detection

---

Bayesian Network

• https://towardsdatascience.com/introduction-to-bayesian-networks-81031eeed94e

---

\[ End-Of-Week-6 \]

---

Last update: September 25, 2022
Created: December 29, 2021

Contributors:
• Ugur Coruh (100.0%)