Queues
Stacks
just think of them as lists with restricted operations…
starting at a node, visit all of their neighbours, then visit their neighbours, then visit their neighbours…
void breadthFirst(Graph g, int src) {
bool *visited = calloc(g->nV, sizeof(bool));
int *pred = calloc(g->nV, sizeof(int));
Queue q = QueueNew();
visited[src] = true;
QueueEnqueue(q, src);
while (!QueueIsEmpty(q)) {
int v = QueueDequeue(q);
printf("%d\\n", v);
for (int w = 0; w < g->nV; w++) {
if (g->edges[v][w] && !visited[w]) {
visited[w] = true;
pred[w] = v;
QueueEnqueue(q, w);
}
}
}
free(visited);
free(pred);
QueueFree(q);
}
starting at a node, visit nodes until we cannot visit any more unvisited nodes, then backtrack and repeat
void depthFirst(Graph g, int src) {
bool *visited = calloc(g->nV, sizeof(bool));
int *pred = calloc(g->nV, sizeof(int));
Stack s = StackNew();
StackPush(s, src);
while (!StackIsEmpty(s)) {
int v = StackPop(s);
if (visited[v]) continue;
visited[v] = true;
printf("%d\\n", v);
for (int w = g->nV - 1; w >= 0; w--) {
if (g->edges[v][w] && !visited[w]) {
pred[w] = v;
StackPush(s, w);
}
}
}
free(visited);
free(pred);
StackFree(s);
}