This repository has been archived by the owner on Dec 13, 2024. It is now read-only.
-
-
Notifications
You must be signed in to change notification settings - Fork 1
/
08-dfs_search.zig
128 lines (105 loc) · 3.46 KB
/
08-dfs_search.zig
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
const std = @import("std");
const print = std.debug.print;
const time = std.time;
const Instant = time.Instant;
const allocator = std.heap.page_allocator;
const Allocator = std.mem.Allocator;
const MAX_NODES: usize = 50_000; // Adjust as needed
/// Node structure for adjacency list
const Node = struct {
vertex: usize,
next: ?*Node,
};
/// Graph structure
const Graph = struct {
numVertices: usize,
adjLists: []?*Node, // Array of optional pointers to Nodes
visited: []bool, // Array of visited flags
/// Deinitialize the graph by freeing allocated memory
fn deinit(self: *Graph, alloc: Allocator) void {
// Free all nodes in adjacency lists
for (self.adjLists) |nodePtr| {
var node = nodePtr;
while (node) |currentNode| {
const nextNode = currentNode.next;
alloc.destroy(currentNode);
node = nextNode;
}
}
alloc.free(self.adjLists);
alloc.free(self.visited);
}
};
/// Function to create a node
fn createNode(alloc: Allocator, v: usize) !*Node {
const newNode = try alloc.create(Node);
newNode.* = Node{
.vertex = v,
.next = null,
};
return newNode;
}
/// Function to create a graph
fn createGraph(alloc: Allocator, vertices: usize) !*Graph {
const graph = try alloc.create(Graph);
graph.numVertices = vertices;
graph.adjLists = try alloc.alloc(?*Node, vertices);
graph.visited = try alloc.alloc(bool, vertices);
for (0..vertices) |i| {
graph.adjLists[i] = null;
graph.visited[i] = false;
}
return graph;
}
/// Function to add edge to an undirected graph
fn addEdge(alloc: Allocator, graph: *Graph, src: usize, dest: usize) !void {
// Add edge from src to dest
var newNode = try createNode(alloc, dest);
newNode.next = graph.adjLists[src];
graph.adjLists[src] = newNode;
// Since the graph is undirected, add edge from dest to src also
newNode = try createNode(alloc, src);
newNode.next = graph.adjLists[dest];
graph.adjLists[dest] = newNode;
}
/// DFS algorithm
fn dfs(graph: *Graph, vertex: usize) void {
graph.visited[vertex] = true;
var temp = graph.adjLists[vertex];
while (temp) |node| {
const adjVertex = node.vertex;
if (!graph.visited[adjVertex]) {
dfs(graph, adjVertex);
}
temp = node.next;
}
}
/// Main function to demonstrate DFS and measure execution time.
pub fn main() !void {
const N_values = [_]usize{ 1_000, 5_000, 10_000, 20_000, 50_000 };
for (N_values) |N| {
if (N > MAX_NODES) {
print("N exceeds MAX_NODES limit.\n", .{});
continue;
}
const graph = try createGraph(allocator, N);
defer allocator.destroy(graph);
defer graph.deinit(allocator);
// Build a connected graph (e.g., a chain)
for (0..N - 1) |i| {
try addEdge(allocator, graph, i, i + 1);
}
// Measure start time
const start = try Instant.now();
// Perform DFS starting from vertex 0
dfs(graph, 0);
// Measure end time
const end = try Instant.now();
// Calculate the elapsed time in seconds
const elapsed: f64 = @floatFromInt(end.since(start));
const time_spent = elapsed / time.ns_per_s;
// Print the result
print("DFS with N = {d}\n", .{N});
print("Time taken: {d} seconds\n\n", .{time_spent});
}
}