Basics of Graph Theory

Filed Under: C Programming
Graph Theory Basics

In this article, we’ll touch upon the graph theory basics. Graph Theory is a branch of mathematics that aims at studying problems related to a structure called a Graph.

In this article, we will try to understand the basics of Graph Theory, and also touch upon a C programmer’s perspective for representing such problems.


What is a Graph?

A Graph is a structure that consists of a set of nodes/vertices that map to a set of edges. How do they map together?

Well, the words themselves give you a hint. A node/vertex is a point on the graph, and edges join two vertices together, through a line segment. We represent an edge joining a pair of vertices by => edge = (u, v)

The below figure represents a Graph having 3 vertices and 2 edges. We don’t need to connect all the vertices together in a graph.

Basics of Graph Theory- Graphs
Graph Basics

Now that you know what a Graph is, let’s look at the types of Graphs.


Types of Graphs

The highest level of demarcation is based on the direction.

That is, there are two types of graphs based on this category: Undirected and Directed.

Undirected Graph

An undirected graph is a graph where every edge is represented as an unordered pair e = (1, 2). This means that the order doesn’t matter to us, since (1, 2) is the same as (2, 1).

All graphs which do not have an arrow between vertices are called Undirected Graphs.

Basics of Graph Theory - Undirected Graph
Undirected Graph

Directed Graph

A directed graph is a graph where every edge is directed (unidirectional). This means that the edges e1 = (1, 2) and e2 = (2, 1) are different.

They represent oppositely directed edges between 1 and 2.

We represent any connection by an arrow mark to show the direction of the edge.

Basics of Graph Theory - Directed Graph
Directed Graph

These are the two major types of Graphs, which themselves have different divisions. We will continue to cover this topic as we go along in the future.

Weighted Graphs

There is one more type of graph, called a Weighted Graph, which we use in a lot of problems.

This is simply any directed/undirected graph with each edge having a weight/cost associated with it.

Weighted Graph
Weighted Graph

Now that we know the basics of graphs, let us look at the implementation of these graphs in C.


Implementation of Graphs

There are two ways of implementing a graph.

  1. Adjacency Matrix
  2. Adjacency List

Using Adjacency Matrices

An Adjacency Matrix adj is a matrix where:

  • adj[i][j] = 1 if (i, j) has an edge connecting them
  • adj[i][j] = 0 otherwise

This has the advantage of an O(1) time complexity for searching and updating values, but has a space complexity of O(n^2).

For the directed graph below, let’s figure out the adjacency matrix.

Directed Graph 1
Directed Graph – Example

We denote the matrix to have the element adj[i][j] = 1 only if there is a directed edge from i to j.

Adjacency Matrix Graph
Adjacency Matrix Graph

Constructing the matrix is very simple, so let’s quickly look at an example in C. Here, we implement the adjacency matrix as a 2D-array.

The implementation is as below. Code is self-explanatory for anyone familiar with C programming and pointers.

/**
    Code for https://journaldev.com article
    Purpose: Adjacency Matrix representation of a Graph
    @author: Vijay Ramachandran
    @date: 10-02-2020
*/

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

typedef struct Graph Graph;

struct Graph {
    // Number of vertices
    int v;
    // Adjacency Matrix
    int** adj;
};

int** init_adjacency_matrix(Graph g) {
    // Initializes an adjacency matrix for the graph
    if (g.adj)
        return g.adj;
    // Allocates memory for the matrix
    // and sets every element to 0
    int** matrix = (int**) calloc (g.v, sizeof(int*));
    for (int i=0; i<g.v; i++) {
        matrix[i] = (int*) calloc (g.v, sizeof(int));
    }
    g.adj = matrix;
    printf("Initialized Adjacency Matrix!\n");
    return matrix;
}

void free_matrix(Graph g) {
    // Free the adjacency matrix
    if (!g.adj)
        return;
    for (int i=0; i<g.v; i++)
        free(g.adj[i]);
    free(g.adj);
}

void add_edge(Graph g, int i, int j) {
    // Adds an edge connecting two vertices i and j
    if (!g.adj) {
        fprintf(stderr, "Adjacency Matrix not initialized!\n");
        exit(1);
    }
    
    else if (i > g.v || j > g.v) {
        fprintf(stderr, "Invalid Vertex Number\n");
        exit(1);
    }
    g.adj[i-1][j-1] = 1;
}

