Chapter 20: Elementary Graph Algorithms: BFS, DFS, and Topological Sort

Welcome to Last Minute Lecture.

This free chapter overview is designed to help students review and understand key concepts.

These summaries supplement not replaced the original textbook and may not be redistributed or resold.

For complete coverage, always consult the official text.

Welcome back to the Deep Dive.

You know, it's amazing how much of our world runs on connections.

I mean, think about it, social media, the internet, even the way cities are laid out.

It's all networks, right?

And at the heart of how computers make sense of these networks, well, there are these elegant things called graph algorithms.

And that's our deep dive today.

We're going to break down how computers actually represent and explore these complex webs of relationships.

So let's get right to it.

If we're talking about teaching a computer about these networks,

where do we even begin?

How do we represent the connections?

Well, imagine you're trying to describe, let's say, a group of friends and who knows whom.

One way to do that is to just list out each person and then write down all their friends' names next to them.

Like a contact list.

Yeah, exactly.

And that's essentially the idea behind what we call an adjacency list in computer science.

Each person is like a point in the network, a vertex, and their friends are the neighbors they're connected to by edges, those lines representing the friendships.

Okay, so each person gets their own list of connections.

Makes sense.

But what if the connections aren't always two -way?

Like on social media, if I follow someone, they don't necessarily follow me back.

Right, and that's where directed graphs come in.

See, in an adjacency list for a directed graph, if there's an edge going from, say, vertex U to vertex V, then V will be on U's list.

But U would only be on V's list if the connection goes both ways.

Kind of like one -way streets versus two -way streets on a map, right?

Ah, so it captures that one -way dynamic.

So for networks where there aren't a ton of connections per person, this adjacency list seems pretty efficient.

But how efficient are we talking, like, memory -wise?

For these sparse graphs, as we call them, where the number of connections or edges, we use E to represent that, is much smaller than the number of possible connections, well, adjacency lists really shine.

They only need space that grows proportionally to the number of individuals, the vertices, which we represent with V plus the number of edges, E.

So it's written as big theta of V plus E.

It's basically saying the memory needed scales linearly with the number of people and connections, which is pretty darn good.

Okay, so it's all about keeping things lean when the network isn't super dense.

But what if we needed to actually find all the connections in the network using this list?

How long would that take?

To find all those connections or edges, you'd have to go through each person, each vertex, and their list of friends, right?

So that takes time proportional to V plus E again, because we have to look at everyone and then their connections on average.

Okay, now let's add another layer of complexity.

What if these connections have some kind of value attached, a weight?

Like, imagine a delivery network where the roads between locations have different travel times.

That's where weighted graphs come in.

So with our handy adjacency list, when we store that a neighbor V is connected to U, we also store the weight of that connection.

Let's call it W of UV.

Basically, each entry in the list now becomes a pair, the neighbor, and the cost or weight of reaching them.

So it's not just who you're connected to, but how you're connected, the strength or cost of that connection.

All right, so that's adjacency list, like a personalized contact book for networks.

What's the other big way computers wrap their heads around these graphs?

That would be the adjacency matrix.

Picture a giant grid where both the rows and the columns represent all the individuals in our network.

Okay, I'm picturing it like a spreadsheet almost.

Exactly.

So if we have, say, V individuals, then we make a V by V grid and we can call it A.

Now, if there's a connection from person I to person J, the cell in the i -th row and j -th column, we write that as A sub ij, that cell gets a one.

If they're not directly connected, it gets a zero.

Ah, so it's like a quick reference chart for connections.

How does this matrix deal with those one -way connections we talked about?

For a directed network, if A sub ij is one, it just means there's a connection from i to j.

But A sub j, I might be zero if there's no connection back.

But for an undirected network, like our mutual friendships example, if i and j are connected, both A sub ij and A sub j, i will be one.

So the matrix becomes symmetrical.

It looks the same if you flip it along its diagonal.

Okay, so it mirrors that two -way relationship.

Yeah.

What about space though?

This grid seems like it could get pretty massive for large networks.

You're right, that's the trade -off.

An adjacency matrix always needs space proportional to V squared, regardless of how many connections there actually are.

That's because it has to account for every possible pair, even if they're not connected.

So while adjacency lists are great for sparse networks, matrices can become memory hogs when you're dealing with a lot of individuals and relatively few connections.

So you trade off memory efficiency for quick access to relationship information.

But how long does it take to actually find all the connections using this grid?

Well, worst case scenario, you might have to check every single cell in that V by V matrix, right?

So that would take time proportional to V squared.

So there are definitely situations where a matrix makes more sense, right?

Like if you need to check for connections super quickly.

Exactly.

The beauty of a matrix is that checking if U and V are connected is lightning fast.

You just look up the cell A sub UV and boom, you know, that's what we call constant time, O of one.

And if the network is unweighted, you're just storing a zero or a one in each cell, a single bit of information, which can be pretty compact, especially at the low level.

Okay.

So each method has its strengths, depending on what you're trying to do.

Now, what happens when we need to store more than just whether two individuals are connected?

Well, in a lot of algorithms, we need to track extra information about the individuals or the connections themselves.

Things like how far someone is from a starting point or whether we've already visited them in our exploration.

Like making notes on our network map as we go along.

Yeah.

So we use notations like V dot ED to represent some data D attached to individual V or UV dot F for data F about the connection between U and V.

And in practice, this could be extra lists or tables alongside our main representation or even properties attached to the individuals and connections in a computer program.

Got it.

So we've laid the groundwork.

We know how to represent these networks.

Now, how do we actually start exploring them?

Let's dive into the search algorithms you mentioned, starting with breadth first search or BFS.

BFS is like that classic systematic exploration, kind of like ripples spreading out from a point.

The idea is you start at a source and explore everything one step away, then two steps away and so on.

It's guaranteed that the first time you reach a node, you found the shortest path to get there, at least in terms of the number of connections.

So it's like mapping out the network in layers like an onion.

How does it keep track of all that?

BFS uses a queue, which is like a line where the first one in is the first one out, FIFO, they call it.

And it uses those colors we talked about.

White means undiscovered, gray means discovered, but not fully explored.

And black means we've looked at all its neighbors.

Okay, paint me a picture.

How does this BFS actually play out step by step?

All right.

First, everyone starts white at infinity distance, except our starting point S, which is at distance zero, because, well, we're already there.

We also track who led us to each individual using predecessors, initially set to nothing.

Then we enqueue our starting point S and color it gray.

So S is our first gray node ready to be explored.

Exactly.

Now, as long as our queue isn't empty, we dequeue a gray vertex, call it U.

For each of its neighbors, V, if V is still white, meaning undiscovered, we color it gray, set its distance to be U's distance plus one, mark U as its predecessor, and then enqueue V.

So we're systematically marking how far each individual is from our starting point and who led us to them.

Precisely.

And once we've looked at all of U's neighbors, we color U black, signifying it's fully explored.

This process repeats until the queue's empty.

And all those black nodes form our explored territory.

How efficient is this whole process?

With adjacency lists, BFS runs in time proportional to V plus E, just like finding all edges.

Setting things up takes time proportional to V, the number of individuals.

Queue operations adding and removing individuals also take time proportional to V overall.

And exploring connections takes time proportional to E, the total number of connections, so it all adds up to O of V plus E.

So again, pretty efficient for most networks.

You mentioned BFS finds shortest paths.

How does that work exactly?

The distance we calculate during BFS that V dot D is actually the shortest path distance.

We explore an increasing order of distance from the source.

So the first time we reach an individual, it's got to be the shortest route in terms of number of connections.

Ah, because we're expanding outward layer by layer.

And you also mentioned something about a breadth -first tree.

What's that all about?

The breadth -first tree, we call it G sub pi.

It's formed by those predecessor relationships.

Basically, you start with S.

And for every other individual with a predecessor, you draw a connection back to that predecessor.

This tree shows you a unique shortest path back to the starting point from any reachable individual.

So it's a visual representation of those shortest paths.

OK, BFS is all about breadth, that systematic layered exploration.

Now let's

DFS.

Sounds like it takes a deeper approach.

You got it.

Instead of layers, DFS is all about going as deep as possible along each path before backtracking.

Think of it like exploring a maze.

You pick a direction and just keep going until you hit a dead end.

Then you go back to last fork and try a different path.

And if there are still unexplored areas after checking all paths from the starting point, well, we just pick a new starting point and do it again, creating a depth first forest, a collection of these exploration trees.

So DFS is more about delving into every cranny.

Does it also use those colors to track progress?

Absolutely.

We've still got white for undiscovered, gray for being explored, and black for fully explored.

But DFS adds another tool to its toolkit, timestamps.

We record a discovery time, or V dot D, when we first encounter a node and color it gray, and a finish time, V dot F, when we're done with it, and color it black.

So we're timestamping our exploration.

How does the actual DFS procedure work?

The main procedure starts by coloring everyone white, setting credit assessors to nothing, and initializing a global clock to zero.

Then it goes through each individual.

If it finds a white one, meaning we haven't explored from there yet, it calls this recursive procedure called DFS visit.

Recursive, meaning it calls itself.

That sounds pretty intense.

Yeah, it's like a function that keeps calling itself to dive deeper and deeper.

So in DFS visit, we increment our global clock, set the current time as the discovery time for that individual, and color them gray.

Then for each of their neighbors, if the neighbor is white, we set the current individual as their predecessor and call DFS visit again on that neighbor.

So we're really going deep down the rabbit hole with those recursive calls.

Exactly.

And once we've explored all our neighbors, we increment the clock again, record the finish time, and color the individual black.

So we're tracking when we enter and exit each individual's exploration.

And what about the efficiency of DFS?

Is it comparable to DFS?

Yep.

With adjacency lists, DFS also runs in time proportional to V plus E.

The main loop takes time proportional to V, and then all the calls to DFS visit together take time proportional to V plus E.

Okay, so both are quite efficient.

But it seems like these timestamps in DFS give us some extra information about the network structure.

Absolutely.

One cool thing is that the predecessor relationships form a depth -first forest, a collection of tree -like structures representing our exploration paths.

Plus, the discovery and finish times have this neat parenthesis structure.

Imagine drawing an opening parenthesis when you discover a node and a closing one when you finish.

They'll always be neatly nested or completely separate, reflecting the hierarchical way DFS explores.

It's like those nested Russian dolls.

Yeah.

What does that nesting tell us about the relationships between individuals?

It tells us about ancestry in the first forest.

If V is a descendant of U, meaning we started exploring V while exploring U and finished V before U, then U dot D will be less than V dot D, which will be less than V dot F, which will be less than U dot F.

You can also think of it like this.

At the moment we discover U, if there's a path from U to V consisting only of white nodes, then V will become a descendant of U.

That's the white path theorem.

So DFS not only explores, but it also reveals family trees within the network.

And then there's the way DFS classifies connections, which sounds like it gives us even more insight.

Right.

When we explore a connection from a gray individual U to another individual V, we can categorize it based on V's color at that moment.

If V is white, it's a tree edge, meaning it leads to a new part of the network.

If V is gray, it's a back edge, a loop back to an ancestor, which tells us there's a cycle in the network.

Ah, so back edges are like those loops in a maze that bring you back to where you started.

Precisely.

And if V is black and U was discovered before V, it's a forward edge, a connection to a descendant we've already explored.

And if V is black but U was discovered after V, it's a cross edge, which can connect different parts of the depth -first forest.

Oh, and one more interesting thing.

In undirected graphs, you'll only ever have tree edges and back edges.

So much information packed into a single exploration.

Now let's move on to those real world applications.

You mentioned topological sorting, which sounded incredibly useful.

What exactly is that and how does it leverage DFS?

Topological sorting is all about finding a linear order for things when there are dependencies between them.

