Graphs are one of the most prevalent data structures in computer science. It's a powerful data structure that's utilized to represent relationships between different types of data. In a graph, each data point is stored as a node and each relationship between those data points is represented by an edge. For example, a social network is considered a graph in which each person is considered a node and a friendship between two people is considered an edge.
Graphs are best utilized for problems in which there are binary relationships between objects. Once a problem can be represented as a graph, the problem can generally be solved based off of one of the key graph algorithms. For interviews, it is vital to know how to implement a graph, basic graph traversals (BFS, DFS) and how to sort topologically the graph.
Graphs consist of a set of..
A directed graph is a graph that in which all edges are associated with a direction. An example of a directed edge would be a one way street.
An undirected graph is a graph in which all edges do not have a direction. An example of this would be a friendship!
Before going over the what cyclic and acyclic graphs are, there are two key terms to cover: path and cycle. A path is a sequence of vertices connected by edges and a cycle a path whose first and last vertices are the same.
A cyclic graph means that there contains a least one cycle within the graph.
An acyclic graph has no cycles within it.
A commonly used phrase when referring to graphs is a directed acylic graph (DAG), which is a directed graph in which there are no cycles. In a DAG, these two terms are commonly used to denote nodes with special properties:
In this section we discuss two potential ways graphs are represented in text. For both representations we will use the following graph example.
The graph above have the following qualities:
Adjacency list is the most common way to represent graphs. With this approach of representing a graph, each node stores a list of its adjacent vertices. For undirected graphs, each edge from u to v would be stored twice: once in u's list of neighbors and once in v's list of neighbors.
Adjacency list:
graph = {
'A': ['B', 'C']
'B': ['C', 'E']
'C': ['D']
'D': ['E']
}An edge set simply represents a graph as a collection of all its edges.
Edge List:
graph = [
('A', 'B'),
('B', 'C'),
('B', 'E'),
('C', 'D'),
('D', 'E')
]An adjacency matrix represents a graph with n nodes as a n by n boolean matrix, in which matrix[u][v] is set to true if an edge exists from node u to node v.
In this example, we assign each node an index. We will assign the following indices:
| 0 (A) | 1 (B) | 2 (C) | 3 (D) | 4 (D) | |
|---|---|---|---|---|---|
| 0 (A) | 0 | 1 | 1 | 0 | 0 |
| 1 (B) | 0 | 0 | 1 | 0 | 1 |
| 2 (C) | 0 | 0 | 0 | 1 | 0 |
| 3 (D) | 0 | 0 | 0 | 0 | 1 |
| 4 (E) | 0 | 0 | 0 | 0 | 0 |
Adjacency Matrix
graph = [
[0, 1, 1, 0, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 0, 0]
]This representation of a graph is efficient for checking if an edge exists between a pair of vertices. However, it may be less efficient for search algorithms because it requires iterating through all the nodes in the graph to identify a node's neighbors.
Below is a chart of the most common graph operations and their runtimes for each of the graph representations. In the chart below, V represents the number of vertices in the graph and E represents the number of edges in the graph.
| Representation | Getting all adjacent edges for a vertex | Traversing entire graph | hasEdge(u, v) | Space |
|---|---|---|---|---|
| Adjacency matrix | O(V) | O(V2) | O(1) | O(V2) |
| Edge Set | O(E) | O(E) | O(E) | O(E) |
| Adjacency List | O(1) | O(V + E) | O(max number of edges a vertex has) | O(E + V) |
Credit: UC Berkeley data structures course
What are some common questions we should ask our interviewer?
Are there any special techniques that we can use to help make this easier?
In the Matching step of UMPIRE, you want to think about common patterns and tricks that could apply to this problem.
O(V+E) traversal time and space) vs. adjacency matrix (O(V²) time and space). If the graph is dense, the matrix is fine. Graphs are usually large and sparse so we opt for the adjacency list.Tips:
| Average Case | Worst Case | |
|---|---|---|
| Dijkstra's Algorithm | O(E log V) |
O(V^2) |
| Prim's Algorithm | O(E log V) |
O(V^2) |
| Topological Sort | O(V + E) |
O(V + E) |
| Bellman-Ford Algorithm | O(V + E) |
O(V + E) |
| Floyd-Warshall Algorithm | O(V^3) |
O(V^3) |
