# Halo

A magic place for coding

0%

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

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

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

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.

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

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