## Introduction

A **graph** *G* consists of a set *V*, whose members are called the **vertices** of *G*, together with a set *E* of pairs of distinct vertices from *V*. These paris are called the **edges** of *G*. If *e = (v, w)* is an edge with vertices *v* and *w*, then *v* and *w* are said to **lie on** *e*, and *e* is said to be **incident** with *v* and *w*.

### Two Kinds of Graph

If the pairs are **unordered**, then *G* is called an **undirected graph**;

If the pairs are **ordered**, then *G* is called a **directed graph**, often shortened to **digraph**.

#### Undirected Graph

There are several concepts concerning **undirected graph**:

- Two vertices in an
*undirected graph*are called**adjacent**if there is an edge from one to the other. - A
**path**is a sequence of distinct vertices, each adjacent to the next. - A
**circle**is a path containing at least three vertices such that the last vertex on the path is adjacent to the first one. - A graph is called
**connected**if there is a path from any vertex to any other vertex. - If a graph is disconnected, we shall refer to a
**maximal subset of connected vertices**as a**component**.

And now we can give the definition of a **tree**: **A free tree is defined as a connected undirected graph with no circle.**

#### Direted Graph

We require all edges in a path or a cycle to have the same direction, so that following a path or a circle means always moving in the direction indicated by the arrows.

A directed graph is called **strongly connected** if there is a directed path from any vertex to any other vertex.

If we suppress the direction of the edges and the resulting undirected graph is connected, we call the directed graph **weakly connected**.

### Traversal

#### Depth-First Algorithm(DFS)

**depth-first** traversal is naturally formulated as a recursive algorithm. Its action, when it reaches a vertex *v*, is:

1 | visit(v); |

#### Breadth-First Algorithm(BFS)

We use a **Queue** to implement **breadth-first** traversal. Its action, when it reaches a vertex *v*, is:

1 | q.append(v); |

### Implementation

There are several ways to represent a graph: **Set**, **Adjacency Table**, **Adjacency List**. Here I’d like to use an **adjacency list** with mixed list.

1 | typedef int Vertex; |

**neighbors** are an array of *LinkedList*. Each index of **neighbors** represents a vertex, and each *LinkedList* store the vertices which are adjacent to the present vertex.

#### insert(**const** Vertex &start, **const** Vertex &end)

*precondition*: None.*postcondition*: If *start* and *end* are both valid, *end* will be added to the list of *start*.

1 | template <int max_size> |

#### depth_first(void (*visit)(Vertex &x))

*precondition*: None.*postcondition*: The function *visit has been performed at each vertex of the *Digraph* in depth-first order.

1 | template <int max_size> |

#### traverse(Vertex &v, bool visited[], void (*visit)(Vertex &))

*precondition*: *v* is a vertex of the *Digraph**postcondition*: The depth-first traversal, using function *visit has been completed for *v* and for all vertices that can be reached from *v*.

1 | template <int max_size> |

#### breadth_first(void (*visit)(Vertex &x))

*precondition*: None.*postcondition*: The function *visit has been performed at each vertex of the *Digraph* in breadth_first order.

1 | template <int max_size> |

In this post I only give a brief introduction about **graph**. However, **graph** can be used to deal with many problems such as the **shortest path problem**. Thank you so much!