# Notes for Algorithms, Part II: Undirected Graphs

This is a note for 4.1 Undirected Graphs, *Algorithms, Part II*.

## Introduction

### Some graph-processing problems

- Path. Is there a path between $s$ and $t$?
- Shortest path. What is the shortest path between $s$ and $t$?
- Cycle. Is there a cycle in the graph?
- Euler tour. Is there a cycle that uses each edge exactly once?
- Hamilton tour. Is there a cycle that uses each vertex exactly once? (classical NP-complete problem)
- Connectivity. Is there a way to connect all of the vertices?
- MST (Minimal Spanning Tree, 最小生成树). What is the best way to connect all of the vertices?
- Biconnectivity (双连通性). Is there a vertex whose removal disconnects the graph? (DFS)
- Planarity. Can you draw the graph in the plane with no crossing edges? (linear-time DFS-based planarity algorithm discovered by Tarjan in 1970s)
- Graph isomorphism (同构). Do two adjacency lists represent the same graph? (graph isomorphism is longstanding open problem, 长期悬而未决)

## Graph API

$$

\begin{aligned}

\text{public class } &\text{Graph} \\

&\text{Graph(int V)} &\text{create an empty graph with V vertices}\\

&\text{Graph(In in)} &\text{create a graph from input stream}\\

\text{void } &\text{addEdge(int v, int w)} &\text{add an edge v-w}\\

\text{Iterable<Integer> } &\text{adj(int v)} &\text{vertices adjacent to v}\\

\text{int } &\text{V()} &\text{number of vertices}\\

\text{int } &\text{E()} &\text{number of edges}\\

\text{String } &\text{toString()} &\text{string representation}\\

\end{aligned}

$$

### Typical graph-processing code

- compute the degree of $v$

1 | public static in degree(Graph G, int v) { |

- compute maximum degree

1 | public static int maxDegree(Graph G) { |

- compute average degree

1 | public static double averageDegree(Graph G) { |

- compute self-loops

1 | public static int numberOfSelfLoops(Graph G) { |

### Representations

- Set-of-edges graph representation
- Adjacency-matrix graph representation
**Adjacency-list graph representation**

representation | space | add edge | edge between v and w? | iterate over vertices adjacent to v? |
---|---|---|---|---|

list of edges | E | 1 | E | E |

adjacency matrix | V^2 | 1* | 1 | V |

adjacency lists | E+V | 1 | degree(v) | degree(v) |

* disallows parallel edges

#### Adjacency-list graph representation: Java implementation

1 | public class Graph { |

## Depth-first search

**DFS** (to visit a vertex $v$):

- Mark $v$ as visited
- Recursively visit all unmarked vertices $w$ adjacent to $v$

1 | public class DepthFirstPaths { |

DFS marks all vertices connected to $s$ in time proportional to the sum of their degrees.

After DFS, can find vertices connected to $s$ in constant time and can find a pth to $s$ (if one exists) in time proportional to its length.

1 | public boolean hasPathTo(int v) { |

## Breadth-first search

**BFS** (from source vertex $s$):

- Put $s$ onto a FIFO queue, and mark $s$ as visited
- Repeat until the queue is empty:
- remove the least recently added vertex $v$
- add each of $v$'s unvisited neighbors to the queue, and mark them as visited

BFS computes shortest paths from $s$ to all other vertices in a graph in time proportional to $E+V$

1 | public class BreadthFirstPaths { |

## Connected components

$$

\begin{aligned}

\text{public class } &\text{CC}\\

&\text{CC(Graph G)} &\text{find connected components in G} \\

\text{boolean }&\text{connected(int v, int w)} &\text{are v and w connected?} \\

\text{int }&\text{count()} &\text{number of connected components} \\

\text{int }&\text{id(int v)} &\text{component identifier for v} \\

\end{aligned}

$$

**Connected components**:

- Initialize all vertices $v$ as unmarked
- For each unmarked vertex $v$, run DFS to identify all vertices discovered as part of the same component

1 | public class CC { |