1. Introduction to Graph Algorithms

Notation

We expand our notation for termination time for algorithms and apply this to graphs:

$$T(|V|,|E|)=\begin{array}{c}\text{number of primitive operations on a}\\ \text{graph with }|V|\text{ verticies and }|E|\text{ edges}\end{array}$$

Primitive operations can be performed in $O(1)$ steps.

Algorithm: Breadth First Search

Breadth First Search (Algorithm)

$\text{BFS}(G)$:

1. Select root vertex and add to a Queue (ADT)
2. While queue is not empty:
   1. Inspect first element $u$ in queue
   2. Add unvisited neighbours of $u$ to queue
   3. Remove $u$ from queue

Link to original

Theorem: The termination time for Breadth-First-Search is $O(|V|+|E|)$.

• Every vertex is enqueued or dequeued at most once.
• Steps 2.1 to 2.3 are repeated once for each $u\in V$.
• Inspecting (2.1) and removing (2.3) take a constant amount (at most $O(1)$) number of steps.
• Step 2.2 requires $O(|\text{Adj}(u)|)$ operations to queue each of the adjacent vertices to $u$. Where $\text{Adj}(u)$ denotes the set of vertices adjacent to $u$.
• Hence we sum all of these terms: $$\begin{array}{rl}T(|V|,|E|)& =\sum _{u\in V}\left(\begin{array}{c}O(1)+O(|\text{Adj}(u)|+O(1)\end{array}\right)\\ & =O(|V|)+O(|E|)+O(|V|)\\ & =O(2|V|)+O(|E|)\\ & =O(|V+E|)\end{array}$$

Example Search

{
	"url":"[week4_bfsdfs.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%202/Semester%201/5CCS2FC2%20Foundations%20of%20Computing%202/Resources/Slides/week4_bfsdfs.pdf)",
	"page":[5,6,7,8,9,10,11,12,13,14,15,16],
	"scale":1.5
}

Algorithm: Depth First Search

Depth First Search (Algorithm)

$\text{DFS}(G)$:

1. Select root vertex and add to a Stack (ADT)
2. While stack is not-empty:
   1. Inspect top element $u$ on the stack
   2. Add any unvisited neighbours of $u$ to the stack
   3. Remove $u$ from the stack

Link to original

Example Search

{
	"url":"[week4_bfsdfs.pdf](https://git.is.horse/insert/university/obsidian-notes/-/raw/9d95afcbbdb7a4c77ca9f62b32e35c6f31e269e7/University/Year%202/Semester%201/5CCS2FC2%20Foundations%20of%20Computing%202/Resources/Slides/week4_bfsdfs.pdf)",
	"page":[19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42],
	"scale":1.5
}