👀 Views: 3 💬 Answers: 1 📅 Created: 2025-06-05

c# algorithm bfs graph C#

I'm refactoring my project and I'm building a feature where I've been struggling with this for a few days now and could really use some help. Quick question that's been bugging me - I'm working on a C# application where I need to implement a Breadth-First Search (BFS) algorithm to find the shortest path in an unweighted graph. However, I'm encountering an issue where my output does not seem to reflect the shortest path correctly, especially when there are multiple paths to the same node. The graph is represented as an adjacency list using a `Dictionary<int, List<int>>`. Here’s the code I've written so far: ```csharp using System; using System.Collections.Generic; class Graph { private Dictionary<int, List<int>> adjList; public Graph() { adjList = new Dictionary<int, List<int>>(); } public void AddEdge(int source, int destination) { if (!adjList.ContainsKey(source)) adjList[source] = new List<int>(); if (!adjList.ContainsKey(destination)) adjList[destination] = new List<int>(); adjList[source].Add(destination); adjList[destination].Add(source); // Undirected graph } public List<int> BFS(int start, int end) { Queue<int> queue = new Queue<int>(); Dictionary<int, bool> visited = new Dictionary<int, bool>(); Dictionary<int, int> parent = new Dictionary<int, int>(); queue.Enqueue(start); visited[start] = true; parent[start] = -1; while (queue.Count > 0) { int current = queue.Dequeue(); if (current == end) { return BuildPath(parent, end); } foreach (var neighbor in adjList[current]) { if (!visited.ContainsKey(neighbor)) { visited[neighbor] = true; parent[neighbor] = current; queue.Enqueue(neighbor); } } } return new List<int>(); // Return empty path if no path found } private List<int> BuildPath(Dictionary<int, int> parent, int end) { List<int> path = new List<int>(); for (int at = end; at != -1; at = parent[at]) { path.Add(at); } path.Reverse(); // Reverse the path to get the correct order return path; } } ``` I'm using this `BFS` method to find the path between two nodes in my graph, but the path returned is sometimes longer than expected. For example, when I try to find the path from node 1 to node 4, it returns [1, 2, 3, 4] instead of the shorter path [1, 4] when these edges exist directly. I suspect it might have something to do with how I'm managing the `visited` dictionary or the `parent` relationships. I've tried printing the contents of the `visited` and `parent` dictionaries during iteration, but they seem to be updated correctly. Any suggestions on what might be going wrong here? Am I missing an edge case in my BFS implementation or in how I'm constructing the path? Has anyone else encountered this? Hoping someone can shed some light on this. What's the correct way to implement this?