Notes from CS2040S Week 9 Lecture 2 on Graphs

cs2040s_w9_l2.md

CS2040S Week 9 Lecture 2

Notes from Week 9 Lecture 2 on Graphs

BFS

Properties of parent edges

• They form a tree (shortest path tree)
  • There are no cycles – all nodes visited only once
• Parent edges are always shortest paths from starting node s
• For now, all edges have weight/distance 1

DFS

• Follow path until stuck
• Backtrack along breadcrumbs until reach unexplored neighbour
• Recursively search

Algorithm

1. Follow path until stuck
2. Backtrack until you find a new edge
3. Recursively explore it
4. Don't repeat a vertex

DFS-visit(Node[] nodelist, boolean[] visited, int startID):
	for (Integer v: nodelist[startID].nbors):
		if (!visited[v]):
			visited[v] = true
			DFS-visit(nodelist, visited, v)

DFS(Node[] nodelist):
	boolean[] visited = new boolean[nodelist.length]
	Arrays.fill(visited, false)
	
	for (start = 0, start < nodelist.length, start++):
				

Parent graph is the graph where DFS traversal edge takes – so only those edges are marked.

Properties of DFS parent graph

• Parent edges form a tree
  • Need not contain the shortest path tree
    • In a cycle, it might return a longer path tree
  • DFS on a cycle returns a tree because we keep track of visited nodes
    • Never visit a node more than once

DFS Analysis

Like BFS, runtime of DFS is O(V + E) using adjacency list if we visit all nodes and edges. Runtime of DFS with matrix is O(V^2).

Analysis using List

• DFS-visit called only once per node – O(V)
  • After visited, never call it again
• In DFS-visit, each neighbour is enumerated – O(E)
• For connected graph, it'd be O(E)

Analysis using Matrix

• DFS-visit called only once per node – O(V)
  • After visited, never call it again
• In DFS-visit, each neighbour is enumerated – O(V) per node

To build an iterative version of DFS, use a Stack to keep track of where we are at. Iterative BFS is done with a Queue by adding frontiers.

BFS and DFS visit every node and every edge in the graph, not every path.

Directed Graphs (Digraph)

• Should always have directions from one node to another
• DGs can contain cycles as long as they have appropriate directions
• Degree of a node is separated into in-degree and out-degree
  • #incoming and #outgoing edges
• In an adjacency list, edges appear at most twice (also once or none)
• Minimal change in adjacency matrix – just need to be careful where 1 goes
• Topological Ordering
  • Sequential total ordering of all nodes
  • Edges only point forward
• Not all DG has a topological ordering