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