Introduction
Graphs are mathematical objects that are used in graph theory in order to model the relationships between objects. They are defined by 2 sets:
Vertices – denoted as V. These are the “elements” in our graph.
Edges – denoted as E. Every edge connects between 2 vertices.
For example, the following graph will look like this:
V=\{A,B,C,D,E\}
E=\{A - B, B - C, B - D, C - E, D - E\}
In practice, we can model many real-world problems using graphs and use them to find the solutions.
Key Terms
Path
A path in a graph is a series of edges such that the end vertex of each edge is the start vertex of the next edge. A path can be of any length.
A few examples for paths in the previous example:
- A \rightarrow B \rightarrow C
- A \rightarrow B \rightarrow D
- D \rightarrow E \rightarrow C \rightarrow B
Cycle
A cycle a is a type of a path where the start vertex of the path and the end vertex of the path is the same. Meaning that if we start traveling from a vertex according to a given path, we end up in the same vertex where we started.
Note that we can annotate the same cycle in many ways. In the context of the above image, we could also write it as B-C-A-B or C-A-B-C. These are all ways to mention the same cycle.
Vertex Degree
The degree of a vertex is the number of edges that are connected to a vertex. In the case of directed graphs (explained below) we note the distinction between the:
- In degree – the number of edges coming in
- Out degree – The number of edges going out
Graph Properties
Directionality
Undirected
A graph can be undirected, where every edge is presented by an unordered pair of 2 vertices. The edge connects the vertices and has no directionality.
V=\{A,B,C,D\}
E=\{A - B, A - C, C - B, C - D\}
Directed
A graph can be directed, where every edge is presented by an ordered pair of 2 vertices. The order defines the edge direction.
For example, let’s use our previous example but add directionality to the edges:
V=\{A,B,C,D\}
E=\{A \rightarrow B, B \rightarrow C, C \rightarrow A, C \rightarrow D\}
Cyclic or Acyclic
A graph is considered cyclic if it contains at least one cycle. Meaning you can “travel” from a vertex through edges to different vertices, and end up back at the beginning.
The examples that we showed previously are both considered cyclic, in the directed and undirected version. Because they both contain the cyclic path A \rightarrow B \rightarrow C \rightarrow A.
If for example we flipped the directionality of the edge C \rightarrow A to A \rightarrow C, the graph would no longer be cyclic and is considered acyclic.
V=\{A,B,C,D\}
E=\{A \rightarrow B, A \rightarrow C, B \rightarrow C, C \rightarrow D\}
Connectivity
A graph is considered connected if there exists a path between each pair of nodes. Meaning you are able to “travel” starting from an arbitrary node, to each other node in the graph. We usually say connected when we are talking about edges that have no direction.
In the above example, no matter on which vertex you start, you can “travel” (find a path) to any other vertex.
Connected Components (Undirected case)
In the undirected case, you’ll see the term connected components mentioned. Each connected components is a subgraph (subset of the graphs vertices and edges) such that every vertex in the subgraph can be reached by every vertex in the subgraph by some path.
In the above example we have a graph with 2 connected components. Note that for each connected component we can travel from any vertex to any vertex in the same component, but we cannot reach the vertices in the other component.
Strongly Connected Components (Directed case)
A strongly connected component is very similar to the connected components we saw in the directed case, only this time we are dealing with edges that have directionality. We can break down every directed graph into a set of strongly connected components. Let’s look at an example.
Note that unlike the undirected case, strongly connected components can have edges between them, and this does not “merge” them into one single component. For example, we have a strongly connected component with only one vertex (orange) and it cannot be part of the large yellow one. You can reach all the vertices in the yellow component from the orange one, but you cannot do the opposite.
Also note that if we dropped the directionality of the edges, the entire graph would be one large connected component.
Weighted Edges
The edges can have numeric weights on them. The weights can also be negative. In practice this can be used in many real world problems. We will see practical examples of this in the upcoming posts.
Possible Implementations
There are 2 main ways to implement graphs programmatically. Adjacency Matrices and Adjacency Lists.
Adjacency Matrix
We represent a graph with n vertices using a n \times n matrix.
Directed
The cell in coordinates (i, j) in the matrix will contain a binary 1 or 0, where 1 indicates an edge exists and goes from i \rightarrow j.
Let’s see an example:
Undirected
In the case of edges with no directionality, the matrix will be symmetric.
Can you ask yourself why? In an undirected graph, If we have an edge from i \rightarrow j then we also have an edge from j \rightarrow i
Weighted Edges
In the case of weighted edges, the matrix can have actual values inside the cells instead of containing binary 1s and 0s. Zero means there is no edge between the vertices. (The directionality doesn’t matter. As mentioned, the matrix will just be symmetric if undirected)
Adjacency List
This approach implements the graph as an array where each cell represents a vertex. Each cell contains a linked list of the vertex’s neighbors.
Directed
The linked list in the i^{th} cell of the array will contain the element j if and only if there exist an edge in the graph from i \rightarrow j.
This is best seen using an example:
Undirected
In the undirected case, we will have more elements inside our array’s linked lists. The reason for that is that if an edge exists from i \rightarrow j, the edge from j \rightarrow i to also exists, so we have to track both directions inside our data structure.
Weighted Edges
Just like the previous cases, but here we can keep additional data in every one of the linked list nodes. In this case we keep the vertex that is pointed to, with the weight that is attached to the edge.
Closing words
This article is the first in the series of our graph data structure tutorials. In the upcoming posts we will see the common algorithms that are used, with common use cases in real world problems and interview questions.