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:
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.
An edge set simply represents a graph as a collection of all its edges.
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.
The 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 verticies 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
NOTE: This section covers algorithms that will generally not come up in interviews.
