## Introduction

### Undirected graphs

Graph. Set of vertices connected pairwise by edges.

### Graph applications ### 图的相关术语

Path. Sequence of vertices connected by edges.
Cycle. Path whose first and last vertices are the same.

Two vertices are connected if there is a path between them. ### 图相关的一些问题

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.

Connectivity. Is there a way to connect all of the vertices?
MST. What is the best way to connect all of the vertices?
Biconnectivity. Is there a vertex whose removal disconnects the graph?

Planarity. Can you draw the graph in the plane with no crossing edges?
Graph isomorphism. Do two adjacency lists represent the same graph?

## graph API  ### Graph API: sample client ### Typical graph-processing code ### Set-of-edges graph representation

Maintain vertex-indexed array of lists. ### Adjacency-list graph representation: Java implementation ## 深度优先搜索

### Design pattern for graph processing

Design pattern. Decouple graph data type from graph processing.

• Create a Graph object.
• Pass the Graph to a graph-processing routine.
• Query the graph-processing routine for information.  ### Depth-first search demo

To visit a vertex v:

• Mark vertex `v` as visited.
• Recursively visit all unmarked vertices adjacent to `v`. Goal. Find all vertices connected to s (and a corresponding path).
Idea. Mimic maze exploration.

Algorithm.

• Use recursion (ball of string).
• Mark each visited vertex (and keep track of edge taken to visit it).
• Return (retrace steps) when no unvisited options.

Data structures.

• `boolean[]` marked to mark visited vertices.
• `int[]` edgeTo to keep tree of paths.
(`edgeTo[w] == v`) means that edge v-w taken to visit w for first time ### Depth-first search properties

Proposition. DFS marks all vertices connected to s in time proportional to the sum of their degrees. Proposition. After DFS, can find vertices connected to s in constant time and can find a path to s (if one exists) in time proportional to its length. ## 广度优先搜索

Repeat until queue is empty:

• Remove vertex v from queue.
• Add to queue all unmarked vertices adjacent to v and mark them. Depth-first search. Put unvisited vertices on a stack.
Breadth-first search. Put unvisited vertices on a queue.

Shortest path. Find path from s to t that uses fewest number of edges.   