void remove_edge(Graph g, int i, int j) {
    // Sets the edge from i to j as zero
    if (!g.adj) {
        fprintf(stderr, "Adjacency Matrix not initialized!\n");
        exit(1);
    }
    else if (i > g.v || j > g.v) {
        fprintf(stderr, "Invalid Vertex Number\n");
        exit(1);
    }

    g.adj[i-1][j-1] = 0;
}

int check_if_exists(Graph g, int i, int j) {
    // Checks if there is an edge from vertex i to j
    if (!g.adj) {
        fprintf(stderr, "Adjacency Matrix not initialized!\n");
        exit(1);
    }
    else if (i > g.v || j > g.v) {
        fprintf(stderr, "Invalid Vertex Number\n");
        return 0;
    }

    return g.adj[i-1][j-1];
}

int main() {
    // Graph with 4 vertices
    Graph g = {4, NULL};
    printf("Created a Graph Structure with %d vertices\n", g.v);
    g.adj = init_adjacency_matrix(g);

    // Let's connect the 4 vertices using 6 edges
    add_edge(g, 1, 2);
    add_edge(g, 2, 1);
    add_edge(g, 2, 3);
    add_edge(g, 2, 4);
    add_edge(g, 3, 1);
    add_edge(g, 4, 3);

    // Check if the edge is connected
    printf("Is there an edge from 1 to 2?\n");
    if (check_if_exists(g, 1, 2))
        printf("Yes\n");
    else
        printf("No\n");
    
    printf("Is there an edge from 4 to 3?\n");
    if (check_if_exists(g, 4, 3))
        printf("Yes\n");
    else
        printf("No\n");

    printf("Is there an edge from 1 to 3?\n");
    if (check_if_exists(g, 1, 3))
        printf("Yes\n");
    else
        printf("No\n");

    free_matrix(g);
    return 0;
}

Output

Created a Graph Structure with 4 vertices
Initialized Adjacency Matrix!
Is there an edge from 1 to 2?
Yes
Is there an edge from 4 to 3?
Yes
Is there an edge from 1 to 3?
No

The problem is that we always need to use O(n^2) elements for storage, and hence, we often use adjacency lists to represent graphs.

Using Adjacency Lists

An Adjacency List is a list that can be used to represent connected vertices.

The idea is to store a linked list for vertex, that consists of all vertices which are directly connected to it.

Adjacency List – Courtesy: KhanAcademy

We can implement this using an array of linked lists.

A simple implementation in C is given below.

/**
    Code for https://journaldev.com article
    Purpose: Adjacency List representation of a Graph
    @author: Vijay Ramachandran
    @date: 10-02-2020
*/

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

typedef struct Graph Graph;

typedef struct Node Node;

struct Node {
    // To represent the linked list node.
    // Contains the vertex index
    int vertex;
    // And a pointer to the next element in the linked list
    Node* next;
};

struct Graph {
    // Number of vertices
    int v;
    // Array of Adjacency Lists
    Node** adj_lists;
};

Node** init_adjacency_lists(Graph g) {
    // Initializes an adjacency matrix for the graph
    if (g.adj_lists)
        return g.adj_lists;
    // Allocates memory for the lists
    // There is a list for every vertex in the graph
    // which means there are g.v adjacent lists
    Node** adj_lists = (Node**) calloc (g.v,  sizeof(Node*));

    // Set them to NULL initially
    for (int i = 0; i < g.v; i++)
        adj_lists[i] = NULL;
    
    printf("Initialized Adjacency Lists!\n");
    return adj_lists;
}

void free_list(Node* list) {
    // Frees all nodes in the list, headed by 'list'
    Node* temp = list;
    while(temp) {
        Node* rm_node = temp;
        temp = rm_node->next;
        rm_node->next = NULL;
        free(rm_node);
    }
}

void free_adj_lists(Graph g) {
    // Free the adjacency matrix
    if (!g.adj_lists)
        return;
    for (int i=0; i<g.v; i++)
        free_list(g.adj_lists[i]);
    free(g.adj_lists);
}

void print_list(Node* list) {
    // Prints the linked list
    Node* temp = list;
    while(temp) {
        printf("Node: %d -> ", temp->vertex);
        temp = temp->next;
    }
    printf("\n");
}

Node* create_node(int vertex) {
    // Creates a LinkedList node to hold the vertex
    Node* node = (Node*) calloc (1, sizeof(Node));
    node->next = NULL;
    node->vertex = vertex;
    return node;
}

