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

Visual Studio
11

async
11

HTTP
10

Windows Azure
10

Tourism
10

TPL
9

OWIN
8

ASP.NET vNext
8

Katana
7

Git
7

JQuery
7

Deployment
6

Microsoft
6

JavaScript
6

NuGet
6

MS SQL
6

PowerShell
6

DLM
6

MongoDB
6

Unit Testing
5

Entity Framework
5

Software Development
5

DbContext
5

Razor
5

Microsoft Azure
5

Docker
5

Continuous Delivery
4

GitHub
4

IIS
4

Hosting
4

.NET Core
4

IT Stuff
4

Algorithms
4

Data Structures
4

UNWTO
4

Elasticsearch
4

SQL Server
4

ASP.NET Core
4

Caching
3

Golang
3

Redis
3

Architecture
3

Polyglot Persistance
3

Go
3

gulp
2

Code Review
2

Aspect Oriented Programming
2

Facts & Figures
2

PostSharp
2

Blogging
2

Assignments
2

OAuth
2

Linux
2

Continuous Integration
2

Azure Search
2

WCF Web API
2

Security
2

RavenDB
2

Autofac
2

SemVer
2

Random
2

Software Engineer
2

nodejs
2

Deployments
2

SQL Release
2

Congress & Convention Tourism
1

Dexter
1

Travis CI
1

Continious Delivery
1

Blob Storage
1

Azure
1

tugberkugurlu.com
1

SQL Injection
1

Roslyn
1

Windows 8
1

IoT
1

TourismGeek
1

NGINX
1

Cognitive Services
1

Tourism Business
1

Kafka
1

Distributed Systems
1

Azure Storage
1

Scaling
1

TV Series
1

Microsoft SQL Server
1

Identity
1

Machine Learning
1

Graph
1

Time Saviour
1

Windows Server AppFabric
1

Neo4j
1

Business
1

Docker Compose
1

Software
1

Messaging
1

Web Application
1

Search
1

Go Slices
1

MvcScaffolding
1

Bash
1

Web
1

Programming
1

Visual Basic
1

MVP
1

Tech Guys
1

Azure Web Apps
1

React
1

Web.Config
1

Microsoft Office
1

Lucene.NET
1

Excel
1

UX
1

Concurrency
1

xUnit
1

Redux
1

Career
1

eCommerce
1

Projects
1

Windows Live Writer
1

Octopus Deploy
1