Depth-First Search and Breadth-First Search
Preface
Welcome to the final article in our series on data structures for iOS developers! Over the years, we've covered the fundamental data structures that help you solve programming and data processing problems efficiently. Today, we'll wrap up the series with a look at graphs and the breadth-first search (BFS) and depth-first search (DFS) methods. These algorithms are an important part of many applications, from finding the shortest path to analyzing graph connectivity and more.
In this series we have already studied:
Big O notation: A formal way to evaluate the complexity of algorithms, which helps us understand how well they work as the amount of data increases. Read more here and here.
Arrays: Basic structures for storing sequential data, their advantages and disadvantages. Read more here.
Linked lists: Flexible data structures that allow efficient memory management and resizing on the fly. Details and usage examples can be found here.
Stacks and Queues: Basic data structures for managing the order of operations and processing data in the order in which they arrive or in priority. Learn more here.
Hash tables: An efficient way to store and quickly access data using hash functions. The article is available at the link.
Trees and binary search trees: Fundamental data structures for organizing and searching information. Learn more here.
Sorting algorithms: Key data sorting techniques, including bubble sort, merge sort, quicksort, and more. Learn more about sorting approaches here.
Fibonacci series and memoization: Applying dynamic programming and optimizing computations when working with recursive problems such as calculating Fibonacci numbers. Read here.
These materials provide a solid foundation for understanding and applying data structures to real-world problems. Today's article is the logical conclusion of the series, in which we will delve into the application of graphs to solving various problems using search algorithms.
Subscribe to my Telegram channel!
If you liked this series of articles and want to receive even more useful content on algorithms and data structures, as well as participate in discussions and receive exclusive materials, I invite you to join my Telegram channel! Subscribe by link and stay up to date with all the news and updates.
What are graphs?
A graph is a mathematical structure consisting of a set of vertices (or nodes) and a set of edges (or faces) that connect pairs of vertices. Graphs are used to model relationships and connections between objects. A graph can be directed or undirected.
If you have read the previous articles, you have already seen a graph, and this graph is called a binary tree. But what are its limitations? First, each parent can only have two children. Second, the graph always has a top-down direction. In other words, the edges or links always go from parent to child.
The graphs we'll look at won't be limited by the number of vertices or edges. Our vertices and edges can go anywhere. You can take any data structure and represent nodes as vertices and links as edges.
When we talk about edges, there are two types. The type we saw in a binary tree is a directed edge, which goes in one direction from one node to another. But here, with regular graphs, we are not limited to that. These edges can be bidirectional, meaning they can go in both directions. Also, our nodes can connect to any other node we want. We are not limited to going only from parent to child.
When we dig deeper into graphs, we see that these edges can also have weights. A weight in a graph represents the relative cost of moving along an edge from one node to another. For example, if we want to find the cheapest flight from Moscow to Sydney, or the shortest distance, we can build a graph with edges and figure out which path is the shortest.
In a nutshell, a graph is simply a series of nodes and edges that represent some problem or area that we typically want to explore or traverse. Before we start building graphs, it helps if we have some basic data structures that we can use to represent the data.
First, we'll look at three different ways to represent graphs as data. Then we'll look at two of the most common ways to use these data structures to search graphs.
How do graphs work?
When it comes to modeling graph data structures, our goal is to represent each of these nodes and edges as a simple basic data structure. And three very common graph data structures are edge lists, adjacency matrices, and adjacency lists.
Let's start with an edge list. In an edge list, we simply take each edge in the graph, say from zero to one, and represent it as two elements in an array: zero and one. That's the whole point of a list. The beauty of a list is its simplicity. There's nothing complicated about representing it. The only downside is that if we want to find a specific edge in a list, it's a linear search and we have to search the entire list, in other words, O(n).
On the other hand, the adjacency matrix has a very fast lookup time. Here, we take each edge in the graph and represent it as a one in a two-dimensional matrix. For example, if an edge goes from zero to one, zero will be our element i, and one will be our element j. We will find that place in the matrix and put a one there. Same for an edge from one to two: we will find a place in the matrix and insert a one at positions one, two to represent that edge. The advantage of the adjacency matrix is that it provides fast O(1) lookup. The only disadvantage is that it is not the most efficient in terms of memory usage. If we have few edges, the matrix will have a lot of zeros, which will waste memory.
But there is a data structure that combines the simplicity of an edge list with the speed of an adjacency matrix: an adjacency list. In this structure, we take each vertex and simply store each of its neighbors as a list in an array. For example, vertex 0 has two neighbors: vertices 1 and 4. We simply store 1 and 4 in an array, and these will be the neighbors of vertex 0. Likewise for vertex 1, which has a neighbor 2. Vertex 2 has no neighbors. Vertex 3 has two neighbors: 1 and 2, and vertex 4 has three neighbors. Storing an array of arrays, or linked lists of these elements, allows us to quickly build a collection of neighbors for each vertex and then quickly find them.
If you make all the edges in a graph undirected, then in the case of a list of edges, this simply means that for each existing edge, the inverse is added. For example, if there was an edge from one vertex to another, then the inverse edge is added. Thus, the number of edges doubles, and each edge becomes two-sided.
For an adjacency matrix, this results in the matrix being symmetric. That is, the values in the matrix on either side of the main diagonal will be the same, which is a good visual way to check if the matrix is correct for an undirected graph.
As for the adjacency list, neighbors in both directions are added for each node. As a result, each node gets additional connections to other nodes, which reflect the bidirectional edges.
Now that we have the basic data structures for graphs, we can move on to practice. We will look at the breadth-first search algorithm, the main tool for working with graphs.
Breadth-first search
In breadth-first search, we start at the central node and expand our search outward. We look at the nodes that are closest to us, traverse them all, and then move to the next level of the graph. Think of it as nearest neighbor search. This method is used to find friends in social graphs, generate song recommendations on Spotify, and identify low-latency players in online games to distribute the load more evenly.
Depth-first search, on the other hand, starts at a node and goes inward, ignoring all but one other node, and continues until it has gone around all the nodes or encountered no more edges to expand. This algorithm is useful for finding a path through a maze or solving problems with unique solutions, such as finding a path through a maze, and for detecting cycles in a graph.
Breadth-first search is mostly about bookkeeping. We keep track of which nodes we've visited as we traverse the graph. To stay on the top level and visit immediate neighbors instead of going deeper, we use a queue. Queues operate on a FIFO (first in, first out) principle. The queue is the core of the breadth-first search algorithm: we add the nodes we want to visit to one end of the queue and pop them in the order they arrive from the other end. This is how we maintain breadth-first search. Let's see what this looks like in code.
import Foundation
// Очередь для поиска в ширину
struct Queue<T> {
private var array: [T]
init() {
array = []
}
var isEmpty: Bool {
return array.isEmpty
}
var count: Int {
return array.count
}
mutating func add(_ element: T) {
array.append(element)
}
mutating func remove() -> T? {
if isEmpty {
return nil
} else {
return array.removeFirst()
}
}
func peek() -> T? {
return array.first
}
}
// Стек для поиска в глубину
struct Stack<T> {
fileprivate var array = [T]()
var isEmpty: Bool {
return array.isEmpty
}
var count: Int {
return array.count
}
mutating func push(_ element: T) {
array.append(element)
}
mutating func pop() -> T? {
return array.popLast()
}
var top: T? {
return array.last
}
}
class Graph {
var V = 0 // количество вершин
var adj = [[Int]]() // список смежности
init(_ V: Int) {
self.V = V
for _ in 0..<V {
adj.append([Int]()) // создать пустой массив списков смежности
}
}
func addEdge(v: Int, w: Int) {
adj[v].append(w)
}
// Обход в ширину (BFS) от заданной начальной вершины s
func BFS(s: Int) -> [Int] {
var result = [Int]()
// Отметить все вершины как не посещенные
var visited = adj.map { _ in false }
// Создать очередь для обхода в ширину (BFS Queue)
var queue = Queue<Int>()
// Отметить первую вершину как посещенную и добавить в очередь
visited[s] = true
print("Starting at \(s)")
queue.add(s)
result.append(s)
while queue.count > 0 {
let current = queue.remove()!
print("De-queueing \(current)")
// Получить все смежные вершины текущей вершины
// Если смежная вершина еще не посещена,
// отметить её как посещенную и добавить в очередь
for n in adj[current] {
if visited[n] == false {
visited[n] = true
print("Queuing \(n)")
queue.add(n)
result.append(n)
}
}
}
return result
}
// Обход в глубину (DFS) от заданной начальной вершины s
func DFS(s: Int) -> [Int] {
var result = [Int]()
// Отметить все вершины как не посещенные
var visited = adj.map { _ in false }
// Создать стек для обхода в глубину (DFS Stack)
var stack = Stack<Int>()
// Отметить первую вершину как посещенную и добавить в стек
// print("Начало с вершины \(s)")
visited[s] = true
stack.push(s)
while stack.count > 0 {
let current = stack.pop()!
// print("Извлечение из стека \(current)")
result.append(current)
// Перебрать всех соседей, добавляя их в стек и извлекая по мере углубления
for n in adj[current] {
for n in adj[current] {
if visited[n] == false {
visited[n] = true
// print("Добавление в стек - \(n)")
stack.push(n)
}
}
}
return result
}
}
// Нужно создать столько вершин, сколько есть рёбер
let g = Graph(8)
g.addEdge(v: 0, w: 1)
g.addEdge(v: 1, w: 4)
g.addEdge(v: 4, w: 6)
g.addEdge(v: 6, w: 0)
g.addEdge(v: 1, w: 5)
g.addEdge(v: 5, w: 3)
g.addEdge(v: 3, w: 0)
g.addEdge(v: 5, w: 2)
g.addEdge(v: 2, w: 7)
//g.BFS(s: 0)
print(g.DFS(s: 0))
Code Analysis
The first thing we'll do is create a graph. We'll specify how many nodes or vertices we have in the graph. In our case, that number will be eight, the same graph we used before, from 0 to 7. And to set this up, we need to define all the edges in our graph.
Now this is an undirected graph, which means we have edges going from zero to one, but we also have edges going back from one to zero. Since all the edges in our graph are undirected, we add them all here in both directions (add edge).
When we're ready to search, we simply call the breadth-first search function, starting at node 0. And if we run it, we get the same result we saw earlier: starting at node 0, going breadth-first to node 7.
In our graph, we set up the data like this: we have a variable V that keeps track of the number of vertices, and we have an array of arrays of integers. This is what will store all of our neighbors. This is our adjacency list, as we saw earlier. It will keep track of all of the neighbors of each node, storing them as an array of arrays of integers.
When we create a graph, we simply know how many vertices we have. Then we create our adjacency list, and we're ready to go. For any vertex V that's connected to another W, we simply find the array and add that other vertex as a neighbor.
When it comes to traversal, we start by marking all visited nodes as false, meaning we haven't visited any nodes yet. We then create our queue to keep track of where we've been. We take the first node passed to the breadth-first search function. We mark it as visited, print it to show we've been there, and add it to the queue. In our case, that would be node 0.
While we have something in the queue, we pop the next node off the queue, thereby removing it from the queue. Then we visit all of its neighbors. We go to the array of arrays, our adjacency list, get an iterator, and simply walk through each one. If we haven't visited it yet, we mark it as visited and add it to the queue. We do this for all of the neighbors, and we continue until we've visited all of the nodes in the graph.
So, that's how breadth-first search works in a nutshell. An elegant little algorithm, absolutely beautiful. Now you have an example to work with and play with yourself.
Depth First Search
Depth-first search works very similarly to breadth-first search. Here we have the same graph that we used in breadth-first search, but notice that now we have a stack instead of a queue. Remember that the stack uses the LIFO principle – the last value in, first out. This allows us to go deep instead of wide. This is the difference between depth-first and breadth-first search.
Now let's see what this looks like in code.
Code Analysis
The code for depth-first search is almost the same as breadth-first search. The only difference here is that instead of a queue, we use a stack. And instead of adding to and popping from the queue, we add and pop elements from the stack. Other than that, it's the same algorithm.
We have the same test with the same graph. If we run it and look, we see that instead of going breadth-first, we go depth-first. So, like in our example, the first path we go is from 0 to 3, then to 5, then to 2, and then to 7. Then we go back and take the rest of the path: 6, 4, and 1.
Now let's walk through this algorithm and see how it works in detail. I've added some output statements so that when you run the test, like in breadth-first search, you can see where the various elements are being added and extracted.
We start with node 0. We go there, visit it, add it to the stack, and mark it as visited. Now we're ready to move on. We pop node 0 off the stack. The first thing we do is look at its neighbors: we have nodes 1, 6, and 3. We add them to the stack in random order, so since 3 was the last element added, we pop it first and look at its neighbors. We have node 5, so we mark it as visited, add it to the stack, and continue to node 5.
When we reach node 5, we look around and see that all nodes have been visited except node 2. So we add node 2 to the stack and continue to it. We pop node 2, look at its neighbors, and see that node 7 is the only unvisited node. We mark it as visited, add it to the stack, and at this point the path ends.
Notice the path we took: from 0 to 3 to 5 to 2 to 7. This is a depth-first search. Instead of staying at the top and visiting nodes 1, 6, and 3 from node 0, we picked node 3 and went as far down that path as we could until we reached node 7.
Once this path is exhausted, we come back and see that the next item on our stack is node 6. Now we take another path, pop node 6, go to it, look around, and see that we have an unvisited node 4. We mark it as visited, add it to the stack, and continue to node 4. When we reach node 4, we see that we have no more unvisited nodes. We have already marked node 1 as visited. Now we pop node 4, then node 1, and that's it. We just took a different route for the last leg of the path, going from node 0 to node 6, then to node 4, and finally to node 1.
Conclusion
One of the most common interview questions when it comes to graphs is which algorithm is better: breadth-first search or depth-first search? And to help you answer this question, it’s helpful to have a few key examples of each in mind so you can explain that the answer to this question depends on context.
For example, you can say that breadth-first search is best for finding things that are at the top levels of a graph. When we use breadth-first search, we are looking for immediate neighbors, things that are nearby. This includes things like social networks like Facebook and LinkedIn where you want to find new friends, computer games, and anything where you think the solution to the problem you are looking for in a graph is near or at the top of the graph structure. In those cases, you would use breadth-first search.
Depth-first search, on the other hand, is better at finding things that are far away. When you think of depth-first search, you think of there being a single solution or something far away that can only be found efficiently by going deep. A classic example of this is artificial intelligence in chess. To determine the best way to win chess, you gradually need to look at your opponent's moves, extrapolate to the end of the game to see if there is a solution, and then work backwards to choose the next move. With breadth-first search, you go wide and use a queue, while with depth-first search, you go deep and use a stack. Now you should be able to explain the difference between breadth-first search and depth-first search, and when asked which one is better, you should be able to say that it depends on the problem, and then give specific examples.
