An Introduction to Graphs

Definitions

A graph is defined by its vertices (aka nodes) and edges: G := (V, E). A connected graph is one where there exists a path between any two vertices. Edges can have directions. A graph with directed edges is called a directed graph (or digraph).

A connected graph without cycles is called a tree. Most trees in computer science are rooted trees.

Representations

The adjacency matrix representation of graph G is defined to be a boolean matrix M in which M[i][j] equals 1 if and only if the i-th and j-th vertices are connected by an edge.

For example, the adjacency matrix representation of the following graph

!basic-graph

is [[0,1,1],[1,0,1],[1,1,0]].

The adjancency list representation of graph G describes the neighbors of each vertex.

For example, the adjacency list representation of the following graph

!labeled-graph

is {'a': ['b', 'c'], 'b': ['a', 'c'], 'c': ['a', 'b']}.

Tradeoffs

First off, if a graph is dense, then adjacency matrix and adjacency list have similar performance. When dealing with a sparse graph, however, the two representations have their individual advantages and disadvantages.

If we want to obtain all neighbors of a node, then the adjacency list representation wins. If we want to check two nodes are connected, then the adjacency matrix representation wins.