Ψάξιμο κατά βάθος

Για να επισκευθούμε όλους τους κόμβους ενός γράφου με ν κόμβους χρειαζόμαστε έναν πίνακα λογικών μεταβλητών μιας διάστασης και μήκους ν ο οποίος περιέχει την τιμή "αληθές" για τους κόμβους τους οποίους έχουμε επισκευθεί. Η συστηματική επίσκεψη όλων των κόμβων γίνεται σύμφωνα με τα παρακάτω βήματα:

Φυλάμε την τιμή "ψευδές" στον πίνακα επισκέψεων.
Επισκεπτόμαστε όλους τους κόμβους που δεν έχουμε επισκευτεί.

Η επίσκεψη ενός κόμβου γίνεται σύμφωνα με τα παρακάτω βήματα:

Σημειώνουμε στον πίνακα ότι έχουμε επισκευθεί τον κόμβο.
Επισκεπτόμαστε όλους τους συνδεδεμένους κόμβους που δεν έχουμε επισκευθεί.

Το παρακάτω παράδειγμα περιέχει υλοποίηση για λίστα γειτνίασης:

#include <stdlib.h>
#include <stdio.h>

/*
 * Adjacency list for a graph of 10 nodes
 */
struct s_adjlist {
	int node;
	struct s_adjlist *next;
};

static struct s_adjlist *adj[10];
static int visited[10];

/*
 * Visit the nodes starting from node printing their value using
 * depth first search 
 */
static void
visit(int node)
{
	struct s_adjlist *p;

	visited[node] = 1;
	printf("%d\n", node);
	for (p = adj[node]; p != NULL; p = p->next)
		if (!visited[p->node])
			visit(p->node);
}

main()
{
	int a, b;
	struct s_adjlist *p;
	int i;

	/* Read edges and connect them */
	while (scanf("%d %d", &a, &b) == 2) {
		p = (struct s_adjlist *)malloc(sizeof(struct s_adjlist));
		p->node = b;
		p->next = adj[a];
		adj[a] = p;
		p = (struct s_adjlist *)malloc(sizeof(struct s_adjlist));
		p->node = a;
		p->next = adj[b];
		adj[b] = p;
	}
	/* Depth first search/print of the graph */
	for (i = 0; i < 10; i++)
		visited[i] = 0;
	for (i = 0; i < 10; i++)
		if (!visited[i])
			visit(i);
}

Αν το πρόγραμμα διαβάσει το γράφο:

θα τυπώσει την παρακάτω σειρά επίσκεψης: