Coder π¨π»βπ», Speaker π£, Author π, ex-Microsoft MVP πΈ, Blogger π», Software Engineering at Deliveroo π, F1 fan π, Loves travelling π«

I live in London, UK π‘

A while ago, I have written up on Graphs and gave a few examples about their application for real world problems. In this post, I want to talk about one of the most common graph algorithms, Depth-first search (DFS).

@ 2018-07-28 12:32:00

A while ago, I have written up on Graphs and gave a few examples about their application for real world problems. I absolutely love graphs as they are so powerful to model the data for several key computer science problems. In this post, I want to talk about one of the most common graph algorithms, Depth-first search (DFS) and how and where it could be useful.

DFS is a specific algorithm for traversing and searching a graph data structure. Depending on the type of graph, the algorithm might differ. However, the idea is actually quite simple for a Directed Acyclic Graph (DAG):

- You start with a source vertex (let's call it "S")
- You visit the first neighbour vertex of that node (let's call this "N")
- You do the same for "N" and you keep going till you end up at a leaf vertex (L) (which is a vertex that has no edges to another vertex)
- Then you visit the second neighbour of L's parent vertex.
- You would be once you exhaust all the vertices.

I must admit that this is a bit simplified version of the algorithm even for a DAG. For instance, we didn't touch on the fact that we might end up actually visiting the same vertex multiple times if we don't take this into account in our algorithm. There is a really good visualization of this algorithm here where you can observe how the algorithm works in a visual way through a logical graph representation.

There are various applications of DFS which are used to solve particular problems such as Topological Sorting and detecting cycle in a graph. There are also occasions where DFS is used as part of another known algorithm to solve a real world problem. One example to that is the Tarjanβs Algorithm to find Strongly Connected Components.

This is also a good resource which lists out different real world applications of DFS.

As you might guess, DFS is not the only known algorithm in order to traverse a graph data structure. Breadth-First Search (BFS) is a another most known graph traversal algorithm which has the similar semantics to DFS but instead of going in depth on a vertex, it prefers visit the all the neighbors of the current vertex. Bidirectional search is another one of the traversal algorithms which is mainly used to find a shortest path from an initial vertex to a goal vertex in a directed graph.

Hey, I'm Tugberk π

Coder π¨π»βπ», Speaker π£, Author π, ex-Microsoft MVP πΈ, Blogger π», Software Engineering at Deliveroo π, F1 fan π, Loves travelling π«

I live in London, UK π‘

ASP.Net

101

.net
75

ASP.NET Web API
49

ASP.NET MVC
42

C#
36

Geek Talks
30

ASP.NET 5
17

SignalR
16

Tips
14

async
11

Visual Studio
11

Tourism
10

Windows Azure
10

HTTP
10

TPL
9

OWIN
8

ASP.NET vNext
8

Katana
7

Git
7

JQuery
7

MongoDB
6

PowerShell
6

NuGet
6

DLM
6

Deployment
6

MS SQL
6

JavaScript
6

Microsoft
6

Microsoft Azure
5

Razor
5

Docker
5

DbContext
5

Entity Framework
5

Unit Testing
5

Software Development
5

Continuous Delivery
4

Algorithms
4

.NET Core
4

Elasticsearch
4

UNWTO
4

IT Stuff
4

ASP.NET Core
4

Hosting
4

IIS
4

Data Structures
4

GitHub
4

SQL Server
4

Go
3

Redis
3

Caching
3

Architecture
3

Golang
3

Polyglot Persistance
3

Deployments
2

Software Engineer
2

Code Review
2

SQL Release
2

OAuth
2

Aspect Oriented Programming
2

PostSharp
2

Security
2

Azure Search
2

nodejs
2

Assignments
2

gulp
2

Facts & Figures
2

Linux
2

Blogging
2

RavenDB
2

SemVer
2

Random
2

Autofac
2

WCF Web API
2

Continuous Integration
2

TV Series
1

Tech Guys
1

Lucene.NET
1

Web
1

Search
1

Cognitive Services
1

xUnit
1

Tourism Business
1

Dexter
1

Software
1

Congress & Convention Tourism
1

Messaging
1

TourismGeek
1

Kafka
1

Azure
1

Programming
1

Microsoft SQL Server
1

Microsoft Office
1

Projects
1

Docker Compose
1

UX
1

Neo4j
1

NGINX
1

React
1

Concurrency
1

Blob Storage
1

Career
1

Azure Storage
1

Continious Delivery
1

Windows Server AppFabric
1

Web Application
1

SQL Injection
1

tugberkugurlu.com
1

eCommerce
1

Visual Basic
1

Travis CI
1

Excel
1

MvcScaffolding
1

Roslyn
1

Go Slices
1

Scaling
1

Windows 8
1

MVP
1

Azure Web Apps
1

Octopus Deploy
1

IoT
1

Web.Config
1

Time Saviour
1

Business
1

Identity
1

Windows Live Writer
1

Bash
1

Graph
1

Machine Learning
1

Redux
1

Distributed Systems
1