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

Windows Azure
10

Tourism
10

HTTP
10

TPL
9

ASP.NET vNext
8

OWIN
8

Git
7

Katana
7

JQuery
7

DLM
6

JavaScript
6

PowerShell
6

MS SQL
6

Microsoft
6

Deployment
6

NuGet
6

MongoDB
6

Razor
5

Docker
5

DbContext
5

Entity Framework
5

Unit Testing
5

Software Development
5

Microsoft Azure
5

GitHub
4

Hosting
4

Continuous Delivery
4

IT Stuff
4

SQL Server
4

IIS
4

Elasticsearch
4

.NET Core
4

ASP.NET Core
4

UNWTO
4

Redis
3

Polyglot Persistance
3

Caching
3

Architecture
3

Autofac
2

SemVer
2

OAuth
2

Security
2

Linux
2

Aspect Oriented Programming
2

Code Review
2

SQL Release
2

Software Engineer
2

gulp
2

Continuous Integration
2

nodejs
2

PostSharp
2

Random
2

Azure Search
2

Facts & Figures
2

WCF Web API
2

Blogging
2

Assignments
2

Deployments
2

RavenDB
2

Neo4j
1

Web Application
1

Visual Basic
1

tugberkugurlu.com
1

Time Saviour
1

Scaling
1

Blob Storage
1

Windows Server AppFabric
1

Projects
1

NGINX
1

Octopus Deploy
1

UX
1

Algorithms
1

Tourism Business
1

Identity
1

Data Structures
1

React
1

Machine Learning
1

xUnit
1

Continious Delivery
1

Azure Web Apps
1

Messaging
1

TV Series
1

Microsoft SQL Server
1

Bash
1

Programming
1

Windows Live Writer
1

Software
1

Dexter
1

Excel
1

Lucene.NET
1

Kafka
1

Career
1

Cognitive Services
1

eCommerce
1

MVP
1

TourismGeek
1

Graph
1

Azure
1

Tech Guys
1

Search
1

Redux
1

Web
1

Azure Storage
1

Congress & Convention Tourism
1

Concurrency
1

IoT
1

Web.Config
1

Travis CI
1

Microsoft Office
1

Docker Compose
1

Business
1

Roslyn
1

Distributed Systems
1

Windows 8
1

MvcScaffolding
1

SQL Injection
1