Skip to content

Instantly share code, notes, and snippets.

@dtinth
Created March 24, 2010 07:35
Show Gist options
  • Save dtinth/342069 to your computer and use it in GitHub Desktop.
Save dtinth/342069 to your computer and use it in GitHub Desktop.
#include <stdio.h>
#include <stdlib.h>
#define NUM_VERTEX 10
struct Vertex {
char name;
int mark;
struct Node* list;
};
struct Node {
struct Vertex* vertex;
struct Node* next;
};
struct Queue {
};
typedef struct Vertex Vertex;
typedef struct Node Node;
// creates a new vertex and return pointer to it
Vertex* new_vertex(char name) {
Vertex* vertex = (Vertex*)malloc(sizeof(Vertex));
vertex->name = name;
vertex->list = 0;
return vertex;
}
// connect the vertex a to vertex b
// by adding b to a's linked list!
void do_connect(Vertex* a, Vertex* b) {
Node* node = (Node*)malloc(sizeof(Node));
node->vertex = b;
node->next = a->list;
a->list = node;
}
// connects a to b and b to a
void connect(Vertex* a, Vertex* b) {
do_connect (a, b);
do_connect (b, a);
}
// visit function
void visit(Vertex* vertex) {
printf ("\n%5d. %c", vertex->mark, vertex->name);
}
// do a depth first search
void do_dfs(Vertex *vertex, int* count) {
Node* p = vertex->list;
vertex->mark = ++(*count);
visit (vertex);
while (p != 0) {
if (!p->vertex->mark) {
do_dfs (p->vertex, count);
}
p = p->next;
}
}
void dfs(Vertex *graph[]) {
int i;
int count = 0;
// set all to unvisited
for (i = 0; i < NUM_VERTEX; i ++) {
graph[i]->mark = 0;
}
// each vertex dfs it
for (i = 0; i < NUM_VERTEX; i ++) {
if (graph[i]->mark == 0) {
do_dfs (graph[i], &count);
}
}
}
// breadth first search
void do_bfs(Vertex *vertex, int* count) {
Node *initialQueue, *front, *rear, *p, *temp;
Vertex *w;
// count = count + 1, mark vertex with count
vertex->mark = ++(*count);
visit (vertex);
// initialize a queue, and initialize with vertex.
initialQueue = (Node*)malloc(sizeof(Node));
initialQueue->vertex = vertex;
initialQueue->next = 0;
front = initialQueue;
rear = initialQueue;
// while queue is not empty
while (front != 0) {
// for vertyex w in V adjacent to the front vertex
p = front->vertex->list;
while (p != 0) {
w = p->vertex;
// if w is marked with 0
if (w->mark == 0) {
Node* nextQueue;
// count = count + 1, mark w with count
w->mark = ++(*count);
visit (w);
// add w to queue
nextQueue = (Node*)malloc(sizeof(Node));
nextQueue->vertex = w;
nextQueue->next = 0;
rear->next = nextQueue;
rear = nextQueue;
}
p = p->next;
}
// remove front vertex from queue
temp = front;
front = front->next;
free (temp);
}
}
void bfs(Vertex *graph[]) {
int i;
int count = 0;
// set all to unvisited
for (i = 0; i < NUM_VERTEX; i ++) {
graph[i]->mark = 0;
}
// each vertex bfs it
for (i = 0; i < NUM_VERTEX; i ++) {
if (graph[i]->mark == 0) {
do_bfs (graph[i], &count);
}
}
}
// main function
int main() {
// create a adjacency list
Vertex *graph[NUM_VERTEX] = {
new_vertex('A'), //[0]
new_vertex('B'), //[1]
new_vertex('C'), //[2]
new_vertex('D'), //[3]
new_vertex('E'), //[4]
new_vertex('F'), //[5]
new_vertex('G'), //[6]
new_vertex('H'), //[7]
new_vertex('I'), //[8]
new_vertex('J') //[9]
};
// connect the vertices
connect(graph[0], graph[2]);
connect(graph[0], graph[3]);
connect(graph[0], graph[4]);
connect(graph[1], graph[4]);
connect(graph[1], graph[5]);
connect(graph[2], graph[3]);
connect(graph[2], graph[5]);
connect(graph[4], graph[5]);
connect(graph[6], graph[7]);
connect(graph[6], graph[9]);
connect(graph[7], graph[8]);
connect(graph[8], graph[9]);
// depth first search
printf ("DFS: ");
dfs (graph);
// breadth first search
printf ("\n\n");
printf ("BFS: ");
bfs (graph);
printf ("\n\nAnd that's it!!");
getchar ();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment