Traversal

Pseudocode

1
2
3
4
5
6
7
8

Add item onto stack/queue

while stack/queue is not empty {
  dequeue/pop
  mark item as visited
  -> perform operations here if needed
  add neighbouring nodes
}

• DFS - Stack
  
• BFS - Queue
  

Find shortest (non-weighted) -> BFS (from a or b) (to b or a)

// DFS Search Example

// BFS Search Example

Spanning Tree

Kruskal's Algorithm

• Sort min max
• Add edges incrementally (as long as they don’t lead to a cycle)
  • Add edge, if cycle created
  • Remove edge

Prim's Algorithm

• Start at any
• Add neighbouring vertices