On Graphs
Continuing on from our discussion about trees a couple of blog posts ago, we will now discuss their superset, graphs.
Trees are a type of graph, but the converse is not true. Graphs are a collection of nodes with edges connecting some of them. However, for a tree, there will be no cycles amongst these connections.
A cycle in graph theory is when a vertex (node) is reachable from itself through its edges to other nodes.
[8] //A cycle: 8 can reach itself
/ \
/ \
[3]-----[10] //A tree: contains no cycles //A graph
[8] [8] [7]
/ \ | \ |
/ \ | \ |
[3] [10] [3]--[10]--[11]
/ \ \
/ \ \
[1] [6] [14] Graphs can have a number of properties:
- They can be directed or undirected. In a directed graph, think of each edge as having a one-way flow. In a non-directed graph each edge flows both ways.
- If there is a path between every pair of vertices, a graph is considered a connected graph.
- A graph that has no cycles is called an acyclic graph
Representing Graphs
In the context of programming, the two most common ways of representing a graph are the adjacency list and the adjacency matrix.
- In an adjacency list, one has a list containing the nodes of the graph, with each node linking to a list of all its adjacent vertices.
- In an adjacency matrix, a NxN matrix (N is the number of nodes in the graph) is used to represent the graph. Each value stored at matrix[i][j] denotes whether or not an edge exists from node [i] to [j] (i.e. 1 or 0).
Below is an example for representing the following graph:
// Undirected Graph //list //Matrix
[0] [0]->[1]->[2] // [0] [1] [2] [3]
| \ [1]->[0]->[2] // [0] 0 1 1 0
| \ [2]->[1]->[3]->[0] // [1] 1 0 1 0
[1]--[2]--[3] [3]->[2] // [2] 1 1 0 1
// [3] 0 0 1 0