COMP2521 | COMP2521 Exam |
Topic Index: Linear ADTs ... Sorting ... Searching ... Graphs
This document gives code for representative ADTs and algorithms discussed in Lectures. It's organised as a single long page, broken down by topic area. The code assumes that all collection types are made up of Items, where the Item type has equality, less than, greater than, comparison, and display functions available as eq(it1,it2), less(it1,it2), greater(it1,it2), cmp(it1,it2) and show(it). Sometimes, Items have keys which are integer or string values that uniquely identify the Item. They key value can be extracted from an Item using the key(it) function. ADTs are implemented via a pointer to a hidden representation type (e.g. the Stack type is a pointer to a StackRep structure).
Note: the code below has not been compiled; we make no guarantees that there are no bugs. This code is provided simply as a guide to how the algorithms were implemented.
Interface:
typedef struct StackRep *Stack; // set up empty stack Stack newStack(int); // remove unwanted stack void dropStack(Stack); // insert an Item on top of stack void StackPush(Stack,Item); // remove Item from top of stack Item StackPop(Stack); // check whether stack is empty Bool StackIsEmpty(Stack);
Implementation (via arrays):
typedef struct StackRep { Item *item; int top; } StackRep; // set up empty stack Stack newStack(int n) { Stack s; s = malloc(sizeof(StackRep)); assert(s != NULL); s->item = malloc(n * sizeof(Item)); assert(s->item != NULL); s->top = -1; return s; } // remove unwanted stack void dropStack(Stack s) { assert(s != NULL); free(s->item); free(s); } // insert Item on top of stack void StackPush(Stack s, Item it) { assert(s->top < MAXITEMS-1); s->top++; int i = s->top; s->item[i] = it; } // remove Item from top of stack Item StackPop(Stack s) { assert(s->top > -1); int i = s->top; Item it = s->item[i]; s->top--; return it; } // check whether stack is empty Bool StackIsEmpty(Stack s) { return (s->top < 0); }
Interface:
typedef struct QueueRep *Queue; // set up empty queue Queue newQueue(int); // remove unwanted queue void dropQueue(Queue); // insert Item at back of queue void QueueJoin(Queue,Item); // remove Item from front of queue Item QueueLeave(Queue); // check whether queue is empty Bool QueueIsEmpty(Queue);
Implementation (via arrays):
typedef struct QueueRep { Item *item; // array to hold Items int front; // next Item to be removed int back; // last Item added int nitems; // # Items currently in queue int maxitems; // size of array } QueueRep; // set up empty queue Queue newQueue(int n) { Queue q; q = malloc(sizeof(QueueRep)); assert(q != NULL); q->item = malloc(n * sizeof(Item)); assert(q->item != NULL); q->front = q->back = 0; q->nitems = 0; q->maxitems = n; return q; } // remove unwanted queue void dropQueue(Queue q) { assert(q != NULL); free(q->item); free(q); } // insert item on top of queue void QueueJoin(Queue q, Item it) { assert(q->nitems < q->maxitems); q->item[q->front] = it; q->nitems++; q->front = (q->front+1)%q->maxitems; } // remove item from front of queue Item QueueLeave(Queue q) { assert(q->nitems > 0); Item it = q->item[q->back]; q->nitems--; q->back = (q->back+1)%q->maxitems; return it; } // check whether queue is empty Bool QueueIsEmpty(Queue q) { return (q->nitems == 0); }
Priority Queue:
Interface:
typedef struct PQueueRep *PQueue; create new empty priority queue PQueue newPQueue(int size); add item to priority queue void PQJoin(PQueue q, Item it); remove item from priority queue Item PQLeave(PQueue q); free up priority queue void dropPQueue(PQueue q);
Implementation:
struct PQueueRep { int nItems; // count of items Item *items; // heap-array of Items int size; // size of array } // create a new empty queue PQueue newPQueue(int size) { PQueue q = malloc(sizeof(struct PQrep)); assert(q != NULL); // indexes start from 1 q->items = malloc(sizeof(Item) * (size+1)); assert(q->items != NULL); q->nItems = 0; q->size = size; return q; } // add a new item into the queue void PQJoin(PQueue q, Item it) { assert(q != NULL && q->nItems < q->size); q->nItems++; q->items[q->nItems] = it; fixUp(q->items, q->nItems); } // remove item from priority queue Item PQLeave(PQueue q) { assert(q != NULL && q->nItems > 0); swap(q->items, 1, q->nItems); q->nItems--; fixDown(p->items, 1, q->nItems); return q->items[q->nItems+1]; } free up priority queue void dropPQueue(PQueue q) { assert(q != NULL); free(q->items); free(q); } void fixUp(Item a[], int k) { while (k > 1 && less(a[k/2],a[k])) { swap(a, k, k/2); k = k/2; // integer division } } void fixDown(Item a[], int k, int N) { while (2*k <= N) { int j = 2*k; // choose larger of two children if (j < N && less(a[j], a[j+1])) j++; if (!less(a[k], a[j])) break; swap(a, k, j); k = j; } }
Sorting problem:
Pre-condition: a[0..N-1] contain Items Post-condition: forall i:0..N-2, key(a[i]) ≤ key(a[i+1])
Selection sort:
void selectionSort(int a[], int lo, int hi) { int i, j, min; for (i = lo; i < hi; i++) { min = i; for (j = i+1; j <= hi; j++) { if (less(a[j],a[min])) min = j; } swap(a[i], a[min]); } }
Bubble sort:
void bubbleSort(int a[], int lo, int hi) { int i, j; for (i = lo; i < hi; i++) { for (j = hi; j > i; j--) { if (less(a[j], a[j-1])) { swap(a[j], a[j-1]); } } } }
Bubble sort with Early Exit:
void bubbleSort(int a[], int lo, int hi) { int i, j, nswaps; for (i = lo; i < hi; i++) { nswaps = 0; for (j = hi; j > i; j--) { if (less(a[j], a[j-1])) { swap(a[j], a[j-1]); nswaps++; } } if (nswaps == 0) break; } }
Insertion sort:
void insertionSort(int a[], int lo, int hi) { int i, j, val; for (i = lo+1; i <= hi; i++) { val = a[i]; for (j = i; j > lo; j--) { if (!less(val,a[j-1])) break; a[j] = a[j-1]; } a[j] = val; } }
Shell sort:
void shellSort(int a[], int lo, int hi) { int n = (hi-lo) + 1; int i, j, h; //calculate starting h value for (h = 1; h <= (n - 1)/9; h = (3 * h) + 1) { printf("%d ",h); } for (; h > 0; h /= 3) { for (i = h; i < n; i++) { int key = a[i]; for (j = i; j >= h && key < a[j - h] ; j -=h) { a[j] = a[j - h]; } a[j] = key; } } } }
Quicksort: (with median-of-three partitioning)
void quicksort(Item a[], int lo, int hi) { int i; // index of pivot if (hi <= lo) return; medianOfThree(a, lo, hi); i = partition(a, lo+1, hi-1); quicksort(a, lo, i-1); quicksort(a, i+1, hi); } void medianOfThree(Item a[], int lo, int hi) { int mid = (lo+hi)/2; if (less(a[mid],a[lo])) swap(a, lo, mid); if (less(a[hi],a[mid])) swap(a, mid, hi); if (less(a[mid],a[lo])) swap(a, lo, mid); // now, we have a[lo] ≤ a[mid] ≤ a[hi] // swap a[mid] to a[lo+1] to use as pivot swap(a, lo+1, mid); } int partition(Item a[], int lo, int hi) { Item v = a[lo]; // pivot int i = lo+1, j = hi; for (;;) { while (less(a[i],v) && i < j) i++; while (less(v,a[j]) && j > i) j--; if (i == j) break; swap(a,i,j); } j = less(a[i],v) ? i : i-1; swap(a,lo,j); return j; }
Mergesort:
void mergesort(Item a[], int lo, int hi) { int mid = (lo+hi)/2; // mid point if (hi <= lo) return; mergesort(a, lo, mid); mergesort(a, mid+1, hi); merge(a, lo, mid, hi); } void merge(Item a[], int lo, int mid, int hi) { int i, j, k, nitems = hi-lo+1; Item *tmp = malloc(nitems*sizeof(Item)); i = lo; j = mid+1; k = 0; // scan both segments, copying to tmp while (i <= mid && j <= hi) { if (less(a[i],a[j])) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } // copy items from unfinished segment while (i <= mid) tmp[k++] = a[i++]; while (j <= hi) tmp[k++] = a[j++]; //copy tmp back to main array for (i = lo, k = 0; i <= hi; i++, k++) a[i] = tmp[k]; free(tmp); }
Binary search in array:
// search for key k in array a[]
// - returns index of location for k
// - doesn't indicate whether key is actually there or not
int findInArray(Key k, Item a[], int lo, int hi)
{
if (hi <= lo) return lo;
int mid = (hi+lo)/2;
int diff = cmp(k, key(a[mid]));
if (diff < 0)
return findInArray(k, a, lo, mid);
else if (diff > 0)
return findInArray(k, a, mid+1, hi);
else
return mid;
}
BST Interface:
typedef struct Node *Tree; // create an empty Tree Tree newTree(); // free memory associated with Tree void dropTree(Tree); // display a Tree (sideways) void showTree(Tree); // insert a new item into a Tree Tree TreeInsert(Tree, Item); // delete item with given key from Tree Tree TreeDelete(Tree, Key); // check whether item with given key is in Tree int TreeFind(Tree, Key); // compute depth of Tree int TreeDepth(Tree); // count #nodes in Tree int TreeNumNodes(Tree);
BST Implementation:
typedef struct Node *Link; typedef struct Node { Item value; Link left, right; } Node; // make a new node containing an Item static Link newNode(Item it) { Link new = malloc(sizeof(Node)); assert(new != NULL); new->value = it; new->left = new->right = NULL; return new; } // create a new empty Tree Tree newTree() { return NULL; } // free memory associated with Tree void dropTree(Tree t) { if (t == NULL) return; dropTree(t->left); dropTree(t->right); free(t); } // display a Tree (sideways) void showTree(Tree t) { void doShowTree(Tree); doShowTree(t); } // insert a new value into a Tree Tree TreeInsert(Tree t, Item it) { if (t == NULL) return newNode(it); int diff = cmp(key(it),key(t->value)); if (diff == 0) t->value = it; else if (diff < 0) t->left = TreeInsert(t->left, it); else if (diff > 0) t->right = TreeInsert(t->right, it); return t; } // insert a new value as root of Tree Tree insertAtRoot(Tree t, Item it) { if (t == NULL) return newNode(it); int diff = cmp(key(it), key(t->value)); if (diff == 0) t->value = it; else if (diff < 0) { t->left = insertAtRoot(t->left, it); printf("rotateR(%d)\n",t->value); t = rotateR(t); } else if (diff > 0) { t->right = insertAtRoot(t->right, it); printf("rotateL(%d)\n",t->value); t = rotateL(t); } return t; } // delete item with given key from Tree Tree TreeDelete(Tree t, Key k) { Tree deleteRoot(Tree); if (t == NULL) return NULL; int diff = cmp(k,key(t->value)); if (diff == 0) t = deleteRoot(t); else if (diff < 0) t->left = TreeDelete(t->left, k); else if (diff > 0) t->right = TreeDelete(t->right, k); return t; } // delete root of tree Tree deleteRoot(Tree t) { Link newRoot; // if no subtrees, tree empty after delete if (t->left == NULL && t->right == NULL) { free(t); return NULL; } // if only right subtree, make it the new root else if (t->left == NULL && t->right != NULL) { newRoot = t->right; free(t); return newRoot; } // if only left subtree, make it the new root else if (t->left != NULL && t->right == NULL) { newRoot = t->left; free(t); return newRoot; } // else (t->left != NULL && t->right != NULL) // so has two subtrees // - find inorder successor (grab value) // - delete inorder successor node // - move its value to root Link parent = t; Link succ = t->right; // not null! while (succ->left != NULL) { parent = succ; succ = succ->left; } int succVal = succ->value; t = TreeDelete(t,succVal); t->value = succVal; return t; } // check whether item with given key is in Tree int TreeFind(Tree t, Key k) { if (t == NULL) return 0; int res, diff = cmp(k,key(t->value)); if (diff < 0) res = TreeFind(t->left, k); else if (diff > 0) res = TreeFind(t->right, k); else // (diff == 0) res = 1; return res; } // compute depth of Tree int TreeDepth(Tree t) { if (t == NULL) return 0; else { int ldepth = TreeDepth(t->left); int rdepth = TreeDepth(t->right); //return 1 + (ldepth > rdepth)?ldepth:rdepth; if (ldepth > rdepth) return 1+ldepth; else return 1+rdepth; } } // count #nodes in Tree int TreeNumNodes(Tree t) { if (t == NULL) return 0; return 1 + TreeNumNodes(t->left) + TreeNumNodes(t->right); }
typedef struct node * link; struct treeImp{ link root; }; struct node{ Item item; link left; link right; int size; //Keeps track of the number of nodes in each sub-tree }; static link emptyTree = NULL; static link NEW (Item item, link l, link r, int size){ link newLink = malloc (sizeof *newLink); newLink->item = item; newLink->left = l; newLink->right = r; newLink->size = size; return newLink; } //Initialises a tree //In this implementation, a tree is not just a pointer to the root node //but is a struct which contains a pointer to the root node. Tree TREEinit(int balanceStrategy){ Tree t = malloc(sizeof(struct treeImp)); assert(t!= NULL); if(emptyTree == NULL){ emptyTree = NEW(NULLitem,NULL,NULL,0); } t->root = emptyTree; srand(time(NULL)); //seed random number generator for insertRandom return t; } //returns the size of the tree int TREEcount(Tree tree){ if(tree->root == NULL) return 0; return tree->root->size; } void TREEdestroy(Tree t){ assert(t != NULL); destroyNodes(t->root); free(emptyTree); free(t); } // A recursive version of standard BST insertion // Modified to update the size counters // inserts duplicates link insert (link currentLink, Item item) { if (currentLink == emptyTree) { return (NEW (item, emptyTree, emptyTree, 1)); } if (less (key (item), key (currentLink->item))) { currentLink->left = insert (currentLink->left, item); } else { currentLink->right = insert (currentLink->right, item); } currentLink->size++; return (currentLink); } // A recursive function that inserts the new item // at the root of the tree. This is used in randomInsert link insertAtRoot(link currentLink, Item item){ if(currentLink == emptyTree){ return (NEW(item,emptyTree,emptyTree,1)); } //size gets updated by the rotate functions if (less (key (item), key (currentLink->item))) { currentLink->left = insertAtRoot (currentLink->left, item); currentLink = rotRight(currentLink); } else { currentLink->right = insertAtRoot (currentLink->right, item); currentLink = rotLeft(currentLink); } return (currentLink); } // Randomly inserts either at the leaf of the tree or the root link insertRandom(link currentLink, Item item){ if (currentLink == emptyTree) { return (NEW (item, emptyTree, emptyTree, 1)); } //Prob 1/N if(rand() < RAND_MAX/(currentLink->size+1)){ return insertAtRoot(currentLink,item); } else if (less (key (item), key (currentLink->item))) { currentLink->left = insertRandom (currentLink->left, item); } else { currentLink->right = insertRandom (currentLink->right, item); } currentLink->size++; return (currentLink); } // Performs a standard recursive search for the key in the given tree // returns 1 if found and 0 otherwise int searchR(link t, Key k){ int returnVal; if (t == NULL || t == emptyTree){ returnVal = 0; }else if (less(k,t->item)){ returnVal = searchR(t->left, k); }else if (greater(k,t->item)){ returnVal = searchR(t->right, k); }else{ returnVal = 1; } return returnVal; } static link rotLeft (link currentTree) { if(currentTree == NULL || currentTree == emptyTree || currentTree->right == emptyTree){ return currentTree; } link rotLTree = currentTree->right; currentTree->right = rotLTree->left; rotLTree->left = currentTree; rotLTree->left->size = rotLTree->left->left->size + rotLTree->left->right->size +1; rotLTree->size = rotLTree->left->size + rotLTree->right->size + 1; return rotLTree; } static link rotRight (link currentTree) { if(currentTree == NULL || currentTree == emptyTree || currentTree->left == emptyTree){ return currentTree; } link rotRTree = currentTree->left; currentTree->left = rotRTree->right; rotRTree->right = currentTree; rotRTree->right->size = rotRTree->right->left->size + rotRTree->right->right->size + 1; rotRTree->size = rotRTree->right->size+ rotRTree->left->size+1; return rotRTree; } // partition tree at node with position pos (counting from 0) in the // sorted sequence of all items, node become new root node. link partitionR (link currentTree, int pos) { if(currentTree == NULL || currentTree == emptyTree) return currentTree; int leftSubtreeSize = currentTree->left->size; if (leftSubtreeSize > pos) { currentTree->left = partitionR (currentTree->left, pos); currentTree = rotRight (currentTree) ; } else if (leftSubtreeSize < pos) { currentTree->right = partitionR (currentTree->right, pos - 1 - leftSubtreeSize); currentTree = rotLeft (currentTree) ; } return currentTree; } link balance(link tree){ if(tree->size >=2){ tree = partitionR(tree,tree->size/2); tree->left = balance(tree->left); tree->right = balance(tree->right); } return tree; } link insertSplay (link tree, Item item) { Key v = key (item); if (tree == emptyTree) return (NEW (item, emptyTree, emptyTree, 1)); if (less (v, key(tree->item))) { if (tree->left == emptyTree) { return (NEW (item, emptyTree, tree, tree->size+1)); } if (less (v, key (tree->left->item))) { tree->left->left = insertSplay (tree->left->left, item); tree = rotRight (tree); } else { tree->left->right = insertSplay (tree->left->right, item); tree->left = rotLeft (tree->left); } return rotRight (tree); } else { if (tree->right == emptyTree) { return (NEW (item, tree, emptyTree, tree->size+1)); } if (less (key (tree->right->item), v)) { tree->right->right = insertSplay (tree->right->right, item); tree = rotLeft (tree); } else { tree->right->left = insertSplay (tree->right->left, item); tree->right = rotRight (tree->right); } return rotLeft (tree); } } //The function should perform rotations on all //items in the search path in a similar way to that of //splay tree insertion - except no node is actually inserted //The node that contains the key //should be rotated up and returned as the root of the tree //and *found should be set to 1 //If the key was not found, the last node on the search //path should be rotated up to the root of the tree //and found should be set to 0 //returns the new root of the tree //sets the value of *found to 0 or 1 link searchSplay (link n, Key k, int * found){ link returnVal = emptyTree; if (n == emptyTree) { // item not found *found = 0; returnVal = n; }else if (eq(key(n->item),k)) { *found = 1; // item found, store true returnVal = n; } else if (less (k, key (n->item))) { if (n->left == emptyTree){ *found = 0;// item not found //returnVal = rotateRight(n); returnVal = n; }else if(eq(key(n->left->item),k)){ *found = 1; returnVal = rotRight(n); }else{ if (less (k, key(n->left->item))) { /* left-left */ n->left->left = searchSplay (n->left->left, k, found); n = rotRight (n); } else { /* left-right */ n->left->right = searchSplay (n->left->right, k, found); n->left = rotLeft (n->left); } returnVal = rotRight (n); } } else { //printf("At node %s\n",n->item); if (n->right == emptyTree){ *found = 0;// item not found //returnVal = rotateLeft(n); returnVal = n; }else if(eq(key(n->right->item),k)){ *found = 1; returnVal = rotLeft(n); } else{ if (less (key(n->right->item), k)) { /* right-right */ n->right->right = searchSplay (n->right->right, k, found); n = rotLeft (n); } else { /* right-left */ n->right->left = searchSplay (n->right->left, k, found); n->right = rotRight (n->right); } returnVal = rotLeft (n); } } return returnVal; } static void destroyNodes(link n){ if( n != emptyTree){ destroyNodes(n->left); destroyNodes(n->right); free(n->item); free(n); } }
Hash table Interface:
typedef struct HashTabRep *HashTable; // create an empty HashTable HashTable newHashTable(int); // free memory associated with HashTable void dropHashTable(HashTable); // insert a new value into a HashTable void hashTableInsert(HashTable, Item); // delete a value from a HashTable void hashTableDelete(HashTable, Key); // get Item from HashTable using Key Item *hashTableSearch(HashTable, Key);
Hash Table Implementation: (separate chains)
#include "List.h" // use Lists of Items typedef struct HashTabRep { List *lists; // lists of Items int nslots; // # elements in array int nitems; // # items stored in HashTable } HashTabRep; // convert key to index static int hash(Key k, int N) { int h = ... convert key to int return h % N; } // create an empty HashTable HashTable newHashTable(int N) { HashTable new = malloc(sizeof(HashTable)); assert(new != NULL); new->lists = malloc(N*sizeof(List)); assert(new->items != NULL); int i; for (i = 0; i < N; i++) new->lists[i] = newList(); new->nslots = N; new->nitems = 0; return new; } // free memory associated with HashTable void dropHashTable(HashTable ht) { free(ht->lists); free(ht); } // insert a new value into a HashTable void hashTableInsert(HashTable ht, Item it) { Key k = key(it); int i = hash(k, ht->nslots); ListInsert(ht->lists[i], it); } // delete a value from a HashTable void hashTableDelete(HashTable ht, Key k) { int i = hash(k, ht->nslots); ListDelete(ht->lists[i], k); } // get Item from HashTable using Key Item *hashTableSearch(HashTable ht, Key k) { int i = hash(k, ht->nslots); return ListSearch(ht->lists[i], k); }
Hash Table Implementation: (linear probing)
#include "List.h" // use Lists of Items typedef struct HashTabRep { Item *items; // lists of Items int nslots; // # elements in array int nitems; // # items stored in HashTable } HashTabRep; // convert key to index static int hash(Key k, int N) { int h = ... convert key to int return h % N; } // create an empty HashTable HashTable newHashTable(int N) { HashTabRep *new = malloc(sizeof(HashTabRep)); assert(new != NULL); new->items = malloc(N*sizeof(Item)); assert(new->items != NULL); int i; for (i = 0; i < N; i++) new->items[i] = NoItem; new->nslots = N; new->nitems = 0; return new; } // free memory associated with HashTable void dropHashTable(HashTable ht) { free(ht->items); free(ht); } // insert a new value into a HashTable void hashTableInsert(HashTable ht, Item it) { int N = ht->nslots; Item *data = ht->items; Key k = key(it); int ix, j, i = hash(k,N); for (j = 0; j < N; j++) { ix = (i+j)%N; if (cmp(k,key(data[ix]) == 0) break; else if (data[ix] == NoItem) break; } if (j < N) { data[ix] = it; ht->nitems++; } } // delete a value from a HashTable void hashTableDelete(HashTable ht, Key k) { int N = ht->nslots; Item *data = ht->items; int j, i = hash(k,N); for (j = 0; j < N; j++) { int ix = (i+j)%N; if (cmp(k,key(data[ix]) == 0) break; else if (data[ix] == NoItem) return; // k not in table } data[ix] = NoItem; ht->nitems--; // clean up probe path j = ix+1; while (data[j] != NoItem) { Item it = data[j]; data[j] = NoItem; ht->nitems--; insert(ht, it); j = (j+1)%N); } } // get Item from HashTable using Key Item *hashTableSearch(HashTable ht, Key k) { int N = ht->nslots; Item *data = ht->items; int j, i = hash(k,N); for (j = 0; j < N; j++) { int ix = (i+j)%N; if (cmp(k,key(data[ix]) == 0) return &(data[ix]); } return NULL; }
Graph Interface:
// visible data structures for Graphs typedef struct GraphRep *Graph; // vertices denoted by integers 0..N-1 typedef int Vertex; // edges are pairs of vertices (end-points) typedef struct { Vertex v; Vertex w; } Edge; // auxiliary operations on graphs int validV(Graph,Vertex); // validity check Edge mkEdge(Graph, Vertex, Vertex); // edge creation int neighbours(Graph, Vertex, Vertex); // edge existence // core operations on graphs // make new graph with nV vertices Graph newGraph(int nV); // free memory allocated to graph void dropGraph(Graph); // show "printable" representation of graph void showGraph(Graph); // add new edge to a graph void insertE(Graph, Edge); // remove an edge from a graph void removeE(Graph, Edge); // returns #vertices & array of edges int edges(Graph, Edge *, int);
Implementation of Auxiliary Operations:
// is a vertex valid in a given Graph? static int validV(Graph g, Vertex v) { return (g != NULL && v >= 0 && v < g->nV); } // make an Edge value Edge mkEdge(Graph g, Vertex v, Vertex w) { assert(validV(g,v) && validV(g,w)); Edge e = {v,w}; // struct assignment return e; }
Adjacency Matrix Representation:
typedef struct GraphRep { int nV; // #vertices int nE; // #edges Bool **edges; // matrix of booleans } GraphRep; // check whether two vertices are connected int neighbours(Graph g, Vertex v, Vertex w) { assert(validV(g,v) && validV(g,w)); return g->edges[v][w]; } // make new graph with nV vertices Graph newGraph(int nV) { assert(nV >= 0); int i, j; int **e = malloc(nV * sizeof(int *)); assert(e != NULL); for (i = 0; i < nV; i++) { e[i] = malloc(nV * sizeof(int)); assert(e[i] != NULL); for (j = 0; j < nV; j++) e[i][j] = FALSE; } Graph g = malloc(sizeof(GraphRep)); assert(g != NULL); g->nV = nV; g->nE = 0; g->edges = e; return g; } // free memory allocated to graph void dropGraph(Graph g) { assert(g != NULL); int i; for (i = 0; i < g->nV; i++) free(g->edges[i]); free(g->edges); free(g); } // show "printable" representation of graph void showGraph(Graph g) { assert(g != NULL); printf("V=%d, E=%d\n", g->nV, g->nE); int i, j; for (i = 0; i < g->nV; i++) { int nshown = 0; for (j = i+1; j < g->nV; j++) { if (g->edges[i][j] != 0) { printf("%d-%d ",i,j); nshown++; } } if (nshown > 0) printf("\n"); } } // add new edge to a graph void insertE(Graph g, Edge e) { assert(g != NULL); assert(validV(g,e.v) && validV(g,e.w)); if (g->edges[e.v][e.w]) return; g->edges[e.v][e.w] = 1; g->edges[e.w][e.v] = 1; g->nE++; } // remove an edge from a graph void removeE(Graph g, Edge e) { assert(g != NULL); assert(validV(g,e.v) && validV(g,e.w)); if (!g->edges[e.v][e.w]) return; g->edges[e.v][e.w] = 0; g->edges[e.w][e.v] = 0; g->nE--; } // returns #vertices & array of edges int edges(Graph g, Edge *es, int nE) { assert(g != NULL && es != NULL); assert(nE >= g->nE); int i, j, n = 0; for (i = 0; i < g->nV; i++) { for (j = i+1; j < g->nV; j++) { if (g->edges[i][j] != 0) { assert(n < nE); es[n++] = mkEdge(g,i,j); } } } return n; }
Adjacency List Representation:
typedef struct vNode *VList; struct vNode { Vertex v; vList next; }; typedef struct graphRep GraphRep; struct graphRep { int nV; // #vertices int nE; // #edges VList *edges; // array of lists }; // check whether two vertices are connected int neighbours(Graph g, Vertex v, Vertex w) { assert(validV(g,v) && validV(g,w)); VList curr; curr = g->edges[v]; while (curr != NULL) { if (curr->v == w) return 1; } return 0; } // make new graph with nV vertices Graph newGraph(int nV) { int i, j; VList *e = malloc(nV * sizeof(VList)); assert(e != NULL); for (i = 0; i < nV; i++) e[i] = NULL; Graph g = malloc(sizeof(GraphRep)); assert(g != NULL); g->nV = nV; g->nE = 0; g->edges = e; return g; } // free memory allocated to graph void dropGraph(Graph g) { assert(g != NULL); int i; for (i = 0; i < g->nV; i++) freeVList(g->edges[i]); free(g); } // show "printable" representation of graph void showGraph(Graph) { assert(g != NULL); printf("V=%d, E=%d\n", g->nV, g->nE); int i; for (i = 0; i < g->nV; i++) { vNode *n = g->edges[i]; while (n != NULL) { printf("%d-%d ",i,n->v); n = n->next; } if (g->edges[i] != NULL) printf("\n"); } } // add new edge to a graph void insertE(Graph g, Edge e) { assert(g != NULL); assert(validV(g,e.v) && validV(g,e.w)); int orig = length(g->edges[e.v]); g->edges[e.v] = insertVList(g->edges[e.v], e.w); g->edges[e.w] = insertVList(g->edges[e.w], e.v); if (length(g->edges[e.v]) > orig) g->nE++; } // remove an edge from a graph void removeE(Graph g, Edge e) { assert(g != NULL); assert(validV(g,e.v) && validV(g,e.w)); int orig = length(g->edges[e.v]); g->edges[e.v] = deleteVList(g->edges[e.v], e.w); g->edges[e.w] = deleteVList(g->edges[e.w], e.v); if (length(g->edges[e.v]) < orig) g->nE--; } // returns #vertices & array of edges int edges(Graph g, Edge *es, int nE) { VList curr; assert(g != NULL && es != NULL); assert(nE >= g->nE); int w, n = 0; for (w = 0; w < g->nV; w++) { curr = g->edges[w]; while (curr != NULL) { if (w < curr->v) es[n++] = mkEdge(g,w,curr->v); curr = curr->next; } } return n; }
Path Checking:
int count; int *pre; // array of booleans // indexed by vertex 0..V-1 Vertex *st; // array of Vertices // indexed by vertex 0..V-1 // DFS : depth-first search int hasPath(Graph g, Vertex src, Vertex dest) { int i; count = 0; pre = malloc(g->nV*sizeof(int)); for (i = 0; i < g->nV; i++) pre[i] = -1; int result = dfsPathCheck(g, src, dest); free(pre); return result; } int dfsPathCheck(Graph g, Vertex v, Vertex dest) { pre[v] = count++; Vertex w; for (w = 0; w < g->nV; w++) { if (g->edges[v][w] && w == dest) return 1; // found path if (g->edges[v][w] && pre[w] == -1) return dfsPathCheck(g, w); } return 0; // no path from src to dest } // BFS : breadth-first search int hasPath(Graph g, Vertex src, Vertex dest) { count = 0; pre = malloc(g->nV*sizeof(int)); for (i = 0; i < g->nV; i++) pre[i] = -1; Queue q = newQueue(); QueueJoin(q,src); int isFound = 0; while (!QueueIsEmpty(q) && !isFound) { Vertex y, x = QueueLeave(q); if (pre[x] != -1) continue; for (y = 0; y < g->nV; y++) { if (!g->edges[x][y]) continue; if (y == dest) { isFound = 1; break; } if (pre[y] == -1) { QueueJoin(q,y); } } } dropQueue(q); free(pre); return isFound; }
Find and Display Shortest Path:
int findPath(Graph g, Vertex src, Vertex dest) { count = 0; int i; // array of "been visited" flags pre = malloc(g->nV * sizeof(int)); for (i = 0; i < g->nV; i++) pre[i] = -1; // array of path predecessor vertices (they form a spanning tree) Vertex *st= malloc(g->nV * sizeof(Vertex)); for (i = 0; i < g->nV; i++) st[i] = -1; Queue q = newQueue(); QueueJoin(q, src); visited[src] = count++; int isFound = 0; while (!emptyQ(q) && !isFound) { Vertex y, x = QueueLeave(q); for (y = 0; y < g->nV; y++) { if (!g->edges[x][y]) continue; st[y] = x; if (y == dest) { isFound = 1; break; } if (pre[y] == -1) { QueueJoin(q, y); pre[y] = count++; } } } if (isFound) { // display path in dest..src order Vertex v; for (v = dest; v != src; v = st[v]) printf("%d<-", v); printf("%d\n", src); } free(st); free(pew); dropQueue(q); }
Graph Interface:
// visible data structures for Graphs typedef struct GraphRep *Graph; // vertices denoted by integers 0..N-1 typedef int Vertex; // edges are end-points + weight typedef struct { Vertex src; Vertex dest; float weight; } Edge; // auxiliary operations on graphs int validV(Graph,Vertex); // validity check Edge mkEdge(Graph, Vertex, Vertex, float); // edge creation int neighbours(Graph, Vertex, Vertex); // edge existence float compareE(Edge e1, Edge e2); // compare edge weights // core operations on graphs // make new graph with nV vertices Graph newGraph(int nV); // free memory allocated to graph void dropGraph(Graph); // show "printable" representation of graph void showGraph(Graph); // add new edge to a graph void insertE(Graph, Edge); // remove an edge from a graph void removeE(Graph, Edge); // returns #vertices & array of edges int edges(Graph, Edge *, int);
Implementation of Auxiliary Operations:
// is a vertex valid in a given Graph? static int validV(Graph g, Vertex v) { return (g != NULL && v >= 0 && v < g->nV); } // make an Edge value Edge mkEdge(Graph g, Vertex v, Vertex w) { assert(validV(g,v) && validV(g,w)); Edge new; new.src = src; new.dest = dest; new.weight = weight; return new; } // compare Edge weights int compareE(Edge e1, Edge e2) { return e1.weight - e2.weight; }
Adjacency Matrix Representation:
// since 0 is a valid weight, can't use it for "no edge" // need a distinguished value to indicate "no edge" #define NO_EDGE MAXFLOAT // imaginary distinguished float value typedef struct GraphRep { int nV; // #vertices int nE; // #edges Bool **edges; // matrix of booleans } GraphRep; // check whether two vertices are connected int neighbours(Graph g, Vertex v, Vertex w) { assert(validV(g,v) && validV(g,w)); return (g->edges[v][w] != NO_EDGE); } // make new graph with nV vertices Graph newGraph(int nV) { assert(nV >= 0); int i, j; float **e = malloc(nV * sizeof(float *)); assert(e != NULL); for (i = 0; i < nV; i++) { e[i] = malloc(nV * sizeof(float)); assert(e[i] != NULL); for (j = 0; j < nV; j++) e[i][j] = NO_EDGE; } Graph g = malloc(sizeof(GraphRep)); assert(g != NULL); g->nV = nV; g->nE = 0; g->edges = e; return g; } // free memory allocated to graph void dropGraph(Graph g) { assert(g != NULL); int i; for (i = 0; i < g->nV; i++) free(g->edges[i]); free(g->edges); free(g); } // show "printable" representation of graph void showGraph(Graph g) { assert(g != NULL); printf("V=%d, E=%d\n", g->nV, g->nE); int i, j; for (i = 0; i < g->nV; i++) { int nshown = 0; for (j = i+1; j < g->nV; j++) { float wt = g->edges[i][j]; if (wt != NO_EDGE) { printf("%d-%0.1f-%d ",i,wt,j); nshown++; } } if (nshown > 0) printf("\n"); } } // add new edge to a graph void insertE(Graph g, Edge e) { assert(g != NULL); Vertex v = e.src, w = e.dest; assert(validV(g,v) && validV(g,w)); if (G->edges[v][w] == NO_EDGE) g->nE++; g->edges[v][w] = e.weight; } // remove an edge from a graph void removeE(Graph g, Edge e) { assert(g != NULL); Vertex v = e.src, w = e.dest; assert(validV(g,v) && validV(g,w)); if (g->edges[v][w] == NO_EDGE) return; g->edges[v][w] = NO_EDGE; g->edges[w][v] = NO_EDGE; g->nE--; } // returns #vertices & array of edges int edges(Graph g, Edge *es, int nE) { assert(g != NULL && es != NULL); assert(nE >= g->nE); int i, j, n = 0; for (i = 0; i < g->nV; i++) { for (j = i+1; j < g->nV; j++) { if (g->edges[i][j] != NO_EDGE) { assert(n < nE); es[n++] = mkEdge(g,i,j); } } } return n; }
Minimum Spanning Tree (Kruskal):
typedef Graph MSTree; // an MST is a specialised Graph // assumes existence of list-of-edges ADT MSTree kruskalFindMST(Graph g) { Graph mst = newGraph(); //MST initially empty EdgeList eList; //sorted list of edges int i; Edge e; int eSize = sizeof(Edge); edges(eList, g->nE, g); eList = qsort(sorted, g->nE, eSize, compareE); for (i = 0; mst->nE < g->nV-1; i++) { e = eList[i]; insertE(mst, e); if (hasCycle(mst)) removeE(mst, e); } }
Minimum Spanning Tree (Prim):
void prim(Graph g, int st[], float dist[]){ Vertex v,i; PriQ pq = initPriQ(g->nV); int * visited = malloc(sizeof(int)*g->nV); for(v=0;v < g->nV;v++){ visited[v] = -1; st[v] = -1; dist[v] = NO_EDGE; //infinity insert(pq,newItem(dist[v],v)); } st[0] = 0; dist[0] = 0; increasePriority(pq,0,0); while(!isEmpty(pq)){ v = (delMin(pq))->value; visited[v] = 1; for(i=0;inV;i++){ if(g->adj[v][i] != NO_EDGE && visited[i] == -1){ if(g->adj[v][i] < dist[i]){ dist[i] = g->adj[v][i]; increasePriority(pq,i,dist[i]); st[i] = v; } } } } free(visited); }
Single-source Shortest Path (Dijkstra):
void dijkstra(Graph g,Vertex s,int st[],float dist[]){ int v,t; PriQ pq = initPriQ(g->nV); //insert each vertex into the pq for(v=0;v< g->nV;v++){ st[v] = -1; dist[v] = NO_EDGE; //represents infinity Item i = newItem(dist[v],v); insert(pq,i); } dist[s] = 0.0; //set start veretex dist to 0 increasePriority(pq,s,dist[s]); // update pq while(!isEmpty(pq)){ v = value(delMin(pq)); if(dist[v] != NO_EDGE) for(t = 0;t < g->nV;t++){ if(g->adj[v][t] != NO_EDGE){ if(dist[v] + g->adj[v][t] < dist[t]){ dist[t] = dist[v] + g->adj[v][t]; increasePriority(pq,t,dist[t]); st[t] = v; } } } } }