Graphs As a Data Structure
Graphs are an Abstract Data Type used to organize information and more importantly, how information is related such as the names of Cities and the roads that connect them, or individual people and their various relationships on a social network. Graphs are powerful, and being able to create, use, and manipulate them is of extreme importance in all manner of fields of study and business. Therefore, developing efficient data structures and algorithms to process them is also of the utmost importance. I’ve previously covered representing graphs using the C++ Standard Template Library. In this article i will cover a way to efficiently represent graphs as an adjacency list in C.
Graph vocabulary
To facilitate the explanation of graph terms i will use the aforementioned example of a road map. The two components of a graph are vertexes and edges. A vertex is a fundamental unit of information in a graph. For example each city on a map would be represented in our graph by a vertex. An edge on the other hand, is the relationship which connects vertexes to other vertexes. Edges can be directed or undirected, and may be associated with a weight or a cost. Two nodes which are connected by an edge are considered to be adjacent or neighbors. A graph whose vertexes are connected to every other vertex is called a complete graph. If a graph has few vertexes it is called sparse. Conversely if there are many vertexes it is referred to as dense. All of these things should be taken into consideration when choosing how to implement a graph as a data structure.
Handling Objects in C without OOP
C does not have the benefit of having a container collection like the C++ STL, nor does it have the class object system which enables object oriented programming languages to more easily create and use more advanced data structures. This does not make C inferior, it makes it different.
Its important to remember that while C is not an OOP language, it IS a procedural language, and OOP as applied in C++ is an outgrowth of the procedural programming style used in C to give code more structure. In short: C has the capability to get the job done. If you can do it in C++, there is a way to do it in C. Being able to adapt and shift paradigms makes one a more versatile programmer.
Graph Representation with Adjacency Lists
A popular way to represent graph data is as an Adjacency List. An adjacency list is a list of edges that each vertex posses. Each vertex in the graph has its on adjacency list, and this collection of lists is used to represent the graph as a whole. For our purposes, we will be using an Array of Linked Lists to implement our Graph ADT. to do this in an efficient manner we will use C’s struct system.
Since we are using an Adjacency List representation, we will need a linked list node type:
typedef struct node {
char label;
struct node *next;
} node;
First lets define our Graph struct:
typedef struct {
char *name; /* the name of our Graph */
int V; /* the number of vertexes in the Graph */
struct node *adj[]; /* Our Adjacency list, a list of lists */
} Graph;
A function to initialize our graph must be provided with the number of Vertexes we will be adding to our graph in order to initialize the our adjacency list:
Graph* newGraph(int N)
{
Graph* n = malloc(sizeof(Graph)); /* allocate space on the heap */
n->V = N; /* assign the number of vertexes */
for (int i = 0; i <= n->V; i++) /* initialize an adjacency list for each vertex */
{
n->adj[i] = malloc(sizeof(node));
n->adj[i]->next = NULL;
}
return n;
}
Because we are using arrays, for simplicity we will be using single char’s as vertex labels, which require us to have a way to convert vertex labels to array indexes and vice versa:
int index(char k)
{
return k- 'A' + 1;
}
char name(int k)
{
return k + 'A' - 1;
}
These two functions work in such a way where as:
index(‘A’); will return 1, index(‘B’) will return 2, etc.
Conversely, name(1); will return ‘A’, name(2); will return ‘B’, and so on.
We now have everything we need to be able to start adding vertexes to our graph, the following function adds an undirected edge to our graph, simply put, it adds an entry for a vertexes neighbor to its adjacency list, and adds that vertexes label to its neighbors adjacency list, this is because in an undirected graph, a forward edge and backward edge are equal, but both edges need to be represented:
void addEdge(Graph **g, char from, char to)
{
node *f = malloc(sizeof(node)); /* allocate linked list nodes */
node *t = malloc(sizeof(node)); /* for both edges */
f->label = to; /* forward edge */
t->label = from; /* backward edge *?
f->next = (*g)->adj[index(from)]; /* add the forward edge to adj list */
(*g)->adj[index(from)] = f;
t->next = (*g)->adj[index(to)]; /* add backward edge to adj list *?
(*g)->adj[index(to)] = t;
}
We now have everything we need to construct the actual graph, but no way of visualizing it. The following function iterates over our array of adjacency lists, and iterates over each adjacency list displaying its contents:
void showGraph(Graph *g)
{
for (int i = 1; i <= g->V; i++)
{
printf("%c: ", name(i));
for (node *itr = g->adj[i]; itr != NULL; itr = itr->next)
printf("%c ", itr->label);
printf("\n");
}
}
Our Graph.h is now complete, now lets write a program to test it out:
#include <stdio.h>
#include <stdlib.h>
#include "Graph.h"
int main(int argc, char *argv[])
{
Graph* g = newGraph(5);
addEdge(&g, 'A', 'B');
addEdge(&g, 'A', 'C');
addEdge(&g, 'B', 'E');
addEdge(&g, 'B', 'D');
addEdge(&g, 'C', 'D');
addEdge(&g, 'D', 'E');
showGraph(g);
return 0;
}
Output:
A: C B
B: D E A
C: D A
D: E C B
E: D B
Voila, It works! We now have everything we need to be able to implement and work with graphs in C, or C++(without using the STL!)
In the next installment we’ll cover traversing our graph with breadth first search.
The full code for the examples covered in this article can be found on my github at:
https://github.com/maxgoren/DataStructures/tree/main/Graphing/C
