June 15, 2026 • 20 mins
A comprehensive foundation for graph-processing algorithms. The text introduces undirected graphs as abstract mathematical models used to solve practical problems in fields like social networking, computer routing, and logistics. Through a structured design pattern, the authors present Depth-First Search (DFS) for exploring connectivity and Breadth-First Search (BFS) for identifying the shortest paths between points. Additionally, the source details the adjacency-lists data structure, which allows for the efficient storage and manipulation of massive, sparse datasets. Beyond theory, the text provides Java implementations and real-world examples, such as the "Kevin Bacon" game, to demonstrate how these computational methods analyze complex relationships.
You can listen and download our episodes for free on more than 10 different platforms:
https://linktr.ee/cyber_security_summary
Get the Book now from Amazon:
https://www.amazon.com/Algorithms-Part-II-Robert-Sedgewick-ebook/dp/B0DG5RN218?&linkCode=ll2&tag=cvthunderx-20&linkId=8cabddff83f14a757850774c84a817d2&language=en_US&ref_=as_li_ss_tl
Discover our free courses in tech and cybersecurity, Start learning today:
https://linktr.ee/cybercode_academy
You can listen and download our episodes for free on more than 10 different platforms:
https://linktr.ee/cyber_security_summary
Get the Book now from Amazon:
https://www.amazon.com/Algorithms-Part-II-Robert-Sedgewick-ebook/dp/B0DG5RN218?&linkCode=ll2&tag=cvthunderx-20&linkId=8cabddff83f14a757850774c84a817d2&language=en_US&ref_=as_li_ss_tl
Discover our free courses in tech and cybersecurity, Start learning today:
https://linktr.ee/cybercode_academy
Listen
Watch
Mark as Played
Transcript
Episode Transcript
Available transcripts are automatically generated. Complete accuracy is not guaranteed.
Speaker 1 (00:00):
So usually when you look at a map of a city,
there is this expectation of like static geography. You know,
you see the roads, you see the intersections, right, the
little blue line for the river. Yeah, exactly. The map
just sits there and basically says, you know, here's where
things are.
Speaker 2 (00:15):
It feels like a.
Speaker 3 (00:15):
Fixed picture, just a rigid grid of reality.
Speaker 1 (00:19):
But then you open up a routing app on your
phone and you punch in a destination and suddenly that
static map just comes alive. It's instantaneously calculating I mean,
millions of possibilities, routing you around traffic and finding the
absolute optimal path. Well in a fraction of a second.
Speaker 2 (00:39):
Yeah, the map isn't just a picture anymore.
Speaker 1 (00:40):
At that point, exactly, You're suddenly looking at this invisible,
underlying architecture that really governs how everything in our world connects.
Speaker 3 (00:47):
It is the absolute definition of a hidden mathematical engine.
And that engine is what we call.
Speaker 1 (00:54):
A graph, and that invisible architecture is exactly what we
are mapping out today. Welcome to today's deep dive. We
are diving deep into the science of graphs.
Speaker 3 (01:04):
And just to be absolutely clear, right out of the gate,
we are not talking about like the bar charts or
the line graphs from high.
Speaker 1 (01:12):
School algebra, right, No pie charts here, No, no.
Speaker 3 (01:14):
No, We are talking about mathematical models of pairwise connections.
So we have vertices which are the items themselves, and
we have edges which are the connections between them.
Speaker 1 (01:23):
And the sheer ubiquity of this model in our source
material is staggering. I mean, whether you're looking at a roadmap,
the World Wide Web, an electric circuit, or a massive
social network, you are looking at a graph.
Speaker 3 (01:38):
Absolutely, And the goal of our deep dive today is
to really explore how computer science uses these incredibly simple
models to solve seemingly impossible logistical scheduling and routing problems
in just mere milliseconds.
Speaker 1 (01:54):
Yeah, We're going to start with simple two way connections,
figure out how a computer explores them without getting lost,
and then we'll look at the complications of like one
way streets, which gets messy, oh very and finally we
will add actual costs to those paths. By the end,
we're answering questions ranging from you know, how the Java
programming language manages your computer's memory to how you calculate
(02:14):
your exact Kevin Bacon number.
Speaker 3 (02:16):
I love that one, But we do have to start
with the fundamental blueprint though, right.
Speaker 1 (02:20):
So the most basic model we have, Yeah.
Speaker 3 (02:22):
It's called the undirected graph. In an undirected graph, the
edges are simply two way connections. So if vertex A
is connected to vertex B, then B is connected to A.
Speaker 1 (02:33):
It's perfectly semetic, right, a standard two way street exactly.
Speaker 3 (02:37):
But the immediate challenge when you want to put this
into a computer is how to represent it without just
blowing through massive amounts of memory.
Speaker 1 (02:44):
Because I mean, if you have a massive network, say
billions of users on a social network, most people don't
know most other people, like, the connections are really sparse.
Speaker 2 (02:52):
Yeah, they are.
Speaker 3 (02:53):
And the intuitive way to represent this might be like
a giant grid what we call an adjacency matrix. Imagine
every single vertex has its own row and its own column,
and you just put a check mark where they intersect.
Speaker 1 (03:04):
Okay, makes sense in theory, in.
Speaker 3 (03:06):
Theory, sure, but for a network of millions, a matrix
takes up a prohibitive amount of space. You'd have this
massive grid where you know, ninety nine point nine percent
of the boxes.
Speaker 2 (03:16):
Are just empty.
Speaker 3 (03:17):
Oh wow, Yeah, it's a colossal waste of computing resources.
Speaker 1 (03:20):
So to fix that, the standard approach the sources talk
about is an adjacency list's data structure.
Speaker 2 (03:26):
Right.
Speaker 1 (03:26):
You basically just keep a master array of your vertices,
and for every single one you attach a simple, really
short list of only the vertices it actually connects to.
Speaker 3 (03:35):
You don't record the absences, only the presences.
Speaker 1 (03:38):
Yeah, it's elegant, and it saves exactly enough space to
make processing huge graphs possible.
Speaker 3 (03:45):
But which you have your graph efficiently stored in the computer,
you still need a way to explore it. And sources
bring up this amazing historical.
Speaker 1 (03:52):
Analogy for this, oh, dating back to antiquity, right, Trimo
mays exploration. Yes, I really love this concept. So for
you listen, imagine wandering through a massive physical maze. To
avoid getting hopelessly lost, you carry a ball of string. Right.
You unroll the string behind you as you walk down
any unvisited passage. When you hit an intersection, you mark
(04:15):
it with chalk, so you know you've been there. If
you hit a dead end or you know an intersection
you've already marked, you just turn around and use your
string to retrace your steps until you find a passage
you haven't gone.
Speaker 3 (04:25):
Down yet in that physical process.
Speaker 1 (04:28):
Ye.
Speaker 3 (04:28):
That is the exact mechanism of one of the most
fundamental algorithms in computer science. It's called depth first search
or DFS.
Speaker 1 (04:36):
DFS.
Speaker 3 (04:37):
Yeah, you follow a path as deeply into the graph
as you possibly can until you hit a dead end,
marking vertices as you visit them. Then you literally retrace
your steps back to the last intersection that had an
unexplored edge.
Speaker 1 (04:50):
And that string translates perfectly to a computer's memory, right
because DFS uses what.
Speaker 3 (04:54):
We call a stack exactly, a stack.
Speaker 1 (04:56):
Which operates on a last in, first out role. So
the last inner sec you pass is the very first
one you return to when you need to backtrack.
Speaker 3 (05:03):
It explores the graph by basically looking for new vertices
far away from the start point, and it only takes
closer vertices when it hits those dead ends. There's a
butt there is what if you don't just want to
explore the graph, What if you specifically want to find
the shortest path between two points. Depth first search doesn't
help much there, because it might take you on a
(05:25):
massive winding detour just based on which arbitrary path you
chose to go down first right.
Speaker 1 (05:30):
Because you're just picking a hallway and running. So if
DFS is a single person running as far as they
can down one winding hallway, bread first search or BFS
is well, it's like dropping a stone in a pond.
Speaker 2 (05:42):
Oh, that's a great way to put it.
Speaker 1 (05:44):
The search ripples outward perfectly. You fan out in all
directions at once, You check everywhere that is exactly one
step away. Then only after that one step ring is
completely checked, the search expands to everywhere that is two
steps away, and so on and programmatically.
Speaker 3 (05:59):
The difference is incredibly subtle but profound. Instead of a stack,
breadth first search.
Speaker 1 (06:04):
Uses a q Q right first and first out.
Speaker 3 (06:07):
Like waiting in line at a grocery store. It explores
the oldest discovered intersections first. This guarantees that when you
finally find the vertex you're looking for, you have found
the absolute shortest paths.
Speaker 1 (06:18):
To get there, because you literally already checked every single
path that was shorter exactly.
Speaker 2 (06:23):
You couldn't have missed a shorter way.
Speaker 1 (06:25):
So we've been talking about these vertices as like abstract
numbers vertex zero, vertex one, but in the real world,
data doesn't.
Speaker 3 (06:34):
Really look like that no, it rarely does, and that
brings in what we call symbol graphs.
Speaker 1 (06:39):
Right.
Speaker 3 (06:39):
In a symbol graph, the vertices aren't just integers, they
are strings of text. So they are airport codes like
JFK or LAX, or IP addresses or movie titles.
Speaker 1 (06:51):
And the source material uses the Kevin Bacon game as
the perfect example of this. They use an Internet movie
database file.
Speaker 2 (06:58):
Yes, the classic game.
Speaker 1 (06:59):
For anyone who hasn't played. The goal is to connect
any actor to Kevin Bacon through the movies they've co
starred in. But looking at this as a graph, there
is a fascinating structural detail here.
Speaker 2 (07:08):
Yeah, it's a bipartite graph.
Speaker 1 (07:09):
A bipartite graph. Break that down.
Speaker 3 (07:11):
So a bipartite graph is a network where the vertices
could be divided into two completely distinct sets, and the
key is edges only connect to vertex in one set
to a vertex in the other.
Speaker 1 (07:24):
Okay, So in this case, the two sets are movies
and actors.
Speaker 3 (07:27):
Right, Movies only connect to actors who are in them,
and actors only connect to the movies they acted in.
Speaker 1 (07:33):
So there's no direct actor to actor edge and no
movie to movie edge.
Speaker 3 (07:37):
You have to alternate exactly. And if you apply our
breadth first search algorithm to this bipartite symbol graph, you
effortlessly find the shortest alternating path. Wow, you started the
Kevin Bacon vertex. Ripple out to all the movies he
was in. That's a distance of one. Then you ripple
out to all the actors and all those.
Speaker 1 (07:53):
Movies, so all those actors have a Kevin Bacon number
of one.
Speaker 2 (07:56):
Right.
Speaker 3 (07:57):
Then you sweep to all the other movies those actors
were in, and so on. The BFS algorithm sweeps through
the database and instantaneously proves the Bacon number for anyone.
Speaker 1 (08:06):
And you could use the exact same logic to find
your Urdo's number if you're a mathematician based on like
co authored papers, or even a Bruce Springsteen number to
connect musicians. It's the exact same underlying architecture.
Speaker 3 (08:20):
It is, but there's a massive blind spot here.
Speaker 1 (08:23):
Okay, what's the blind spot?
Speaker 3 (08:24):
The Kevin Bacon game assumes mutual relationships, like if I
worked with you, you worked with me. Two way streets are
great for modeling a movie cast or a physical road network,
But what happens when the world isn't mutual.
Speaker 1 (08:38):
Oh, like, what if a webpage links to you but
you don't link.
Speaker 3 (08:41):
Back exactly, or a one way street in a city.
This brings in directographs or digraphs.
Speaker 1 (08:46):
Digraphs. Okay, so if we are just adding a directional
arrow to the etch, how much harder can this really
beat a process?
Speaker 2 (08:52):
Like?
Speaker 1 (08:52):
Does our ball of string from the maze still work?
Speaker 3 (08:55):
It gets profoundly harder because the moment you introduce direction
reach A bility is no longer symmetric. In a standard graph,
if vertex A can reach vertex B, B can obviously
reach A. In a digraph, the fact that A have
a path to B tells you absolutely nothing about whether
B can get back to A. It completely changes the
(09:15):
topological structure.
Speaker 1 (09:16):
But the depth for search algorithm still works to find
out what is reachable, right it only follows the arrows.
Speaker 3 (09:23):
Yes, it does. And a critical real world application of
this one way reachability is actually going on inside your
computer's ram right now?
Speaker 1 (09:32):
Eait really?
Speaker 2 (09:33):
Yeah?
Speaker 3 (09:33):
Specifically in Java's mark and sweep garbage collection.
Speaker 1 (09:36):
Garbage collection that sounds like something a sanitation truck does
not a programming language, well.
Speaker 3 (09:41):
In memory management, it's absolutely essential. So a running program
creates countless objects in memory. The computer treats all those
objects as vertices in a giant digraph, and the references
from one object to another are the directed edges. Okay, periodically,
the system just pauses and runs a digraph reachability algorithm
starting from the main program. It marks every object it
(10:02):
can reach by following those one way.
Speaker 1 (10:04):
Arrows, and anything that doesn't get marked is no.
Speaker 3 (10:06):
Longer connected to the active program. It's digital garbage. The
system then sweeps those unmarked objects away to free up memory.
Speaker 1 (10:15):
Wow, so it's just unrolling the tremo string through your
computer's memory. That's incredible.
Speaker 2 (10:19):
It really is.
Speaker 1 (10:20):
Another huge area where these one way arrows matter is scheduling.
So think about planning a college course schedule. You have
strict prerequisites. Oh wow, you know you have to take
introduction to CS before you can take advanced programming. You
have to take calculus before linear algebra.
Speaker 3 (10:36):
This is a classic precedence constrained scheduling problem. The vertices
are the courses and the directed ages are the prerequisites
pointing from the requirement to the advanced class. The goal
is to put all these vertices in a straight line,
an order where every single arrow points forward. You can't
take a class before. It's prerequisite in graph processing, finding
(10:57):
this order is called a topological sort.
Speaker 1 (11:00):
Okay, but hold on, that assumes everyone follows the rules.
What if the registrar completely screws up. What if course
A requires course B, course B requires course C, but
course C requires Course.
Speaker 3 (11:10):
A, then you have a massive problem. That is what
we call a directed cycle. If you trace the arrows,
you end up right back where you start it right.
If a graph has a directed cycle, scheduling is completely impossible.
No one can ever graduate.
Speaker 1 (11:24):
It's the ultimate bureaucratic catch twenty two exactly.
Speaker 3 (11:28):
Therefore, topological sorts only work on a very specific type
of graph, a day EAG, which stands for directed a
cyclic graph, a cyclic meaning containing no cycles.
Speaker 1 (11:39):
So before you can even try to schedule the classes,
you have to use a search algorithm just to prove
there are no cycles hiding in the rule book and the.
Speaker 3 (11:46):
Exact same depth first search we've been talking about solves
this too, by keeping track of the path that's currently
exploring the straying.
Speaker 2 (11:53):
In our maze.
Speaker 3 (11:54):
If it ever encounters a vertex that is already on
its current path, it has found a cycle. Ah, if
it explores a whole graph, it never hits its own string.
It's officially a dag and the schedule.
Speaker 2 (12:04):
Can be made.
Speaker 1 (12:05):
Okay, So cycles ruined schedules. We hate cycles and we
want things in a straight line. But what if a
cycle is exactly what we are looking for.
Speaker 3 (12:13):
Then we are looking for strong components and strong connectivity.
Speaker 1 (12:17):
Okay, break that down.
Speaker 3 (12:18):
Two vertices are strongly connected if they are mutually reachable.
So if there is a directed path from A to B,
in a directed path from B back to A, this
inherently means they're part of a directed cycle, right they loop.
A strong component is a cluster of vertices that are
all mutually reachable from one another.
Speaker 1 (12:35):
And the source material uses the example of an ecological
food web for this, which really helped me visualize it.
Imagine a massive digraph where the vertices are species and
the directed edges point from predator to prey. Identifying the
strong components in this massive web allows ecologists to understand
isolated energy flows. If a group of species are all
(12:58):
mutually reachable in this web represents a self contained cycle
of energy and nutrients.
Speaker 2 (13:03):
That's a great example.
Speaker 1 (13:04):
Or think about the world wide Web finding strong components
clusters together hyperlinked pages that all reference each other, which
helps search engines categorize the Internet.
Speaker 3 (13:13):
But computationally finding these massive, intertwined clusters of mutual reachability
in a network of millions of vertices it seems like
an impossibly complex task. If reachability isn't symmetric, how do
you efficiently group everyone who can reach everyone else?
Speaker 1 (13:32):
Yeah? When I read the steps for this in the
source material, it seemed like actual magic. It's called the
Cosaraji Sharer algorithm.
Speaker 2 (13:40):
It is brilliant.
Speaker 3 (13:40):
It finds all the strong components in a digraph in
linear time. The steps are deceptively simple.
Speaker 1 (13:45):
Okay, walk us through it.
Speaker 3 (13:47):
First, you take your digraph and you reverse every single
era you compute the reverse graph. Okay, Then you run
a search on that reverse graph, but you aren't just
looking around. You're keeping a very specific list. You record
the order in which the search finishes explod oring of
Vertex's path, essentially ranking who hits.
Speaker 1 (14:03):
A dead end last, tracking the dead ends.
Speaker 3 (14:04):
Got it? Then you use that specific reverse order to
run your second search on the original unreversed graph.
Speaker 1 (14:10):
Let me stop and explain why flipping the arrows actually works,
because this is where the genius really lies for me.
Speaker 2 (14:16):
Please do.
Speaker 1 (14:17):
If you are exploring a graph and you wander into
a strongly connected cluster, the danger is that you might
accidentally follow an arrow that leads out of the cluster
to some other random part of the graph, and since
it's a one way street, you can't get back. You
just bleed out into the rest of the web.
Speaker 3 (14:32):
Yes, exactly, you lose the cluster. By reversing the arrows
and ranking who hits dead end's last, you are essentially
finding the sinks, the places where flow pulls up. Wow.
When you run the second search using that specific order,
you guarantee that you are always starting in a cluster
where the only outgoing arrows have either been reversed or
(14:54):
point to things you've already found. It artificially traps the
search algorithm inside the cluster. It can't bleed up right,
so every time the search finishes its local sweep, that
isolated bucket of vertices is exactly one strong component.
Speaker 1 (15:07):
You just run a search, flip the graph and run
it again, and boot the complex ecosystem of predator and prey,
or the clustered communities of the World Wide Web. It
just falls out into perfectly organized buckets.
Speaker 2 (15:18):
Beautiful.
Speaker 1 (15:18):
It is absolutely breathtaking that something so complex is solved
by manipulating the flow like that.
Speaker 3 (15:25):
It's a testinate to how deeply understanding the mathematical properties
of the graph yeah, allows you to manipulate it. But
as we move forward, we have to recognize that in
the real world, navigating connections isn't just about whether a
path exists.
Speaker 1 (15:39):
Right, so far, all these connections we've talked about are free.
You either have an edge or you don't. But in reality,
taking a street costs something, which introduces us to edge
weighted graphs.
Speaker 3 (15:49):
We assign a value or a weight to every single connection.
Speaker 1 (15:54):
And my immediate assumption was that an edgeweight is obviously
the physical distance between two points, like the miles between
to airports on a routing map.
Speaker 3 (16:01):
Yeah, that's a very common misconception. Edgeweights can represent physical distance, yes,
but they can also represent the monetary cost of a flight,
or the time it takes for a signal to travel
down a wire, or.
Speaker 2 (16:12):
Even the amount of fuel burned.
Speaker 3 (16:13):
Okay, In fact, edgeways don't even have to be positive.
Speaker 2 (16:16):
They could be zero or even negative values.
Speaker 1 (16:19):
Wait, how can a cost be negative.
Speaker 3 (16:21):
Well, imagine a financial graph modeling currency exchange or stock transactions.
A negative weight might represent a guaranteed profit margin on
a trade. The math of the graph doesn't care what
the number represents, It just knows it needs to optimize it.
Speaker 1 (16:36):
Okay, that makes sense, and one of the most famous
optimization problems is finding the minimum spanning tree or MST.
Speaker 2 (16:43):
Right.
Speaker 1 (16:44):
The goal here is to find a set of edges
that connects every single vertex in the graph without any cycles,
and doing it with the absolute minimum total edge weight possible.
Speaker 3 (16:53):
And this is a profoundly important problem. If you are
laying electrical wiring for a new neighborhood, or laying fiber
optic network cables across an ocean, or even designing the
routing topology for an airline, you need to connect everything
using the absolute minimum amount of resources.
Speaker 1 (17:09):
But finding the minimum spanning tree without just guessing and
checking trillions of combinations, that requires something called the cut property.
Speaker 2 (17:16):
Think about it intuitively.
Speaker 3 (17:17):
Imagine taking all the vertices in your graph and drawing
a line that divides them into two completely isolated islands,
group A and group B.
Speaker 1 (17:25):
Okay, two islands.
Speaker 3 (17:26):
Now, look at all the potential edges that could cross
the water to connect those two islands. The cut property
says that if you want to build a spanning tree,
you absolutely have to build at least one bridge to
connect them. If you want to keep your overall cost down,
why wouldn't you pick the absolute cheapest bridge available. The
property mathematically proves that the crossing edge with the absolute
(17:49):
minimum weight must be part of the minimum spanning tree.
Speaker 1 (17:53):
So any random cut, as long as you divide the
graph into two, the cheapest edge bridging that gap is
guaranteed to be in the final optimal tree.
Speaker 2 (18:02):
Any cut it.
Speaker 1 (18:02):
All that is wild, And this leads to what computer
scientists call a greedy algorithm. Yes, greedy algorithms are amazing
because they seem almost too simple to work. A greedy
algorithm basically just says, at every single step, look at
the options right in front of you and just grab
the cheapest one. Don't worry about the big picture, don't
plan ten steps ahead, just make the best cheapest local
(18:24):
choice right now.
Speaker 3 (18:26):
It is counterintuitive, isn't it, And a lot of areas
in life making the greedy short term choice leads a
disaster down the road. Oh absolutely, But because of the
cut property in the minimum spanning tree problem. Continually making
the greedy local choice mathematically guarantees that you will end
up with the perfect optimal global solution.
Speaker 1 (18:47):
You just keep gobbling up the cheapest connection that doesn't
form a cycle, and when you've connected everything, you were
holding the perfect blueprint for your power grid or your network.
Speaker 3 (18:55):
It highlights a recurring theme in graph processing. Complex global
problem often have elegant solutions if you can just identify
the right local rule to follow.
Speaker 1 (19:04):
Man, what an incredible journey we just took.
Speaker 2 (19:06):
Yeah, we covered a lot of ground.
Speaker 1 (19:08):
We started out literally unrolling a ball of string to
get through a basic maze. Then we use that same
ripple effect to reveal the hidden bipartite web of Kevin
Bacon's movie career. We wrangled chaotic, impossible college schedules by
proving they were directed as cicclet graphs. We trapped cycles
to find mutually assured survival and food webs using the
(19:29):
sheer brilliance of the Kasarda Sharier algorithm. And finally we
routed the cheapest possible power grade using nothing but a
greedy local choice.
Speaker 3 (19:37):
Abstract mathematical models really are the silent force powering our
modern infrastructure. But I do want to leave you with
one final mind expanding thought, straight from the exercises in
our source material.
Speaker 1 (19:49):
Ooh, lay it on us.
Speaker 3 (19:50):
We've talked a lot about maps, computers, and social networks today,
but mathematical chemists used the exact same graph logic we
discussed today to analyze the build holding blocks of the
universe on They use something called the Wiener index. It's
calculated by summing the lengths of the shortest paths between
all pairs of vertices in a graph. But in their graphs,
the vertices are atoms and the egges are chemical bonds.
Speaker 1 (20:13):
Wow. Think about that for a second. The exact same
algorithmic logic your phone's map app uses to route your
car around a traffic jam is simultaneously being used by
scientists to decode the shape, the behavior, and the fundamental
structure of the microscopic molecules inside your own body.
Speaker 3 (20:30):
The rules of the graph apply the matter the scale.
Speaker 1 (20:34):
It really makes you look differently at that city map
we started with. It's not just a picture of streets.
It's a reflection of the invisible architecture that connects literally everything, atoms, actors,
internet pages and you. Everything is connected, and now you
know how to map it.
So usually when you look at a map of a city,
there is this expectation of like static geography. You know,
you see the roads, you see the intersections, right, the
little blue line for the river. Yeah, exactly. The map
just sits there and basically says, you know, here's where
things are.
Speaker 2 (00:15):
It feels like a.
Speaker 3 (00:15):
Fixed picture, just a rigid grid of reality.
Speaker 1 (00:19):
But then you open up a routing app on your
phone and you punch in a destination and suddenly that
static map just comes alive. It's instantaneously calculating I mean,
millions of possibilities, routing you around traffic and finding the
absolute optimal path. Well in a fraction of a second.
Speaker 2 (00:39):
Yeah, the map isn't just a picture anymore.
Speaker 1 (00:40):
At that point, exactly, You're suddenly looking at this invisible,
underlying architecture that really governs how everything in our world connects.
Speaker 3 (00:47):
It is the absolute definition of a hidden mathematical engine.
And that engine is what we call.
Speaker 1 (00:54):
A graph, and that invisible architecture is exactly what we
are mapping out today. Welcome to today's deep dive. We
are diving deep into the science of graphs.
Speaker 3 (01:04):
And just to be absolutely clear, right out of the gate,
we are not talking about like the bar charts or
the line graphs from high.
Speaker 1 (01:12):
School algebra, right, No pie charts here, No, no.
Speaker 3 (01:14):
No, We are talking about mathematical models of pairwise connections.
So we have vertices which are the items themselves, and
we have edges which are the connections between them.
Speaker 1 (01:23):
And the sheer ubiquity of this model in our source
material is staggering. I mean, whether you're looking at a roadmap,
the World Wide Web, an electric circuit, or a massive
social network, you are looking at a graph.
Speaker 3 (01:38):
Absolutely, And the goal of our deep dive today is
to really explore how computer science uses these incredibly simple
models to solve seemingly impossible logistical scheduling and routing problems
in just mere milliseconds.
Speaker 1 (01:54):
Yeah, We're going to start with simple two way connections,
figure out how a computer explores them without getting lost,
and then we'll look at the complications of like one
way streets, which gets messy, oh very and finally we
will add actual costs to those paths. By the end,
we're answering questions ranging from you know, how the Java
programming language manages your computer's memory to how you calculate
(02:14):
your exact Kevin Bacon number.
Speaker 3 (02:16):
I love that one, But we do have to start
with the fundamental blueprint though, right.
Speaker 1 (02:20):
So the most basic model we have, Yeah.
Speaker 3 (02:22):
It's called the undirected graph. In an undirected graph, the
edges are simply two way connections. So if vertex A
is connected to vertex B, then B is connected to A.
Speaker 1 (02:33):
It's perfectly semetic, right, a standard two way street exactly.
Speaker 3 (02:37):
But the immediate challenge when you want to put this
into a computer is how to represent it without just
blowing through massive amounts of memory.
Speaker 1 (02:44):
Because I mean, if you have a massive network, say
billions of users on a social network, most people don't
know most other people, like, the connections are really sparse.
Speaker 2 (02:52):
Yeah, they are.
Speaker 3 (02:53):
And the intuitive way to represent this might be like
a giant grid what we call an adjacency matrix. Imagine
every single vertex has its own row and its own column,
and you just put a check mark where they intersect.
Speaker 1 (03:04):
Okay, makes sense in theory, in.
Speaker 3 (03:06):
Theory, sure, but for a network of millions, a matrix
takes up a prohibitive amount of space. You'd have this
massive grid where you know, ninety nine point nine percent
of the boxes.
Speaker 2 (03:16):
Are just empty.
Speaker 3 (03:17):
Oh wow, Yeah, it's a colossal waste of computing resources.
Speaker 1 (03:20):
So to fix that, the standard approach the sources talk
about is an adjacency list's data structure.
Speaker 2 (03:26):
Right.
Speaker 1 (03:26):
You basically just keep a master array of your vertices,
and for every single one you attach a simple, really
short list of only the vertices it actually connects to.
Speaker 3 (03:35):
You don't record the absences, only the presences.
Speaker 1 (03:38):
Yeah, it's elegant, and it saves exactly enough space to
make processing huge graphs possible.
Speaker 3 (03:45):
But which you have your graph efficiently stored in the computer,
you still need a way to explore it. And sources
bring up this amazing historical.
Speaker 1 (03:52):
Analogy for this, oh, dating back to antiquity, right, Trimo
mays exploration. Yes, I really love this concept. So for
you listen, imagine wandering through a massive physical maze. To
avoid getting hopelessly lost, you carry a ball of string. Right.
You unroll the string behind you as you walk down
any unvisited passage. When you hit an intersection, you mark
(04:15):
it with chalk, so you know you've been there. If
you hit a dead end or you know an intersection
you've already marked, you just turn around and use your
string to retrace your steps until you find a passage
you haven't gone.
Speaker 3 (04:25):
Down yet in that physical process.
Speaker 1 (04:28):
Ye.
Speaker 3 (04:28):
That is the exact mechanism of one of the most
fundamental algorithms in computer science. It's called depth first search
or DFS.
Speaker 1 (04:36):
DFS.
Speaker 3 (04:37):
Yeah, you follow a path as deeply into the graph
as you possibly can until you hit a dead end,
marking vertices as you visit them. Then you literally retrace
your steps back to the last intersection that had an
unexplored edge.
Speaker 1 (04:50):
And that string translates perfectly to a computer's memory, right
because DFS uses what.
Speaker 3 (04:54):
We call a stack exactly, a stack.
Speaker 1 (04:56):
Which operates on a last in, first out role. So
the last inner sec you pass is the very first
one you return to when you need to backtrack.
Speaker 3 (05:03):
It explores the graph by basically looking for new vertices
far away from the start point, and it only takes
closer vertices when it hits those dead ends. There's a
butt there is what if you don't just want to
explore the graph, What if you specifically want to find
the shortest path between two points. Depth first search doesn't
help much there, because it might take you on a
(05:25):
massive winding detour just based on which arbitrary path you
chose to go down first right.
Speaker 1 (05:30):
Because you're just picking a hallway and running. So if
DFS is a single person running as far as they
can down one winding hallway, bread first search or BFS
is well, it's like dropping a stone in a pond.
Speaker 2 (05:42):
Oh, that's a great way to put it.
Speaker 1 (05:44):
The search ripples outward perfectly. You fan out in all
directions at once, You check everywhere that is exactly one
step away. Then only after that one step ring is
completely checked, the search expands to everywhere that is two
steps away, and so on and programmatically.
Speaker 3 (05:59):
The difference is incredibly subtle but profound. Instead of a stack,
breadth first search.
Speaker 1 (06:04):
Uses a q Q right first and first out.
Speaker 3 (06:07):
Like waiting in line at a grocery store. It explores
the oldest discovered intersections first. This guarantees that when you
finally find the vertex you're looking for, you have found
the absolute shortest paths.
Speaker 1 (06:18):
To get there, because you literally already checked every single
path that was shorter exactly.
Speaker 2 (06:23):
You couldn't have missed a shorter way.
Speaker 1 (06:25):
So we've been talking about these vertices as like abstract
numbers vertex zero, vertex one, but in the real world,
data doesn't.
Speaker 3 (06:34):
Really look like that no, it rarely does, and that
brings in what we call symbol graphs.
Speaker 1 (06:39):
Right.
Speaker 3 (06:39):
In a symbol graph, the vertices aren't just integers, they
are strings of text. So they are airport codes like
JFK or LAX, or IP addresses or movie titles.
Speaker 1 (06:51):
And the source material uses the Kevin Bacon game as
the perfect example of this. They use an Internet movie
database file.
Speaker 2 (06:58):
Yes, the classic game.
Speaker 1 (06:59):
For anyone who hasn't played. The goal is to connect
any actor to Kevin Bacon through the movies they've co
starred in. But looking at this as a graph, there
is a fascinating structural detail here.
Speaker 2 (07:08):
Yeah, it's a bipartite graph.
Speaker 1 (07:09):
A bipartite graph. Break that down.
Speaker 3 (07:11):
So a bipartite graph is a network where the vertices
could be divided into two completely distinct sets, and the
key is edges only connect to vertex in one set
to a vertex in the other.
Speaker 1 (07:24):
Okay, So in this case, the two sets are movies
and actors.
Speaker 3 (07:27):
Right, Movies only connect to actors who are in them,
and actors only connect to the movies they acted in.
Speaker 1 (07:33):
So there's no direct actor to actor edge and no
movie to movie edge.
Speaker 3 (07:37):
You have to alternate exactly. And if you apply our
breadth first search algorithm to this bipartite symbol graph, you
effortlessly find the shortest alternating path. Wow, you started the
Kevin Bacon vertex. Ripple out to all the movies he
was in. That's a distance of one. Then you ripple
out to all the actors and all those.
Speaker 1 (07:53):
Movies, so all those actors have a Kevin Bacon number
of one.
Speaker 2 (07:56):
Right.
Speaker 3 (07:57):
Then you sweep to all the other movies those actors
were in, and so on. The BFS algorithm sweeps through
the database and instantaneously proves the Bacon number for anyone.
Speaker 1 (08:06):
And you could use the exact same logic to find
your Urdo's number if you're a mathematician based on like
co authored papers, or even a Bruce Springsteen number to
connect musicians. It's the exact same underlying architecture.
Speaker 3 (08:20):
It is, but there's a massive blind spot here.
Speaker 1 (08:23):
Okay, what's the blind spot?
Speaker 3 (08:24):
The Kevin Bacon game assumes mutual relationships, like if I
worked with you, you worked with me. Two way streets are
great for modeling a movie cast or a physical road network,
But what happens when the world isn't mutual.
Speaker 1 (08:38):
Oh, like, what if a webpage links to you but
you don't link.
Speaker 3 (08:41):
Back exactly, or a one way street in a city.
This brings in directographs or digraphs.
Speaker 1 (08:46):
Digraphs. Okay, so if we are just adding a directional
arrow to the etch, how much harder can this really
beat a process?
Speaker 2 (08:52):
Like?
Speaker 1 (08:52):
Does our ball of string from the maze still work?
Speaker 3 (08:55):
It gets profoundly harder because the moment you introduce direction
reach A bility is no longer symmetric. In a standard graph,
if vertex A can reach vertex B, B can obviously
reach A. In a digraph, the fact that A have
a path to B tells you absolutely nothing about whether
B can get back to A. It completely changes the
(09:15):
topological structure.
Speaker 1 (09:16):
But the depth for search algorithm still works to find
out what is reachable, right it only follows the arrows.
Speaker 3 (09:23):
Yes, it does. And a critical real world application of
this one way reachability is actually going on inside your
computer's ram right now?
Speaker 1 (09:32):
Eait really?
Speaker 2 (09:33):
Yeah?
Speaker 3 (09:33):
Specifically in Java's mark and sweep garbage collection.
Speaker 1 (09:36):
Garbage collection that sounds like something a sanitation truck does
not a programming language, well.
Speaker 3 (09:41):
In memory management, it's absolutely essential. So a running program
creates countless objects in memory. The computer treats all those
objects as vertices in a giant digraph, and the references
from one object to another are the directed edges. Okay, periodically,
the system just pauses and runs a digraph reachability algorithm
starting from the main program. It marks every object it
(10:02):
can reach by following those one way.
Speaker 1 (10:04):
Arrows, and anything that doesn't get marked is no.
Speaker 3 (10:06):
Longer connected to the active program. It's digital garbage. The
system then sweeps those unmarked objects away to free up memory.
Speaker 1 (10:15):
Wow, so it's just unrolling the tremo string through your
computer's memory. That's incredible.
Speaker 2 (10:19):
It really is.
Speaker 1 (10:20):
Another huge area where these one way arrows matter is scheduling.
So think about planning a college course schedule. You have
strict prerequisites. Oh wow, you know you have to take
introduction to CS before you can take advanced programming. You
have to take calculus before linear algebra.
Speaker 3 (10:36):
This is a classic precedence constrained scheduling problem. The vertices
are the courses and the directed ages are the prerequisites
pointing from the requirement to the advanced class. The goal
is to put all these vertices in a straight line,
an order where every single arrow points forward. You can't
take a class before. It's prerequisite in graph processing, finding
(10:57):
this order is called a topological sort.
Speaker 1 (11:00):
Okay, but hold on, that assumes everyone follows the rules.
What if the registrar completely screws up. What if course
A requires course B, course B requires course C, but
course C requires Course.
Speaker 3 (11:10):
A, then you have a massive problem. That is what
we call a directed cycle. If you trace the arrows,
you end up right back where you start it right.
If a graph has a directed cycle, scheduling is completely impossible.
No one can ever graduate.
Speaker 1 (11:24):
It's the ultimate bureaucratic catch twenty two exactly.
Speaker 3 (11:28):
Therefore, topological sorts only work on a very specific type
of graph, a day EAG, which stands for directed a
cyclic graph, a cyclic meaning containing no cycles.
Speaker 1 (11:39):
So before you can even try to schedule the classes,
you have to use a search algorithm just to prove
there are no cycles hiding in the rule book and the.
Speaker 3 (11:46):
Exact same depth first search we've been talking about solves
this too, by keeping track of the path that's currently
exploring the straying.
Speaker 2 (11:53):
In our maze.
Speaker 3 (11:54):
If it ever encounters a vertex that is already on
its current path, it has found a cycle. Ah, if
it explores a whole graph, it never hits its own string.
It's officially a dag and the schedule.
Speaker 2 (12:04):
Can be made.
Speaker 1 (12:05):
Okay, So cycles ruined schedules. We hate cycles and we
want things in a straight line. But what if a
cycle is exactly what we are looking for.
Speaker 3 (12:13):
Then we are looking for strong components and strong connectivity.
Speaker 1 (12:17):
Okay, break that down.
Speaker 3 (12:18):
Two vertices are strongly connected if they are mutually reachable.
So if there is a directed path from A to B,
in a directed path from B back to A, this
inherently means they're part of a directed cycle, right they loop.
A strong component is a cluster of vertices that are
all mutually reachable from one another.
Speaker 1 (12:35):
And the source material uses the example of an ecological
food web for this, which really helped me visualize it.
Imagine a massive digraph where the vertices are species and
the directed edges point from predator to prey. Identifying the
strong components in this massive web allows ecologists to understand
isolated energy flows. If a group of species are all
(12:58):
mutually reachable in this web represents a self contained cycle
of energy and nutrients.
Speaker 2 (13:03):
That's a great example.
Speaker 1 (13:04):
Or think about the world wide Web finding strong components
clusters together hyperlinked pages that all reference each other, which
helps search engines categorize the Internet.
Speaker 3 (13:13):
But computationally finding these massive, intertwined clusters of mutual reachability
in a network of millions of vertices it seems like
an impossibly complex task. If reachability isn't symmetric, how do
you efficiently group everyone who can reach everyone else?
Speaker 1 (13:32):
Yeah? When I read the steps for this in the
source material, it seemed like actual magic. It's called the
Cosaraji Sharer algorithm.
Speaker 2 (13:40):
It is brilliant.
Speaker 3 (13:40):
It finds all the strong components in a digraph in
linear time. The steps are deceptively simple.
Speaker 1 (13:45):
Okay, walk us through it.
Speaker 3 (13:47):
First, you take your digraph and you reverse every single
era you compute the reverse graph. Okay, Then you run
a search on that reverse graph, but you aren't just
looking around. You're keeping a very specific list. You record
the order in which the search finishes explod oring of
Vertex's path, essentially ranking who hits.
Speaker 1 (14:03):
A dead end last, tracking the dead ends.
Speaker 3 (14:04):
Got it? Then you use that specific reverse order to
run your second search on the original unreversed graph.
Speaker 1 (14:10):
Let me stop and explain why flipping the arrows actually works,
because this is where the genius really lies for me.
Speaker 2 (14:16):
Please do.
Speaker 1 (14:17):
If you are exploring a graph and you wander into
a strongly connected cluster, the danger is that you might
accidentally follow an arrow that leads out of the cluster
to some other random part of the graph, and since
it's a one way street, you can't get back. You
just bleed out into the rest of the web.
Speaker 3 (14:32):
Yes, exactly, you lose the cluster. By reversing the arrows
and ranking who hits dead end's last, you are essentially
finding the sinks, the places where flow pulls up. Wow.
When you run the second search using that specific order,
you guarantee that you are always starting in a cluster
where the only outgoing arrows have either been reversed or
(14:54):
point to things you've already found. It artificially traps the
search algorithm inside the cluster. It can't bleed up right,
so every time the search finishes its local sweep, that
isolated bucket of vertices is exactly one strong component.
Speaker 1 (15:07):
You just run a search, flip the graph and run
it again, and boot the complex ecosystem of predator and prey,
or the clustered communities of the World Wide Web. It
just falls out into perfectly organized buckets.
Speaker 2 (15:18):
Beautiful.
Speaker 1 (15:18):
It is absolutely breathtaking that something so complex is solved
by manipulating the flow like that.
Speaker 3 (15:25):
It's a testinate to how deeply understanding the mathematical properties
of the graph yeah, allows you to manipulate it. But
as we move forward, we have to recognize that in
the real world, navigating connections isn't just about whether a
path exists.
Speaker 1 (15:39):
Right, so far, all these connections we've talked about are free.
You either have an edge or you don't. But in reality,
taking a street costs something, which introduces us to edge
weighted graphs.
Speaker 3 (15:49):
We assign a value or a weight to every single connection.
Speaker 1 (15:54):
And my immediate assumption was that an edgeweight is obviously
the physical distance between two points, like the miles between
to airports on a routing map.
Speaker 3 (16:01):
Yeah, that's a very common misconception. Edgeweights can represent physical distance, yes,
but they can also represent the monetary cost of a flight,
or the time it takes for a signal to travel
down a wire, or.
Speaker 2 (16:12):
Even the amount of fuel burned.
Speaker 3 (16:13):
Okay, In fact, edgeways don't even have to be positive.
Speaker 2 (16:16):
They could be zero or even negative values.
Speaker 1 (16:19):
Wait, how can a cost be negative.
Speaker 3 (16:21):
Well, imagine a financial graph modeling currency exchange or stock transactions.
A negative weight might represent a guaranteed profit margin on
a trade. The math of the graph doesn't care what
the number represents, It just knows it needs to optimize it.
Speaker 1 (16:36):
Okay, that makes sense, and one of the most famous
optimization problems is finding the minimum spanning tree or MST.
Speaker 2 (16:43):
Right.
Speaker 1 (16:44):
The goal here is to find a set of edges
that connects every single vertex in the graph without any cycles,
and doing it with the absolute minimum total edge weight possible.
Speaker 3 (16:53):
And this is a profoundly important problem. If you are
laying electrical wiring for a new neighborhood, or laying fiber
optic network cables across an ocean, or even designing the
routing topology for an airline, you need to connect everything
using the absolute minimum amount of resources.
Speaker 1 (17:09):
But finding the minimum spanning tree without just guessing and
checking trillions of combinations, that requires something called the cut property.
Speaker 2 (17:16):
Think about it intuitively.
Speaker 3 (17:17):
Imagine taking all the vertices in your graph and drawing
a line that divides them into two completely isolated islands,
group A and group B.
Speaker 1 (17:25):
Okay, two islands.
Speaker 3 (17:26):
Now, look at all the potential edges that could cross
the water to connect those two islands. The cut property
says that if you want to build a spanning tree,
you absolutely have to build at least one bridge to
connect them. If you want to keep your overall cost down,
why wouldn't you pick the absolute cheapest bridge available. The
property mathematically proves that the crossing edge with the absolute
(17:49):
minimum weight must be part of the minimum spanning tree.
Speaker 1 (17:53):
So any random cut, as long as you divide the
graph into two, the cheapest edge bridging that gap is
guaranteed to be in the final optimal tree.
Speaker 2 (18:02):
Any cut it.
Speaker 1 (18:02):
All that is wild, And this leads to what computer
scientists call a greedy algorithm. Yes, greedy algorithms are amazing
because they seem almost too simple to work. A greedy
algorithm basically just says, at every single step, look at
the options right in front of you and just grab
the cheapest one. Don't worry about the big picture, don't
plan ten steps ahead, just make the best cheapest local
(18:24):
choice right now.
Speaker 3 (18:26):
It is counterintuitive, isn't it, And a lot of areas
in life making the greedy short term choice leads a
disaster down the road. Oh absolutely, But because of the
cut property in the minimum spanning tree problem. Continually making
the greedy local choice mathematically guarantees that you will end
up with the perfect optimal global solution.
Speaker 1 (18:47):
You just keep gobbling up the cheapest connection that doesn't
form a cycle, and when you've connected everything, you were
holding the perfect blueprint for your power grid or your network.
Speaker 3 (18:55):
It highlights a recurring theme in graph processing. Complex global
problem often have elegant solutions if you can just identify
the right local rule to follow.
Speaker 1 (19:04):
Man, what an incredible journey we just took.
Speaker 2 (19:06):
Yeah, we covered a lot of ground.
Speaker 1 (19:08):
We started out literally unrolling a ball of string to
get through a basic maze. Then we use that same
ripple effect to reveal the hidden bipartite web of Kevin
Bacon's movie career. We wrangled chaotic, impossible college schedules by
proving they were directed as cicclet graphs. We trapped cycles
to find mutually assured survival and food webs using the
(19:29):
sheer brilliance of the Kasarda Sharier algorithm. And finally we
routed the cheapest possible power grade using nothing but a
greedy local choice.
Speaker 3 (19:37):
Abstract mathematical models really are the silent force powering our
modern infrastructure. But I do want to leave you with
one final mind expanding thought, straight from the exercises in
our source material.
Speaker 1 (19:49):
Ooh, lay it on us.
Speaker 3 (19:50):
We've talked a lot about maps, computers, and social networks today,
but mathematical chemists used the exact same graph logic we
discussed today to analyze the build holding blocks of the
universe on They use something called the Wiener index. It's
calculated by summing the lengths of the shortest paths between
all pairs of vertices in a graph. But in their graphs,
the vertices are atoms and the egges are chemical bonds.
Speaker 1 (20:13):
Wow. Think about that for a second. The exact same
algorithmic logic your phone's map app uses to route your
car around a traffic jam is simultaneously being used by
scientists to decode the shape, the behavior, and the fundamental
structure of the microscopic molecules inside your own body.
Speaker 3 (20:30):
The rules of the graph apply the matter the scale.
Speaker 1 (20:34):
It really makes you look differently at that city map
we started with. It's not just a picture of streets.
It's a reflection of the invisible architecture that connects literally everything, atoms, actors,
internet pages and you. Everything is connected, and now you
know how to map it.
Popular Podcasts
Stuff You Should Know
If you've ever wanted to know about champagne, satanism, the Stonewall Uprising, chaos theory, LSD, El Nino, true crime and Rosa Parks, then look no further. Josh and Chuck have you covered.
Dateline NBC
Current and classic episodes, featuring compelling true-crime mysteries, powerful documentaries and in-depth investigations. Follow now to get the latest episodes of Dateline NBC completely free, or subscribe to Dateline Premium for ad-free listening and exclusive bonus content: DatelinePremium.com
Betrayal Weekly
Betrayal Weekly is back for a new season. Every Thursday, Betrayal Weekly shares first-hand accounts of broken trust, shocking deceptions, and the trail of destruction they leave behind. Hosted by Andrea Gunning, this weekly ongoing series digs into real-life stories of betrayal and the aftermath. From stories of double lives to dark discoveries, these are cautionary tales and accounts of resilience against all odds. From the producers of the critically acclaimed Betrayal series, Betrayal Weekly drops new episodes every Thursday. If you would like to share your story, you can reach out to the Betrayal Team by emailing them at betrayalpod@gmail.com and follow us on Instagram at @betrayalpod and @glasspodcasts. Please join our Substack for additional exclusive content, curated book recommendations, and community discussions. Sign up FREE by clicking this link Beyond Betrayal Substack. Join our community dedicated to truth, resilience, and healing. Your voice matters! Be a part of our Betrayal journey on Substack.