summaryrefslogtreecommitdiff
path: root/targets/instr_bfs.c
diff options
context:
space:
mode:
Diffstat (limited to 'targets/instr_bfs.c')
-rw-r--r--targets/instr_bfs.c39
1 files changed, 39 insertions, 0 deletions
diff --git a/targets/instr_bfs.c b/targets/instr_bfs.c
new file mode 100644
index 0000000..a7b176e
--- /dev/null
+++ b/targets/instr_bfs.c
@@ -0,0 +1,39 @@
+// Breadth-first search from vertex 0 of a seven-vertex graph, one vertex
+// out of reach, argv[1] times (by default once). Exits with the number of
+// vertices reached.
+#include <stdlib.h>
+
+#define N 7
+static const int edges[][2] = {{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {4, 5}};
+static int adjacent[N][N];
+static int distance[N];
+static int order[N];
+
+static int bfs(int from) {
+ int queue[N], head = 0, tail = 0;
+ for (int v = 0; v < N; v++) distance[v] = -1;
+ distance[from] = 0;
+ queue[tail++] = from;
+ while (head < tail) {
+ int v = queue[head];
+ order[head++] = v;
+ for (int w = 0; w < N; w++) {
+ if (adjacent[v][w] && distance[w] < 0) {
+ distance[w] = distance[v] + 1;
+ queue[tail++] = w;
+ }
+ }
+ }
+ return tail;
+}
+
+int main(int argc, char **argv) {
+ int rounds = argc > 1 ? atoi(argv[1]) : 1;
+ int reached = 0;
+ for (unsigned i = 0; i < sizeof edges / sizeof *edges; i++) {
+ adjacent[edges[i][0]][edges[i][1]] = 1;
+ adjacent[edges[i][1]][edges[i][0]] = 1;
+ }
+ while (rounds-- > 0) reached = bfs(0);
+ return reached;
+}