DinS          Written in 2017/12/8

1. Visually, what is a graph(图)?

See featured image above.

We use graph to represent a large set of data that connect with each other. Compared with other data structures previously introduced, graph is a rather different type. First, it doesn’t have a standard implementation, nor does C++ STL have a container that represents graph. Second, we use operations like access, insert, delete and search to measure the efficiency of data structures, but for graph we don’t use these. Actually we don’t care these in graph.

2. Basic concepts of graph

Graph can be defined as G = (V, E).

V stands for vertex. As the example illustrated above, the featured image, there are 4 vertexes. V = {A, B, C, D}.

E stands for edge. An edge can be understood as a connection between two vertexes. As the example illustrated above, there are 4 edges. E = {AB, AC, BC, BD}.

If two vertexes are connected, i.e. have an edge in between, we say the two vertexes are adjacent. So for the example above, A, B and A, C are adjacent, while A, D are not. Adjacent vertexes are also called neighbors for convenience.

Sometimes we want to measure the number of edges a vertex has. We use the term degree to represent it. The notation is deg(v). For example, deg(A) = 2, deg(B) = 3 and deg(D) = 1.

Depending on the types of edges, graph can be categorized into three groups.

(1)if a graph only has undirected edges, it’s called undirected graph, or undigraph for short. The example above is an undigraph. Undirected edge simply means that AB and BA is the same edge.

(2)if a graph only has directed edges, it’s called directed graph, or digraph for short. Here is an example of digraph.

There’re 5 edges in this digraph. E = {AB, AC, BC, CB, BD}.

Directed edge simply means that you can only go along the arrow.

For digraph, degree are further categorized into out-degree and in-degree. The name is self-explanatory. For example, outdeg(C) = 1 and indeg(C) = 2.

(3)if a graph has both undirected and directed edges, it’s called a mixed graph. Here is an example of mixed graph.

Notice that we can always use a digraph to represent the other two kinds of graph.

We can also add a number to an edge to give the edge some weight. If a graph has weighted edges, it’s called a weighted graph. Here is an example.

The meanings of the number depend on the context.

3. Graph implementation

There are two types of popular implementation for graph.

(1) Adjacency matrix

Though it’s called a matrix, it’s actually a NxN form. To be more specific, it’s vectors inside a vector. We use this form to represent a graph. See the example below.

That’s pretty obvious. We can use G[u][v] to locate the edge from vertex U to vertex V. Since it’s a NxN form, no edges can be left along.

(2) Adjacency list

We can also use lists inside a vector to represent a graph. See this example below.

Each element in the vector is a list. The header is the vertex, and other list nodes are its neighbors.

(3) Comparison and operations

Adjacency matrix and adjacency list have their own advantages and disadvantages.

For adjacency matrix, it’s rather straightforward thus easy to understand. Besides, due to the vector representation, all static operations are O(1). It will take some time if we add or remove vertexes, but this is a rare case for graph. We can just get by. The disadvantage of adjacency matrix is that it wastes a lot of space. In many real-world problems, vertexes are super large, but edges are far less than NxN, say webs on the Internet. In this case we need to turn to adjacency list.

Adjacency list saves space. It’s a huge win over adjacency matrix. Although it may take O(n) to access certain edge, it rarely happens in real-world problem. Your neighbors are few compared with the whole population, right? Overall, adjacency list is a better choice for real-world problem.

4. Graph search

Now that we have a graph, we usually want to see how the graph is made up. That is to say we want to start from certain vertex and travel along the graph to visit each vertex once and only once. This operation is conceptualized as graph search. It serves as a founding algorithm for latter operations.

We know we can have many ways to go along the graph. Depending on the strategy, we have breadth-first search, BFS and depth-first search, DFS.

For BFS, see the second part Graph – Part B.

For DFS, see the third part Graph – Part C.