void add_edge(Graph g, int i, int j) {
    // Adds an edge connecting two vertices i and j
    if (!g.adj_lists) {
        fprintf(stderr, "Adjacency Lists not initialized!\n");
        exit(1);
    }
    
    else if (i > g.v || j > g.v) {
        fprintf(stderr, "Invalid Vertex Number\n");
        exit(1);
    }

    // Create the new node in the souce vertex
    // adjacency list and add the destination
    // vertex to it
    
    // Create a node containing the dst vertex index
    Node* node = create_node(j);

    // Insert at the source list
    // Let's insert at the top, since it doesn't
    // matter whether we insert at the head or not
    node->next = g.adj_lists[i-1];
    // Make the new node as the head
    g.adj_lists[i-1] = node;
}

void remove_edge(Graph g, int i, int j) {
    // Sets the edge from i to j as zero
    if (!g.adj_lists) {
        fprintf(stderr, "Adjacency Lists not initialized!\n");
        exit(1);
    }
    else if (i > g.v || j > g.v) {
        fprintf(stderr, "Invalid Vertex Number\n");
        exit(1);
    }

    // Search for vertex j in i's adjacency list
    Node* temp = g.adj_lists[i-1];
    if (!temp) {
        return;
    }
    if (!(temp->next)) {
        if (temp->vertex == j) {
            free(temp);
            g.adj_lists[i-1] = NULL;
        }
        return;
    }
    while (temp->next) {
        if (temp->vertex == j) {
            // We have found an edge! Remove this element.
            Node* rm_node = temp;
            temp->next = rm_node->next;
            rm_node->next = NULL;
            free(rm_node);
            return;
        }
        temp = temp->next;
    }
    // No element found :(
    return;
}

int check_if_exists(Graph g, int i, int j) {
    // Checks if there is an edge from vertex i to j
    if (!g.adj_lists) {
        fprintf(stderr, "Adjacency Lists not initialized!\n");
        exit(1);
    }
    else if (i > g.v || j > g.v) {
        fprintf(stderr, "Invalid Vertex Number\n");
        return 0;
    }
    
    // Search for vertex j in i's adjacency list
    Node* temp = g.adj_lists[i-1];
    if (!temp) {
        return 0;
    }
    if (!(temp->next)) {
        if (temp->vertex == j) {
            return 1;
        }
        return 0;
    }
    while (temp->next) {
        if (temp->vertex == j) {
            // We have found an edge! Remove this element.
            return 1;
        }
        temp = temp->next;
    }
    // No element found :(
    return 0;
}

int main() {
    // Graph with 4 vertices
    Graph g = {4, NULL};
    printf("Created a Graph Structure with %d vertices\n", g.v);
    g.adj_lists = init_adjacency_lists(g);

    // Let's connect the 4 vertices using edges
    add_edge(g, 1, 2);
    add_edge(g, 2, 1);
    add_edge(g, 2, 3);
    add_edge(g, 2, 4);
    add_edge(g, 3, 1);
    add_edge(g, 4, 3);

    // Check if the edge is connected
    printf("Is there an edge from 1 to 2?\n");
    if (check_if_exists(g, 1, 2))
        printf("Yes\n");
    else
        printf("No\n");
    
    printf("Is there an edge from 4 to 3?\n");
    if (check_if_exists(g, 4, 3))
        printf("Yes\n");
    else
        printf("No\n");

    printf("Is there an edge from 1 to 3?\n");
    if (check_if_exists(g, 1, 3))
        printf("Yes\n");
    else
        printf("No\n");

    printf("\nPrinting the Adjacency Lists for every Vertex:\n"); 
    for (int i=0; i<g.v; i++) {
        printf("Vertex: %d , ", i+1);
        print_list(g.adj_lists[i]);
    }
    free_adj_lists(g);
    return 0;
}

Output

Created a Graph Structure with 4 vertices
Initialized Adjacency Lists!
Is there an edge from 1 to 2?
Yes
Is there an edge from 4 to 3?
Yes
Is there an edge from 1 to 3?
No

Printing the Adjacency Lists for every Vertex:
Vertex: 1 , Node: 2 -> 
Vertex: 2 , Node: 4 -> Node: 3 -> Node: 1 -> 
Vertex: 3 , Node: 1 -> 
Vertex: 4 , Node: 3 -> 

Conclusion

With that, we have covered the basics of Graph Theory. In the upcoming articles, we will take a look at how we can solve different graph theory problems and their implementation in C.

In the meantime, do go through our latest C Programming articles, which cover differ aspects of C.

References


Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages