ass1

ass2

quick review — ADTs

Queues

• FIFO
• two main operations: enqueue and dequeue

Stacks

• LIFO
• two main operations: push and pop

just think of them as lists with restricted operations…

BFS

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);
}

DFS

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);
}