Imagine you have a bunch of tasks, but some tasks need to be done before others.

Topological sort gives you a valid order to do those tasks so that everything gets done in the right sequence.

It's like figuring out the right order to assemble furniture.

And remember, this only works if there are no cycles in the dependencies, meaning no situations where task A depends on B, which depends on C, which depends back on A, that would be a circular dependency.

Okay, so it's about putting things in a sequence that respects the order they need to happen.

But how does DFS fit into this?

The beauty of it is the algorithm is super simple.

You run a standard DFS and as each individual gets finished colored black, you insert them at the front of a linked list.

Once DFS is done, that list will have your topological order.

Just like that.

Why does adding them to the front as they finish produce the correct order?

The key is that in a directed acyclic graph, DFS never finds back edges.

Now if you have a connection from U to V in your graph, when we explore that connection, V can't be gray because that would mean a back edge in their forest cycle.

So it has to be either white or black.

Exactly.

If it's white, it becomes a descendant of U, meaning its finish time will be earlier than U's.

And if it's black, it means we finished exploring V before U, so again, its finish time is earlier.

So by adding them to the front as they finish, anything that U points to will always end up after U in the list, which is exactly what we want for topological order.

Oh, that makes sense.

So it's subtly leveraging those finish times to create the order.

Really elegant.

Okay, last but not least, let's talk about finding strongly connected components.

What are those and how do we use our graph exploration tools to find them?

A strongly connected component, or SEC, is basically a cluster of individuals where everyone can reach everyone else within that cluster by following the connections.

Think of it like identifying friend groups where everyone's directly or indirectly connected within the group.

So it's about finding those self -contained sub networks.

How do we pin them down?

This one's a bit more involved.

We use something called the transpose of the graph,

which is basically the same graph, but with all the arrows flipped.

We denote it as G superscript T.

The interesting thing is that a graph and its transpose have the same SECs.

Okay, so we flip all the arrows.

What do we do with this backwards graph?

Here's how it works.

We first run a standard DFS on the original graph and record everyone's finish times.

Then we build the transpose graph G superscript T.

Now we run another DFS, but this time on G superscript T, and we process individuals in decreasing order of their finish times from that first DFS.

So we're running DFS twice, first on the original, then on the reverse graph, and paying attention to those finish times.

What's the significance of that order?

Here's the magic.

The individuals in each tree of the depth first forest from that second DFS, on the transpose graph, they form a separate SEC.

Why does this whole back and forth with DFS and the flipped graph actually work?

It seems pretty complex.

It's all about how the finish times relate to the structure of the network.

Think of it like this.

If there's a connection from one component to a different one, the latest finish time in the first component will always be greater than the latest finish time in the second.

So information flows from higher finish times to lower finish times.

Exactly.

And when we do that second DFS on the transpose graph, processing individuals in decreasing order of their finish times, we're essentially exploring those components in reverse topological order.

Each tree in that second forest represents a self -contained, strongly connected component.

That's incredible.

So with a couple of DFS runs and a clever manipulation of the graph, we can isolate those fundamental building blocks of the network.

You got it.

These elementary graph algorithms, how we represent networks, how we search them, and how we find these deeper structures, they're the bedrock for so much of our digital world, from navigating the internet to understanding social connections.

So let's take a moment to recap.

Today we learned about adjacency lists, great for those sparsely connected networks, and adjacency matrices, which give us super fast connection checks.

We explored breadth -first search, our level -by -level explorer for shortest paths, and depth -first search, our deep diver that uncovers network structure and helps us classify connections.

And we saw how those algorithms can be applied to real -world problems like topological sorting, putting things in order, and finding those tightly knit, strongly connected components.

Exactly.

And as you go about your day, dear listener, we encourage you to keep an eye out for those hidden networks.

See if you can spot the underlying graphs in everyday things, maybe in your social circles, or even the steps in a complex project.

It's amazing how often these concepts pop up once you start looking for them.

And with that, we've reached the end of our deep live for today.

Thanks for joining us.

Until next time, keep exploring those connections.