## 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`

.

### Depth-first search

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.

## 广度优先搜索

### Breadth-first search demo

Repeat until queue is empty:

- Remove vertex
**v**from queue. - Add to queue all unmarked vertices adjacent to
**v**and mark them.

### Breadth-first search

**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.

### Breadth-first search properties

Proposition. BFS computes shortest paths (fewest number of edges) from **s** to all other vertices in a graph in time proportional to **E + V**.