# 磨刀不误砍柴工 系列之 四 : Graph

Terminology:

**subgraph**of graph G

A graph H whose vertices and edges are subsets of the vertices and edges of G.**spanning subgraph**of graph G

A subgraph of G that contains all the vertices of the graph G.**connected**graph

For any two vertices, there is a path between them.**froest**

A graph without cycles.**tree**

A connected forest, or a connected graph without cycles.

The definition of a tree is somewhat different from the one given in previous blogs. Previously, trees should be called **rooted trees**;in graph, trees should be called **free trees**.

Let G be an undirected graph with `\( n \)`

vertices and `\( m \)`

edges, then:

- If G is connected, then
`\( m >= n - 1 \)`

- If G is a tree, then
`\( m = n - 1 \)`

- If G is a forest, then
`\( m <= n - 1 \)`

## Data Structures for Graphs

- edge list structure,
`\( O(n + m) \)`

space - adjacency list structure,
`\( O(n + m) \)`

space - adjacency matrix,
`\( O(n^2) \)`

space

To store the vertices, we use a container (eg: list or vector);
To store edges, there is difference between **edge/adjacency list** and **adjacency matrix**. The former 2 structures only store the edges actually present in the graph, while the 3rd structure stores a placeholder for every pair of vertices.

### Edge List

The edge list structure is possibly the simplest, tough not the most efficient, representation of a graph G.

[picture of edge list]

### Adjacency List

The vertex object v holds a reference to a container `\( I(v) \)`

, called the **incidence container**; or if directed dges, container `\( I_{in}(v), I_{out}(v) \)`

;

The edge object for an edge (u,v) holds references to the positions of the edge in the incidence containters `\( I(u) \)`

and `\( I(v) \)`

.

[picture of adjacency list]

### Ajacency Matrix

Represent the graph G with an nxn array, A, such that A[i,j] stores a reference tot he edge (i,j), if such an edge exists. If there is no edge (i,j), then A[i,j] is null.

Historically, the adjacency matric was the first representation used for graphs, defined as a Boolean matrix, as follows:

```
\[A[i,j] = \left\{\begin{matrix}
1 & if (i,j) is an edge \\
0 & otherwise
\end{matrix}\right.\]
```

### DFS & BFS

```
write the pesudo-code
```

## - Pseudo-code for Recurisve Depth-First Search

Back edges connect a vertex `\(v\)`

to a previously visited vertex `\(u\)`

, each back edge implies a cycle in G, consisting of the discovery edges from `\(u\)`

to `\(v\)`

plus the back edge (`\(u,v\)`

)

**Algorithm** DFS(G,`\(v\)`

)

* Input:* A graph G and a vertex

`\(v\)`

of G *A labeling of the edges in the connected component of*

**Output:**`\(v\)`

as discovery edges and back edges **for all**edges

`\(e\)`

in G.incidentEdges(`\(v\)`

) **do**

**if**edge

`\(e\)`

is unexplored **then**

`\( w \leftarrow \)`

G.opposite(`\( v,e \)`

) **if**vertex

`\(w\)`

is unexplored **then**

label

`\(e\)`

as a discovery edge recursively call DFS(G,

`\(w\)`

) **else**</br> label

`\(e\)`

as a back edge## - Pseudo-code for a nonrecursive BFS traversal

BFS proceeds in rounds and subdivides the vertices into **levels**. From those that lead to already visited vertices, called **cross edges**.