Graphs

Terminology

• Undirected: $E = V(V - 1) / 2$ - a complete graph, each vertex reachable from all others
• Directed $E = V(V-1)$ - indegree and outdegree concept
• A path is simple if it contains an edge at most once
• Strongly connected digraph - node $u$ may be reachable from $v$ but not necessarily vice versa
• A connected, acyclic undirected graph is called a free tree
  • If we specify a root, it’s a rooted tree
  • Acyclic but not connected is an undirected forest
• Directed, acyclic graphs are called DAGs

Data structures for Undirected Graphs

• Adjacency matrix: $A[u][v] = 1$ if edge(u,v) exists - dense graphs
• Adjacency list: Each edge $(u,v)$ node has a list of the nodes it connects to - sparse graphs

For weighted graphs

• Store weight in matrix cell
• Add field to node object
• Tuples - $(u, v)$ vs the unweighted set notation ${u, v}$

Traversal

Can be multiple trees for BFS or DFS

BFS Shortest Path

• Choose a starting vertex
• Visit in order of increasing distance
• Good for undirected graphs

Pseudocode

Running time

• Time - $\Theta(V+E)$
• Space - $\Theta(V)$

DFS

Same process as BFS but uses a stack

• Go as deep as possible
• Backtrack as little as possible until you can find another path down

Algorithm

• Initially color all the nodes white
• Recursively visit nodes, saving the time (discovery time)

Python

# Using a Python dictionary to act as an adjacency list
graph = {
  '5' : ['3','7'],
  '3' : ['2', '4'],
  '7' : ['8'],
  '2' : [],
  '4' : ['8'],
  '8' : []
}

visited = set() # Set to keep track of visited nodes of graph.

def dfs(visited, graph, node):  #function for dfs
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)

# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, '5')

Types of Edges

• Back edge - the opposite of descendent edge
• Cross edge - Kind of a different path if you think of it like BFS levels
• Tree edge - actual edges, in black

Determining if Cyclic

• Back edges (indicating a cycle)
  • dfs_visit() sees a GRAY vertex
  • If the back edge is a tree edge, then the graph is cyclic. Otherwise, we can color black, and move on
  • Note - if the graph is undirected, it’s not as simple because the gray parent is connected to the current node, but that’s not a cycle

Distinguishing Cross Edges from Descendant Edges

• Use the time counter - if a BLACK finished node was done before a different node, it must be a cross edge

Time Complexity

Same as BFS

• Time - $\Theta(V+E)$
• Space - $\Theta(V)$

Topological Sort

• Given a DAG, we want an ordering where if there is an edge from $u$ to $v$, then $u$ comes before $v$ in the returned list (based on some starting point, multiple valid topo sorts)
• Want to use DFS
  • Use the end time counter, and the topologically sorted vertices are reversed, with the ones most at the end first, and vice versa (note: times may look like start/end) - no importance of start time
  • Ignore descendant and cross edges

Algorithm

• When you set a node BLACK, prepend that node to the topo_list
• time is not necessary for this

Ordering

• You could flip each edge (transpose) and topo sort, which would create a dependency graph

Strongly Connected Components in a Digraph

• From any vertex $u$, I can reach any other vertex - therefore, there must be a directed cycle
• Only a feature of a digraph

Decomposing into SCC Algorithm

1. dfs_sweep(G) to get finish times for $G$
2. Compute $G^T$
3. Call dfs_sweep(G^T) but do it in reversing order from the u.fs from step 1 - this prevents you from crossing SCC boundaries

If you collapse that into a component graph $G^{SCC}$, then you have a DAG and could run Topo Sort

Runs in $\Theta(n)$