Graph

class: center, middle, inverse, title-slide

.title[
# Graph
]
.subtitle[
## in data structures and algorithms
]
.author[
### Awais Shah
]
.date[
### (2024-06-30)
]

---

************

# Data Structures
<blockquote>
Data Structure is a way to store and organize data
</blockquote>
### Linear Data Structures (sequential)
Each element has a direct successor and/or predecessor
- Array.
- Linked list.
- Stack.
- Queue

### Non-linear Data Structures
- Tree
- Graph

---

## Graph

<blockquote>
  A graph \( G = \langle V , E \rangle \) is defined by a pair of two sets: a finite nonempty set \( V \) of items called <b>vertices</b> and a set \( E \) of pairs of these items called <b>edges</b>.
</blockquote>

`\( G = \langle V , E \rangle \)` can be an ordered pair or an unordered pair
#### Vertices (nodes): 
<blockquote>
Vertices represent the fundamental units or entities within a graph. Each vertex can represent an object, entity, or a distinct data point depending on the application. 
</blockquote>

#### Edges:
<blockquote>
Edges connect pairs of vertices in a graph. They represent relationships or connections between the entities represented by vertices. Edges can be directed, undirected, weighted or unweighted.
</blockquote>

---
# Graph Example
<div class="content">
  <div class="text">
    <p>This figure is an example of an *undirected* and *unweighted* graph.</p>
    <p> <b>a,b,c,d,e,f</b> are the **nodes** or **vertices** of the graph while the lines connecting them are the **edges** of the graph </p>
    <p> It can also be represented by an adjacency matrix</p>
    <p>`\(V ={a,b,c,d,e,f},E={(a,c),(a,d),(b,c),(b,f),(c,e),(d,e),(e,f)}\)`</p>
    
  </div>
  <div class="images">
    <img src="https://i.imgur.com/2QO4dZr.png" alt="Graph 1" class="image-medium">
    <img src="https://i.imgur.com/1n2AWG3.png" class="image-medium">
  </div>
</div>
<style>
.content {
  display: flex;
  align-items: center;
}

.text {
  flex: 1;
}

.images {
  flex: 10;
  display: flex;
  flex-direction: column;
  align-items: flex-end;
}

.image-medium {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
}
</style>

---
# Graph Example cont.
<div class="content">
  <div class="text">
    <p>Another representation of Graph is the **adjacency list**.</p>
    <p> The adjacency list of a graph is a collection of linked lists, one for each vertex, that contain all the vertices adjacent to the list’s vertex. </p>
    <p> Usually, such lists start with a header identifying a vertex for which the list is compiled.</p>
    <p>When there are a large number of nodes and small number of edges, the adjacency matrix representation takes a lot more space. In such cases, the adjacency list representation is more efficient to use.</p>
    
  </div>
  <div class="images">
    <img src="https://i.imgur.com/2QO4dZr.png" alt="Graph 1" class="image-medium">
    <img src="https://i.imgur.com/GBjI2O3.png" alt="Graph 2" class="image-medium">
  </div>
</div>
<style>
.content {
  display: flex;
  align-items: center;
}

.text {
  flex: 1;
}

.images {
  flex: 10;
  display: flex;
  flex-direction: column;
  align-items: flex-end;
}

.image-medium {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
}
</style>

---
# Graph Types
### Undirected Graph
<blockquote>
A graph where edges have no direction. The connection between any two vertices is bidirectional.
</blockquote>

### Directed Graph (digraph)
<blockquote>
A graph where edges have a direction, indicating the connection flows from one vertex to another in a specific direction.
</blockquote>

### Unweighted Graph 
<blockquote>
A graph where all edges are considered equal, having no associated weights or values.
</blockquote>

### Weighted Graph 
<blockquote>
A graph where edges have weights or values assigned to them, representing the cost, distance, or any other metric of the connection between vertices.
</blockquote>

---
# Graph Type Examples

<div class="content">
  <div class="image-container">
    <img src="https://i.imgur.com/7hy8V71.png" alt="Directed Graph" class="image-large">
    <p class="image-caption">Directed Graph</p>
  </div>
  <div class="image-container">
    <img src="https://i.imgur.com/4uWtu1W.png" alt="Weighted Graph" class="image-large">
    <p class="image-caption">Weighted Graph</p>
  </div>
</div>

.image-container {
  width: 45%; /* Adjust the width as needed */
  text-align: center;
}

.image-large {
  width: 100%;
  display: block;
  margin: 0 auto;
}

.image-caption {
  margin-top: 5px;
  font-size: 20px;
  font-style: italic;
  text-align: center;
}
</style>
---

# Graph Classification

<div class="content">
  <div class="text">
  <h3> Complete Graph </h3>
    <blockquote>A graph where every pair of distinct vertices is connected by a unique edge.</blockquote>
    <h3> Dense Graph </h3>
    <blockquote> A graph in which the number of edges is close to the maximal number of edges. </blockquote>
    <h3> Sparse Graph </h3>
    <blockquote>
    A graph in which the number of edges is close to the minimal number of edges.
    </blockquote>

</div>
  <div class="images">
    <img src="https://i.imgur.com/dbP1hK4.png" alt="Graph 5" class="image-small">
    <img src="https://i.imgur.com/OucJ4Zz.png" alt="Graph 6" class="image-small">
    <img src="https://i.imgur.com/1oSJJ5y.png" alt="Graph 7" class="image-small">

</div>
</div>
<style>
.content {
  display: flex;
  align-items: center;
}

.text {
  flex: 1;
}

.images {
  flex: 1;
  display: flex;
  flex-direction: column;
  align-items: flex-end;
}

.image-small {
  width: 40%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
}
</style>

---
# Graph Real World Example
### Social Media
</div>
  <div class="images">
    <img src="https://i.imgur.com/WaylVbd.png" alt="Graph 8" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>
---
# Graph Real World Example
### Social Media
</div>
  <div class="images">
    <img src="https://i.imgur.com/EH2DHqa.png" alt="Graph 9" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>

---
# Graph Real World Example
### Social Media
</div>
  <div class="images">
    <img src="https://i.imgur.com/kIgiMfH.png" alt="Graph 10" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>
---
# Graph Real World Example
## Social Media
### Standard Graph Problem
<blockquote>
The problem observed in the above example is known as the standard graph problem and the Breath-First Search (BFS) algorithm is used to solve it.<p> Using BFS we find all nodes having length of the shortest path from Rama equal to 2.
</p>

</blockquote>
---
# Graph Real World Example
### Inter-city road network (unweighted and undirected)
</div>
  <div class="images">
    <img src="https://i.imgur.com/X15VRpf.png" alt="Graph 11" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>
---
# Graph Real World Example
### Inter-city road network (weighted)
</div>
  <div class="images">
    <img src="https://i.imgur.com/2ZLRoVo.png" alt="Graph 12" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>
---
# Graph Traversal
There are 2 main types of Graph traversal.
1. Breath first search.
2. Depth first search.

### Breath first search (BFS)
 Algorithm for traversing or searching through a graph or tree data structure.
 <p>It starts at a selected node (called the <i>root</i> or <i>starting node</i>) and explores all its neighboring nodes at the present depth level before moving on to nodes at the next depth level. </p>
<p>BFS uses a <i>queue</i> to keep track of the nodes to be explored and ensures that each node is processed in the order it was discovered. This makes BFS suitable for finding the shortest path in unweighted graphs.
</p>
---
# Graph traversal via BFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/YB2IrSU.png" alt="Graph 14" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>

---
# Graph traversal via BFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/mhLh3PA.png" alt="Graph 15" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>
---
# Graph traversal via BFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/8UXBkKh.png" alt="Graph 16" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>
---
# Graph traversal via BFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/d4N5kk6.png" alt="Graph 17" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>

---
# Graph traversal via BFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/QSMc5Eu.png" alt="Graph 18" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>

---
# Graph traversal via BFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/QkppnR9.png" alt="Graph 19" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>

---

# Graph traversal via BFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/qlDOjeW.png" alt="Graph 20" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>

---
# Graph traversal 
### Depth first search (DFS)
<p>Depth-First Search (DFS) is an algorithm for traversing or searching tree or graph data structures. </p>
<p>It starts at a selected node (called the root or starting node) and explores as far as possible along each branch before <i>backtracking</i>.</p>
<p>DFS uses a stack to keep track of the path being explored and ensures each node is visited exactly once.</p>

#### Backtracking
- When DFS reaches a node with no unvisited neighbors, it backtracks to the previous node (the node from which it arrived).
---
# Graph traversal via DFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/T7iodRw.png" alt="Graph 21" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>
---
# Graph traversal via DFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/EjX4g3K.png" alt="Graph 22" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
</style>
---
# Graph traversal via DFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/sJTLwRd.png" alt="Graph 23" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
    margin-left: 30px; /* Shift the image to the right */
</style>
---
# Graph traversal via DFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/Q9f0CIU.png" alt="Graph 24" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
  margin-left: 20px; /* Shift the image to the right */
</style>
---
# Graph traversal via DFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/lofc4zi.png" alt="Graph 25" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
  margin-left: 20px; /* Shift the image to the right */
</style>
---
# Graph traversal via DFS
</div>
  <div class="images">
    <img src="https://i.imgur.com/DJWNpdC.png" alt="Graph 26" class="image-large">
  </div>
<style>
.image-large {
  width: 80%; /* Adjust the size as needed */
  margin-bottom: 10px; /* Space between images */
  margin-left: 20px; /* Shift the image to the right */
</style>
---
# Summary 
- Graph definition
- Types
- Classification
- 2 real world examples
- BFS traversal
- DFS traversal
---
class: center,middle,inverse
# Thank you