Understanding Graph Data Structure

Introduction

Graphs are versatile and powerful data structures used in computer science to model various real-world relationships. Whether it's social networks, roadmaps, or the internet, graphs provide an intuitive way to represent and analyze connections between different entities. In this comprehensive guide, we'll delve into the world of graphs, exploring their types, terminologies, and operations, with the help of visual examples to enhance understanding.

What is a Graph?

At its core, a graph consists of nodes (also known as vertices) and edges. Nodes represent entities, and edges represent relationships between these entities. If the edges have a specific direction, the graph is termed as a directed graph or digraph. If there is no direction, it's an undirected graph.

Types of Graphs

This section explores the diverse world of graphs. Connected graphs have a path between every pair of nodes, while disconnected graphs have isolated components. Weighted graphs assign weights to edges, representing the cost or distance between nodes. Cyclic graphs contain cycles (loops), whereas acyclic graphs do not.

Different methods can represent graphs in computers. An adjacency matrix uses a 2D array to represent edges between nodes. Adjacency lists use an array of lists or a hash table to store connected nodes efficiently. Incidence matrices are used mainly in network analysis and linear algebra.

Graph Traversal

Traversal algorithms are essential for navigating through graphs. DFS explores as far as possible along each branch before backtracking, while BFS explores neighbors before moving to the next level. Dijkstra's algorithm finds the shortest path between nodes in a weighted graph, and A* is an advanced algorithm used for pathfinding in games and robotics.

Common Graph Problems
This section covers various graph-related problems encountered in computer science. The shortest path problem aims to find the shortest path between two nodes. The minimum spanning tree problem seeks to connect all nodes with the minimum total edge weight. Topological sorting is crucial for scheduling tasks, and the traveling salesman problem challenges finding the shortest possible route that visits each city and returns to the original city.

Graph Implementation

Now Let’s see an example of Graph class'

// create a graph class
class Graph {
    // defining vertex array and
    // adjacent list
    constructor(noOfVertices)
    {
        this.noOfVertices = noOfVertices;
        this.AdjList = new Map();
    }

    // functions to be implemented

    // addVertex(v)
    // addEdge(v, w)
    // printGraph()

    // bfs(v)
    // dfs(v)
}

The above example shows a framework of Graph class. We define two private variables noOfVertices to store the number of vertices in the graph and AdjList, which stores an adjacency list of a particular vertex. We used a Map Object provided by ES6 in order to implement the Adjacency list. Where the key of a map holds a vertex and values hold an array of an adjacent node.

*Now let’s implement functions to perform basic operations on the graph: *

Adding vertexes

It adds the vertex v as key to adjList and initializes its values with an array.

// add vertex to the graph
addVertex(v)
{
    // initialize the adjacent list with a
    // null array
    this.AdjList.set(v, []);
}

Adding Edges

// add edge to the graph
addEdge(v, w)
{
    // get the list for vertex v and put the
    // vertex w denoting edge between v and w
    this.AdjList.get(v).push(w);

    // Since graph is undirected,
    // add an edge from w to v also
    this.AdjList.get(w).push(v);

In order to add edge, we get the adjacency list of the corresponding src vertex and add the dest to the adjacency list.

Conclusion

Graphs are fundamental in computer science, and their applications are vast and varied. Whether you're designing algorithms, analyzing social networks, or optimizing routes, a deep understanding of graphs is invaluable. This guide has provided a comprehensive overview, touching on various types, representations, traversal methods, and common problems. Armed with this knowledge, you're ready to tackle graph-related challenges with confidence. Happy graph traversing!

sources
https://www.geeksforgeeks.org/implementation-graph-javascript/
https://towardsdatascience.com/common-graph-theory-problems-ca990c6865f1
https://www.geeksforgeeks.org/graph-data-structure-and-algorithms/
https://www.geeksforgeeks.org/introduction-to-graphs-data-structure-and-algorithm-tutorials/