Last update: September 25, 2022 

CE205 Data Structures

Week-5

Graph Data Structure and Traversals

Download DOC, SLIDE, PPTX

---

Outline

• Introduction to Graphs
• Graph Representations
• Graph Traversal
• Water Jug Problem

---

Introduction to Graphs

• Vertex
• Edge

---

Introduction to Graphs

• Undirected Graph
• Directed Graph
• Mixed Graph

---

Introduction to Graphs

• End Vertices or Endpoints
• Origin
• Destination

---

Introduction to Graphs

• Adjacent
• Incident

---

Introduction to Graphs

• Outgoing Edge
• Incoming Edge

---

Introduction to Graphs

• Degree
• Indegree
• Outdegree

---

Introduction to Graphs

• Parallel edges or Multiple edges
• Self-loop
• Simple Graph
• Path

---

Introduction to Graphs

• Btech Smart Class
• http://www.btechsmartclass.com/data_structures/introduction-to-graphs.html

---

Graph Representations

1. Adjacency Matrix
2. Incidence Matrix

3. Adjacency List

4. Btech Smart Class

5. http://www.btechsmartclass.com/data_structures/graph-representations.html

---

Graph Traversal - DFS

1. Depth-First Search (DFS)

2. Iterative Deepening Search(IDS) or Iterative Deepening Depth First Search(IDDFS)

3. Btech Smart Class

4. http://www.btechsmartclass.com/data_structures/graph-traversal-dfs.html

---

Graph Traversal - BFS

• Breadth-First Search (BFS)
• Btech Smart Class
  • http://www.btechsmartclass.com/data_structures/graph-traversal-bfs.html

---

Graph Traversal - DLS

• Depth-limited Search
• Educba
  • https://www.educba.com/depth-limited-search/

---

Graph Traversal

• Uniform Cost Search
• Geeks for Geeks
  • https://www.geeksforgeeks.org/uniform-cost-search-dijkstra-for-large-graphs/

---

Graph Traversal

• Bidirectional Search
• Geeks for Geeks
  • https://www.geeksforgeeks.org/bidirectional-search/

---

Graph Traversal

• Water Jug Problem
• Geeks for Geeks
  • https://www.geeksforgeeks.org/water-jug-problem-using-bfs/
• Tamu Edu
  • https://www.math.tamu.edu/~dallen/hollywood/diehard/diehard.htm
• Udel Edu
  • https://www.eecis.udel.edu/~mccoy/courses/cisc4-681.10f/lec-materials/handouts/search-water-jug-handout.pdf

---

\[ End-Of-Week-5 \]

---

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

Contributors:
• Ugur Coruh (100.0%)