# 磨刀不误砍柴工 系列之 四 : 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]

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)$$.

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


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
Output: A labeling of the edges in the connected component of $$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.

 Tweet