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.<\/p>\n
First, let\u2019s 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.<\/p>\n
Given a graph, implement the DFS and BFS algorithms to find a specific vertex from a given starting vertex.<\/p>\n
n<\/code> (2 \u2264 n \u2264 100)<\/li>\n- Number of edges:
m<\/code> (1 \u2264 m \u2264 300)<\/li>\n- List of edges: Each edge consists of two vertices (u, v)<\/li>\n
- Starting vertex:
start<\/code><\/li>\n- Vertex to find:
target<\/code><\/li>\n<\/ul>\nOutput<\/h3>\n
If it is possible to reach the target vertex from the starting vertex, output true<\/code>; otherwise, output false<\/code>.<\/p>\nProblem Solving<\/h2>\n
This problem can be solved using the DFS and BFS algorithms. Both methods are widely used techniques for graph traversal. First, let\u2019s examine the principles of both algorithms.<\/p>\n
DFS (Depth-First Search)<\/h3>\n
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.<\/p>\n
BFS (Breadth-First Search)<\/h3>\n
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.<\/p>\n
Implementation<\/h2>\n
Now, let\u2019s implement the DFS and BFS algorithms in C#.<\/p>\n
1. Graph Representation<\/h3>\n
A graph can be represented in an adjacency list form. For each node, the connected nodes are stored in a list.<\/p>\n
\npublic class Graph\n{\n private int vertices; \/\/ Number of vertices\n private List[] adjList; \/\/ Adjacency list\n\n public Graph(int n)\n {\n this.vertices = n;\n adjList = new List[n];\n for (int i = 0; i < n; i++)\n {\n adjList[i] = new List();\n }\n }\n\n \/\/ Method to add an edge\n public void AddEdge(int u, int v)\n {\n adjList[u].Add(v);\n adjList[v].Add(u); \/\/ Undirected graph\n }\n\n public List GetNeighbors(int vertex)\n {\n return adjList[vertex];\n }\n}\n<\/int><\/int><\/int><\/int><\/code><\/pre>\n2. DFS Implementation<\/h3>\n
DFS can be implemented recursively as follows.<\/p>\n
\npublic class DFS\n{\n private bool[] visited;\n private Graph graph;\n\n public DFS(Graph g)\n {\n this.graph = g;\n this.visited = new bool[g.vertices];\n }\n\n public bool Search(int start, int target)\n {\n \/\/ Mark the current node as visited\n if (start == target) return true;\n visited[start] = true;\n\n foreach (int neighbor in graph.GetNeighbors(start))\n {\n if (!visited[neighbor] && Search(neighbor, target))\n {\n return true; \/\/ Target found\n }\n }\n return false; \/\/ Target not found\n }\n}\n<\/code><\/pre>\n3. BFS Implementation<\/h3>\n
BFS is implemented by using a queue to explore the next nodes.<\/p>\n
\nusing System.Collections.Generic;\n\npublic class BFS\n{\n private bool[] visited;\n private Graph graph;\n\n public BFS(Graph g)\n {\n this.graph = g;\n this.visited = new bool[g.vertices];\n }\n\n public bool Search(int start, int target)\n {\n Queue queue = new Queue();\n queue.Enqueue(start);\n visited[start] = true;\n\n while (queue.Count > 0)\n {\n int current = queue.Dequeue();\n if (current == target) return true;\n\n foreach (int neighbor in graph.GetNeighbors(current))\n {\n if (!visited[neighbor])\n {\n queue.Enqueue(neighbor);\n visited[neighbor] = true;\n }\n }\n }\n return false; \/\/ Target not found\n }\n}\n<\/int><\/int><\/code><\/pre>\nTest Cases<\/h2>\n
Now let’s create a simple graph to test the implemented algorithms.<\/p>\n
\npublic class MainClass\n{\n public static void Main(string[] args)\n {\n Graph graph = new Graph(5);\n graph.AddEdge(0, 1);\n graph.AddEdge(0, 2);\n graph.AddEdge(1, 3);\n graph.AddEdge(1, 4);\n graph.AddEdge(2, 4);\n\n DFS dfs = new DFS(graph);\n BFS bfs = new BFS(graph);\n\n Console.WriteLine(\"DFS: \" + dfs.Search(0, 4)); \/\/ true\n Console.WriteLine(\"BFS: \" + bfs.Search(0, 4)); \/\/ true\n\n Console.WriteLine(\"DFS (No path): \" + dfs.Search(0, 5)); \/\/ false\n Console.WriteLine(\"BFS (No path): \" + bfs.Search(0, 5)); \/\/ false\n }\n}\n<\/code><\/pre>\nSummary<\/h2>\n
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.<\/p>\n
Through this article, I hope you understand DFS and BFS and develop the ability to handle various coding test problems.<\/p>\n
References<\/h2>\n\n- Geeks for Geeks<\/a><\/li>\n
- LeetCode<\/a><\/li>\n
- Books on algorithms<\/li>\n<\/ul>\n
Conclusion<\/h2>\n
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.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"