To get a job as a software developer, algorithm tests are important. In particular, DFS (Depth-First Search) and BFS (Breadth-First Search) are fundamental concepts in graph traversal and are utilized in many problems. This article will introduce problems that use DFS and BFS algorithms and explain the problem-solving process in detail.
Problem Description
First, let’s assume there is a graph as follows. This graph consists of vertices (Vertex) and edges (Edge). We will solve the problem of exploring this graph to find a specific vertex.
Problem
Given a graph, implement the DFS and BFS algorithms to find a specific vertex from a given starting vertex.
Input
- Number of vertices:
n(2 ≤ n ≤ 100) - Number of edges:
m(1 ≤ m ≤ 300) - List of edges: Each edge consists of two vertices (u, v)
- Starting vertex:
start - Vertex to find:
target
Output
If it is possible to reach the target vertex from the starting vertex, output true; otherwise, output false.
Problem Solving
This problem can be solved using the DFS and BFS algorithms. Both methods are widely used techniques for graph traversal. First, let’s examine the principles of both algorithms.
DFS (Depth-First Search)
DFS is depth-first traversal, where one node is deeply explored, and if there are no more nodes to explore, it backtracks to explore other nodes. It can be implemented using a stack.
BFS (Breadth-First Search)
BFS is breadth-first traversal, where all neighboring nodes of one node are explored before moving on to the next neighboring node. It can be implemented using a queue data structure.
Implementation
Now, let’s implement the DFS and BFS algorithms in C#.
1. Graph Representation
A graph can be represented in an adjacency list form. For each node, the connected nodes are stored in a list.
public class Graph
{
private int vertices; // Number of vertices
private List[] adjList; // Adjacency list
public Graph(int n)
{
this.vertices = n;
adjList = new List[n];
for (int i = 0; i < n; i++)
{
adjList[i] = new List();
}
}
// Method to add an edge
public void AddEdge(int u, int v)
{
adjList[u].Add(v);
adjList[v].Add(u); // Undirected graph
}
public List GetNeighbors(int vertex)
{
return adjList[vertex];
}
}
2. DFS Implementation
DFS can be implemented recursively as follows.
public class DFS
{
private bool[] visited;
private Graph graph;
public DFS(Graph g)
{
this.graph = g;
this.visited = new bool[g.vertices];
}
public bool Search(int start, int target)
{
// Mark the current node as visited
if (start == target) return true;
visited[start] = true;
foreach (int neighbor in graph.GetNeighbors(start))
{
if (!visited[neighbor] && Search(neighbor, target))
{
return true; // Target found
}
}
return false; // Target not found
}
}
3. BFS Implementation
BFS is implemented by using a queue to explore the next nodes.
using System.Collections.Generic;
public class BFS
{
private bool[] visited;
private Graph graph;
public BFS(Graph g)
{
this.graph = g;
this.visited = new bool[g.vertices];
}
public bool Search(int start, int target)
{
Queue queue = new Queue();
queue.Enqueue(start);
visited[start] = true;
while (queue.Count > 0)
{
int current = queue.Dequeue();
if (current == target) return true;
foreach (int neighbor in graph.GetNeighbors(current))
{
if (!visited[neighbor])
{
queue.Enqueue(neighbor);
visited[neighbor] = true;
}
}
}
return false; // Target not found
}
}
Test Cases
Now let’s create a simple graph to test the implemented algorithms.
public class MainClass
{
public static void Main(string[] args)
{
Graph graph = new Graph(5);
graph.AddEdge(0, 1);
graph.AddEdge(0, 2);
graph.AddEdge(1, 3);
graph.AddEdge(1, 4);
graph.AddEdge(2, 4);
DFS dfs = new DFS(graph);
BFS bfs = new BFS(graph);
Console.WriteLine("DFS: " + dfs.Search(0, 4)); // true
Console.WriteLine("BFS: " + bfs.Search(0, 4)); // true
Console.WriteLine("DFS (No path): " + dfs.Search(0, 5)); // false
Console.WriteLine("BFS (No path): " + bfs.Search(0, 5)); // false
}
}
Summary
In this lecture, we examined how to solve graph traversal problems using DFS and BFS algorithms. Each traversal method has its strengths and weaknesses, and the appropriate method should be chosen based on the nature of the problem. DFS is advantageous for problems that require less memory usage and deep exploration but may take longer to find a path. On the other hand, BFS is advantageous for finding the shortest path but may use more memory.
Through this article, I hope you understand DFS and BFS and develop the ability to handle various coding test problems.
References
- Geeks for Geeks
- LeetCode
- Books on algorithms
Conclusion
Coding tests are an important process for evaluating a developer’s basic capabilities. The DFS and BFS algorithms are fundamental methods for graph traversal, making them excellent for solidifying your foundational skills. I hope you will learn various algorithms and data structures and improve your skills through practice.