A graph is a data structure consisting of nodes (vertices) and edges that connect the vertices. A linked list and a tree are indeed special kinds of graphs with certain properties like hierarchy and a strict number of children, expressed using pointers. As graphs can flexibly represent any relationships (transportation, social networks, chemical structures, etc.), they hold tremendous significance. In this article, we will cover basic concepts and representations of graphs.

Types of Graphs

A graph can take many forms, and understanding the differences is important when representing graphs and building algorithms for working with them. A graph is a directed graph when its edges have direction, and it is an undirected graph when its edges do not have direction. For example, when all the edges are represented as pairs of pointers pointing to one another, the graph is undirected. A directed graph is cyclic when there is a cycle (e.g., a pair of vertices pointing to each other, a vertex pointing to itself, or three or more vertices forming a loop), and it is acyclic when there is no cycle.

When the edges in a graph have associated values, such as distance, time, or expected value, we call it a weighted graph. When the edges do not have associated values, the graph is unweighted. A null graph is a graph without any edges, while a graph is complete when all the vertices are connected to every other vertex. We refer to a graph with relatively few edges compared to vertices as sparse, and we call a graph with many edges dense. Given these explanations, try to identify the types of the graphs in the above visualization (This is Q1 of the exercise).

Adjacency Matrix

A graph can be represented in various ways, and one such way is using an adjacency matrix, where each value in the matrix represents the edge between the vertex in the row and the vertex in the column. For a weighted graph, we can include the weight as the value, while for an unweighted graph, we can use a binary value (0 or 1) to indicate the existence of an edge. Querying an edge takes $O(1)$ time, as we only need to access matrix[i][j] to check for an edge from the $i$th vertex to the $j$th vertex.

class AdjacencyMatrix {
    public:
        vector<vector<int>> mat;
 
        void addEdge(int i, int j) {
            if (i < mat.size() && j < mat.size())
            {
                mat[i][j] = 1;
                mat[j][i] = 1;
            }
            else
            {
                cout << "Error: Invalid vertex index." << endl;
            }
        };
 
        void display() {
            for (const auto &row : mat)
            {
                for (int val : row)
                {
                    cout << val << " ";
                }
                cout << endl;
            }
        };
 
    AdjacencyMatrix(int size) {
        mat.resize(size, vector<int>(size, 0));
    };
};

However, adjacency matrices can be memory-intensive, especially for sparse undirected graphs, resulting in a sparse and symmetric matrix. In fact, the space complexity of an adjacency matrix is $O(V^2)$, where $V$ is the number of vertices.

Adjacency List

An alternative way of representing a graph is the adjacency list, which is an array of linked lists where each element corresponds an edge connecting a vertex another vertex.
The space complexity of the adjacency list is $O(V + E)$, where $V$ is the number of vertices, and $E$ is the number of edges. Unless the graph is complete, an adjacency list is always more memory-efficient than an adjacency matrix. However, to check if there is an edge from vertex $i$ to vertex $j$, we need to access the $i$-th index of the array and traverse the linked list to find $j$, which takes $O(E)$.

class AdjacencyList {
    public:
        vector<list<int> > li;
 
        void addEdge(int i, int j) {
            li[i].push_back(j);
            li[j].push_back(i);
        };
 
        void display() {
            for (int i = 0; i < li.size(); i++) {
                cout << i << ": ";
                for (int j : li[i]) {
                    cout << j << " ";
                }
                cout << endl; 
            }
        };
 
    AdjacencyList(int size) {
        li.resize(size);
    };
};

Adding a new vertex is faster with an adjacency list than with an adjacency matrix, as the latter requires creating a new matrix of size $(V+1)^2$ ($O(V^2)$), while the former only requires adding a new element to the array ($O(1)$). Therefore, when memory is abundant, the number of vertices is relatively fixed, and querying edges is more frequent, an adjacency matrix is preferred. Conversely, when memory is limited and the graph structure changes frequently, an adjacency list is the better choice.

Conclusion

In this article, we covered the various types of graphs and their representations. Graph theory is highly relevant in fields like reinforcement learning and graph machine learning, so I might explore it further in a new article series. In the next article, we will discuss how to traverse graphs to perform searches.

Exercises

From this article, there will be an exercise section where you can test your understanding of the material introduced in the article. I highly recommend solving these questions by yourself after reading the main part of the article. You can click on each question to see its answer.

Resources

• GeeksforGeeks. 2024. Graph and its representations. GeeksforGeeks.