// 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 #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; }