<style>
.markdown-body { max-width: 1800px; }
.orange { color: orange; }
.green { color: green; }
.red { color: red; }
section.present > div > pre > code {
max-height: 700px;
max-width: 2000px;
font-size: 16px;
}
section.present > div > blockquote > pre > code {
font-size: 16px;
}
section.present > div > blockquote > code {
font-size: 16px;
}
section.present > div > blockquote {
margin: calc(var(--r-block-margin) / 2) auto;
width: 800px;
}
h3 > span {
font-size: 60px;
color: #ff88ff;
}
h4 > span {
font-size: 60px;
color: #ee4400;
}
h5 > span {
font-size: 27px;
color: orange;
}
section.present > div > blockquote > p {
margin: 0;
}
.image-figure {
margin-right: 100px;
text-align: center;
}
.image-figure img {
height: 500px;
width: 500px;
}
.table {
width: 100%;
font-size: 20px;
}
.table td {
height: 100px;
width: 500px;
}
.table figure {
position: relative;
height: 150px;
margin: 0;
display: flex;
flex-direction: column;
align-items: center;
justify-content: flex-end;
}
.table img {
height: 100px;
margin: 0;
top: 0;
background: transparent;
}
figcaption {
text-align: center;
font-size: 27px;
width: 100%;
bottom: 0;
}
</style>
## Graph Traversal
---
## Graph Traversal
Graph traversal algorithms are techniques used to visit all nodes (or vertices) within a graph in a specific order. These algorithms are fundamental for various computational tasks such as searching, pathfinding, and connectivity analysis. As they traverse the graph, they can gather and compute relevant information.
---
## Graph Traversal
The most common graph traversal algorithms are depth first search (DFS) and breadth first search (BFS), each with its fundamental characteristics and applications. Their ideas are straightforward and simple to learn.
---
### I. Depth-First Search: DFS
#### I.1 - Abstract
Depth First Search (DFS) is a fundamental graph traversal algorithm that explores as deep into the graph as possible before backtracking. It can used to find the lexicographical smallest path from a source node to all reachable nodes by sorting the node's children beforehand (so-called topologically shortest path).
---
### I. Depth-First Search: DFS
#### I.2 - Background
Depth First Search (DFS) dates back to early graph theory studies and remains essential for modern applications in areas like AI, compilers, and network analysis. It follows a systematic approach of exploring as far as possible along a branch before retracing steps to explore unvisited paths. This characteristic makes DFS suitable for tasks requiring exhaustive exploration and backtracking, such as maze solving and topological sorting.
---
### I. Depth-First Search: DFS
#### I.3 - Concepts
> **Node**: Smallest individual unit of a graph abstractically represent a point or entity.
> **Edge**: The simplest relation of two nodes that define a pathway between them.
> **Stack**: Manages nodes need to be explored, can be used for the recursion.
> **Visited**: Keeps track of explored nodes, to avoid revisiting one node indefinitely.
> **Source**: The starting point for DFS traversal, can be considered as DFS root.
> **Path**: The sequence of traversed nodes using edges of pairwisely adjacent nodes.
> **Pre-order**: A parent node is processed before any of its child nodes is done.
> **Discovery Time**: Timestamp of a node's first visited in a traversal order.
> **Finish Time**: Timestamp of a fully visited nodes in a traversal order.
> **Depth**: Indicates how far into the graph DFS has traversed from the source.
> **Reachable Node**: A node that can be traversed via some paths starting from a source.
> **Adjacency Node**: A node that is directly reachable from another node through an edge.
---
### I. Depth-First Search: DFS
#### I.4 - Details: Ideas
```cpp=
Init:
Mark all nodes as unvisited.
If you want lexicographically smallest order, sort the node adjacency list.
Start at the root node or any arbitrary node (this is the DFS root).
Algo:
Mark the node as visited.
For each unvisited adjacent node, recursively call DFS.
Backtrack to the last visited node once all adjacent nodes are visited.
```
---
### I. Depth-First Search: DFS
#### I.4 - Details: Pseudo-code
```cpp=
dfs(node u):
mark u as visisted
for each unvisited adjacency node v
dfs(v)
```
---
### I. Depth-First Search: DFS
#### I.5 - Example: Simple Case
<center>
<figure style="margin-right: 100px; text-align: center;">
<img src="https://hackmd.io/_uploads/rkSXsqab1l.png" alt="" style="height:384px">
<figcaption>1. Given an example graph<br>This graph contains 9 nodes and 11 edges</figcaption>
</figure>
</center>
---
### I. Depth-First Search: DFS
#### I.5 - Example: Simple Case
<center>
<figure style="margin-right: 100px; text-align: center;">
<img src="https://hackmd.io/_uploads/S1s9RcaZ1e.png" alt="" style="height:384px">
<figcaption>2. We can represent the graph data in three common representations<br>Either matrix, edge list or adjacency list can help us with DFS</figcaption>
</figure>
</center>
---
### I. Depth-First Search: DFS
#### I.5 - Example: Simple Case
<center>
<figure style="margin-right: 100px; text-align: center;">
<img src="https://hackmd.io/_uploads/Hyx6JoTb1l.png" alt="" style="height:384px">
<figcaption>3. Let start with an arbitrary node, says node <b>(1)</b><br>This node will be our DFS root from now</figcaption>
</figure>
</center>
---
### I. Depth-First Search: DFS
#### I.5 - Example: Simple Case
<center>
<figure style="margin-right: 100px; text-align: center;">
<img src="https://hackmd.io/_uploads/rkb82q6Zkg.png" alt="" style="height:384px">
<figcaption>4. From <b>(1)</b> we can either traverse to <b>(2)</b>, <b>(3)</b> or <b>(4)</b><br>For lexicographically smallest DFS, we pick <b>(2)</b></figcaption>
</figure>
</center>
---
### I. Depth-First Search: DFS
#### I.5 - Example: Simple Case
<center>
<figure style="margin-right: 100px; text-align: center;">
<img src="https://hackmd.io/_uploads/SyE0A9TW1l.png" alt="" style="height:384px">
<figcaption>5. From <b>(2)</b> we can either traverse to the unvisited nodes <b>(3)</b> or <b>(4)</b><br>For lexicographically smallest DFS, we pick <b>(3)</b></figcaption>
</figure>
</center>
---
### I. Depth-First Search: DFS
#### I.5 - Example: Simple Case
<center>
<figure style="margin-right: 100px; text-align: center;">
<img src="https://hackmd.io/_uploads/HyAlkj6b1g.png" alt="" style="height:384px">
<figcaption>6. From <b>(3)</b>, we can only traverse to the unvisited node <b>(5)</b><br>Since all its other adjacency nodes <b>(1)</b> and <b>(2)</b> are already visisted<br>Notice that two edges <b>(3-5)</b> and <b>(6-9)</b> are crossed but <b>NOT</b> connected</figcaption>
</figure>
</center>
---
### I. Depth-First Search: DFS
#### I.5 - Example: Simple Case
<center>
<figure style="margin-right: 100px; text-align: center;">
<img src="https://hackmd.io/_uploads/H132xspZ1e.png" alt="" style="height:384px">
<figcaption>7. From <b>(5)</b>, we can traverse to either unvisited nodes <b>(7)</b> or <b>(8)</b><br>Again, we will choose <b>(7)</b> for obvious reason</figcaption>
</figure>
</center>
---
### I. Depth-First Search: DFS
#### I.5 - Example: Simple Case
<center>
<figure style="margin-right: 100px; text-align: center;">
<img src="https://hackmd.io/_uploads/H12PZs6WJl.png" alt="" style="height:384px">
<figcaption>8. From <b>(7)</b>, we can only traverse to the unvisited <b>(4)</b><br>Notice that two edges <b>(5-8)</b> and <b>(4-7)</b> are crossed but <b>NOT</b> connected</figcaption>
</figure>
</center>
---
### I. Depth-First Search: DFS
#### I.5 - Example: Simple Case
<center>
<figure style="margin-right: 100px; text-align: center;">
<img src="https://hackmd.io/_uploads/SJFnfs6Wyg.png" alt="" style="height:384px">
<figcaption>9. From <b>(4)</b>, we can only traverse to the unvisited <b>(7)</b><br>We can no longer visit any other nodes, so we stop the DFS</figcaption>
</figure>
</center>
---
### I. Depth-First Search: DFS
#### I.5 - Example: Simple Case
<center>
<figure style="margin-right: 100px; text-align: center;">
<img src="https://hackmd.io/_uploads/BJNfjsTZ1g.png" alt="" style="height:384px">
<figcaption>10. Let add little information to our DFS traversal at root <b>(1)</b><br>Only two nodes aren't visisted are <b>(6)</b> and <b>(9)</b></figcaption>
</figure>
</center>
---
### I. Depth-First Search: DFS
#### I.5 - Example: Simple Case
<center>
<figure style="margin-right: 100px; text-align: center;">
<img src="https://hackmd.io/_uploads/S1h58sTWyg.png" alt="" style="height:384px">
<figcaption>11. Here is our DFS Tree, with depth marked<br>Excepts the two nodes <b>(6)</b> and <b>(9)</b> are not reachable from (1)</figcaption>
</figure>
</center>
---
### I. Depth-First Search: DFS
#### I.6 - Specials
In some tree structures, DFS can find the shortest path as the path between two nodes is always unique, but in general graphs, it may not find the shortest path.
---
## Breadth-First Search: BFS
{"title":"Star Edu, Graph Theory","description":"DFS and","contributors":"[{\"id\":\"a22ea847-846d-438a-bc33-27664a818ea5\",\"add\":13172,\"del\":3565}]"}