An effective programmer needs a solid understanding of data structures and algorithms. Technical interviews will often test your problem-solving and critical thinking skills.
Graphs are one of the many important data structures in programming. In most cases, understanding graphs and solving graph-based problems does not come easy.
What is a graph, and what do you need to know about it?
What Is a Graph?
A graph is a non-linear data structure that has nodes (or vertices) with edges that connect them. All trees are subtypes of graphs, but not all graphs are trees, and the graph is the data structure from which trees originated.
Although you can build data structures in JavaScript and other languages, you can implement a graph in various ways. The most popular approaches are edge lists, adjacency lists, and adjacency matrices.
The Khan Academy guide to representing graphs is a great resource for learning about how to represent a graph.
There are many different types of graphs. One common distinction is between directed and undirected graphs; these come up a lot in coding challenges and real-life uses.
Types of Graphs
-
Directed graph: A graph in which all edges have a direction, also referred to as digraph.
-
Undirected graph: An undirected graph is also known as a two-way graph. In undirected graphs, the direction of edges doesn't matter, and traversal can go in any direction.
-
Weighted graph: A weighted graph is a graph whose nodes and edges have an associated value. In most cases, this value represents the cost of exploring that node or edge.
-
Finite graph: A graph that has a finite number of nodes and edges.
-
Infinite graph: A graph that has an infinite amount of nodes and edges.
-
Trivial graph: A graph that has just one node and no edge.
-
Simple graph: When only one edge connects each pair of the nodes of a graph, it is called a simple graph.
-
Null graph: A null graph is a graph that has no edges connecting its nodes.
-
Multigraph: In a multigraph, at least a pair of nodes have more than one edge connecting them. In multigraphs, there are no self-loops.
-
Complete graph: A complete graph is a graph in which every node connects to every other node in the graph. It is also known as a full graph.
-
Pseudo graph: A graph that has a self-loop aside from other graph edges is called a pseudo graph.
-
Regular graph: A regular graph is a graph where all nodes have equal degrees; i.e every node has the same number of neighbors.
-
Connected graph: A connected graph is simply any graph in which any two nodes connect; i.e a graph with at least one path between every two nodes of the graph.
-
Disconnected graph: A disconnected graph is the direct opposite of a connected graph. In a disconnected graph, there are no edges linking the graph’s nodes, such as in a null graph.
-
Cyclic graph: A cyclic graph is a graph containing at least one graph cycle (a path that ends where it started).
-
Acyclic graph: An acyclic graph is a graph with no cycles at all. It can either be directed or undirected.
-
Subgraph: A subgraph is a derived graph. It is a graph formed out of nodes and edges that are subsets of another graph.
A loop in a graph is an edge that starts from a node and ends at the same node. Therefore, a self-loop is a loop over only one graph node, as seen in a pseudo graph.
Graph Traversal Algorithms
Being a type of non-linear data structure, traversing a graph is quite tricky. Traversing a graph means going through and exploring each node given there is a valid path through the edges. Graph traversal algorithms are mainly of two types.
- Breadth-First Search (BFS): Breadth-first search is a graph traversal algorithm that visits a graph node and explores its neighbors before going on to any of its child nodes. Although you can start traversing a graph from any selected node, the root node is usually the preferred starting point.
- Depth-First Search (DFS): This is the second major graph traversal algorithm. It visits a graph node and explores its child nodes or branches before proceeding to the next node—that is, going deep first before going wide.
Breadth-first search is the recommended algorithm to find paths between two nodes as quickly as possible, especially the shortest path.
Depth-first search is mostly recommended when you want to visit every node in the graph. Both traversal algorithms work fine in any case, but one might be simpler and more optimized than the other in selected scenarios.
A simple illustration can help understand both algorithms better. Think of the states of a country as a graph and try to check if two states, X and Y, are connected. A depth-first search might go on a path almost around the country without realizing early enough that Y is just 2 states away from X.
The advantage of a breadth-first search is that it maintains closeness to the current node as much as possible before going to the next one. It will find the connection between X and Y in a short time without having to explore the whole country.
Another major difference between these two algorithms is in the way they are implemented in code. Breadth-first search is an iterative algorithm and makes use of a queue, while a depth-first search is usually implemented as a recursive algorithm that leverages the stack.
Below is some pseudocode demonstrating the implementation of both algorithms.
Breadth-First Search
bfs(Graph G, GraphNode root) {
let q be new Queue
// mark root as visited
root.visited = true
// add root to the queue
q.enqueue(root)
while (q is not empty) {
let current be q.dequeue() // remove front element in the queue
for(neighbors n of current in G) {
if (n is not yet visited) {
// add to the queue - so you can explore its neighbors too
q.enqueue(n)
n.visited = true
}
}
}
}
Depth-First Search
dfs(Graph G, GraphNode root) {
// base case
if (root is null) return
// mark root as visited
root.visited = true
for (neighbors n of root in G)
if (n is not yet visited)
dfs(G, n) // recursive call
}
A few other graph-traversal algorithms derive from breadth-first and depth-first searches. The most popular ones are:
- Bidirectional search: This algorithm is an optimized way of finding the shortest path between two nodes. It uses two breadth-first searches that collide if there is a path.
- Topological sort: This is used in directed graphs to sort the nodes in the desired order. You cannot apply a topological sort to undirected graphs or graphs with cycles.
- Dijkstra’s algorithm: This is also a type of BFS. It is also used to find the shortest path between two nodes in a weighted directed graph, which may have cycles or not.
Common Interview Questions Based on Graphs
Graphs are among the important data structures every programmer should know. Questions often come up on this topic in technical interviews, and you may encounter some classic problems related to the topic. These include things like the "town judge", "number of islands", and "traveling salesman" problems.
These are just a few of the many popular graph-based interview problems. You can try them out on LeetCode, HackerRank, or GeeksforGeeks.
Understanding Graph Data Structures and Algorithms
Graphs aren’t just useful for technical interviews. They have real-world use cases as well, such as in networking, maps, and airline systems for finding routes. They are also used in the underlying logic of computer systems.
Graphs are excellent for organizing data and for helping us visualize complex problems. Graphs should only be used when absolutely necessary, though, to prevent space complexity or memory issues.