Graph Algorithms
Graph algorithms are essential in OODSA and play a crucial role in solving problems related to graphs. Graphs are mathematical structures that consist of a set of vertices (also known as nodes) and a set of edges that connect these vertices.
One commonly used graph algorithm is Depth First Search (DFS). DFS is a recursive algorithm that traverses or explores a graph in a depthward motion and can be used to solve various graph-related problems such as finding connected components, detecting cycles, and traversing a graph in a depthward motion.
Here's an example of implementing DFS in C#:
TEXT/X-CSHARP
1public class Graph
2{
3 private int numVertices;
4 private List<List<int>> adjacencyList;
5
6 public Graph(int numVertices)
7 {
8 this.numVertices = numVertices;
9 adjacencyList = new List<List<int>>(numVertices);
10 for (int i = 0; i < numVertices; i++)
11 {
12 adjacencyList.Add(new List<int>());
13 }
14 }
15
16 public void AddEdge(int startVertex, int endVertex)
17 {
18 adjacencyList[startVertex].Add(endVertex);
19 }
20
21 public List<int> GetAdjacencyList(int vertex)
22 {
23 return adjacencyList[vertex];
24 }
25
26 public int GetNumVertices()
27 {
28 return numVertices;
29 }
30}
31
32public void DFS(Graph graph, int startVertex)
33{
34 bool[] visited = new bool[graph.GetNumVertices()];
35 DFSUtil(graph, startVertex, visited);
36}
37
38public void DFSUtil(Graph graph, int vertex, bool[] visited)
39{
40 visited[vertex] = true;
41 Console.Write(vertex + " ");
42
43 List<int> adjacencyList = graph.GetAdjacencyList(vertex);
44 foreach (int neighbor in adjacencyList)
45 {
46 if (!visited[neighbor])
47 {
48 DFSUtil(graph, neighbor, visited);
49 }
50 }
51}
52
53Graph graph = new Graph(4);
54graph.AddEdge(0, 1);
55graph.AddEdge(0, 2);
56graph.AddEdge(1, 2);
57graph.AddEdge(2, 0);
58graph.AddEdge(2, 3);
59graph.AddEdge(3, 3);
60
61Console.WriteLine("Depth First Traversal (DFS) from starting vertex 2:");
62DFS(graph, 2);xxxxxxxxxx27
void DFS(Graph graph, int startVertex) { boolean[] visited = new boolean[graph.getNumVertices()]; DFSUtil(graph, startVertex, visited);}void DFSUtil(Graph graph, int vertex, boolean[] visited) { visited[vertex] = true; System.out.print(vertex + " "); LinkedList<Integer> adjacencyList = graph.getAdjacencyList(vertex); for (int neighbor : adjacencyList) { if (!visited[neighbor]) { DFSUtil(graph, neighbor, visited); } }}Graph graph = new Graph(4);graph.addEdge(0, 1);graph.addEdge(0, 2);graph.addEdge(1, 2);graph.addEdge(2, 0);graph.addEdge(2, 3);graph.addEdge(3, 3);System.out.println("Depth First Traversal (DFS) from starting vertex 2:");DFS(graph, 2);OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment
