-
Notifications
You must be signed in to change notification settings - Fork 0
/
GraphExtensions.cs
63 lines (53 loc) · 1.78 KB
/
GraphExtensions.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
using Graphs;
using System.Xml.Linq;
namespace BreadthFirstSearch;
/*
for graph with nodes: A, B, C, D
where: A -> B and C; B and C -> D
A
/ \
B C
\ /
D
BFS traversal sequence: A -> B -> C -> D
*/
public static class GraphExtensions
{
public static void BFS<T>(this Graph<T> graph, T startValue)
{
// Retrieve the start node from the graph using the provided value.
// If the start node is not found, handle the error appropriately.
var startNode = graph.GetNode(startValue);
if (startNode == null)
{
// handle
}
// Initialize a queue to keep track of nodes
// For BFS we use Queue - First-In-First-Out (FIFO) data structure
// queue is used to ensure that nodes are explored in the order they are discovered
// enabling level-by - level traversal of the graph
var queue = new Queue<Node<T>>();
var visited = new HashSet<Node<T>>();
// Add the start node to the queue and mark it as visited
queue.Enqueue(startNode);
visited.Add(startNode);
// Continue searching as long as there are nodes left to visit
while (queue.Count > 0)
{
var currentNode = queue.Dequeue();
if (!graph.Edges.TryGetValue(currentNode, out var edges))
continue;
foreach (var edge in edges)
{
var adjacentNode = edge.Node;
// If an adjacent node hasn't been visited
// add it to the queue and mark it as visited
if (!visited.Contains(adjacentNode))
{
visited.Add(adjacentNode);
queue.Enqueue(adjacentNode);
}
}
}
}
}