Graph Data Structure

A graph in computer science is a data structure that represents a set of objects along with the connections or relations between them. The objects are often referred to as nodes or vertices, and the connections are called edges or arcs. Graphs are a powerful way to model relationships and interactions within a system, enabling the representation of complex structures in an intuitive and flexible manner.

In the real world, graphs are used to represent and analyze a wide range of systems and relationships. For example, social networks can be modeled as graphs, where individuals are nodes and friendships are edges. Transportation networks, such as road systems or flight routes, can be represented as graphs to optimize routes and analyze traffic flow. In biology, graphs are used to model protein interactions or genetic networks. Even the internet itself can be viewed as a massive graph, with each webpage as a vertex and hyperlinks as edges to other webpages.

Structure of a Graph

A graph data structure is made up of multiple nodes (also called as vertices). Each node can store data of any object and can also store links/references to other objects it is connected to. We call the objects involved in the graph as “nodes” or “vertices” and the connections between any object to another object is termed as an “edge”. Below is how a sample graph looks like with each node and edge labeled:

One way to relate the above graph to a real world example is by thinking of each node as a city or a place. In that aspect, there are four nodes or cities: A, B, C and D. Each city is directly connected to 1 or more other cities. For example, city A is connected to cities B and D. City B is connected to cities A, C and D, and so on. Cities A and C are also connected indirectly via city B

Basic Concepts and Terminology

Nodes (Vertices) and Edges

Nodes (Vertices) in a graph are the fundamental building blocks that represent individual points or entities within the graph structure. They can represent a wide variety of concepts depending on what the graph is being used to model. For example, nodes in a graph can represent people in a social network, cities on a map, intersections in a road network, computers connected over network, or even abstract concepts in a flowchart. Here’s a simple example to understand nodes or vertices:

Imagine a social network where each person is represented by a bubble/circle. These bubbles are the nodes or vertices of the graph. Each node can have information associated with it, like a person’s name or age.

The connections between people (such as friendships) would be represented by lines connecting these bubbles. These connections are termed as Edges in the graph. They indicate some kind of relationship or link between two nodes (persons).

In essence, nodes in a graph are the “things” or “objects” that the graph is modeling, while the connections or relationships between them are represented by edges. Together, nodes and edges form the basic structure of a graph, allowing us to visualize and analyze relationships between different elements in a system.

Directed vs Undirected Graphs

In a directed graph, also known as a digraph, the edges have a direction associated with them. These edges are represented by arrows pointing from one vertex to another. The relationship between nodes in a directed graph is one-way, meaning that an edge from node A to node B does not imply an edge from B to A. This type of graph is useful for representing relationships where the direction matters, such as one-way streets in a road network or the flow of data in a computer network. Below is an example directed graph:

In contrast, an undirected graph has edges without any specific direction. The connections between nodes are bidirectional and symmetrical, meaning that if there is an edge between node A and node B, you can traverse from A to B and also from B to A. These edges are typically represented by simple lines connecting the nodes. Undirected graphs are suitable for modeling symmetric relationships, such as friendship connections in a social network or two way connections between cities. Below is an example undirected graph:

Weighted vs Unweighted Graphs

A weighted graph is a graph where each edge has an associated numerical value called a weight. This weight can represent various attributes such as distance, cost, time, or any other measurable quantity relevant to the problem at hand. The weight provides additional information about the relationship between connected nodes. Weighted graphs are more versatile and are commonly used in applications where the strength or cost of connections is significant, such as in path/routing algorithms, network flow problems, or cost optimization scenarios. Below is an example weighted graph:

In contrast, all the edges connecting the vertices in an unweighted graph do not have any associated value or weight. All connections between nodes are considered equal. These graphs are used when the relationship between nodes is binary - either a connection exists or it doesn’t. Unweighted graphs are simpler and are often used in scenarios where the mere presence of a connection is important, rather than its strength or cost.

Path in a Graph

A path in a graph is a sequence of nodes where each consecutive pair is connected by an edge. It’s essentially a route or a way to move from one node to another within the graph. Paths can be simple (not repeating nodes) or non-simple (repeating nodes). In the illustration below, the path via nodes C, A, D is made up of the dotted edges highlighted in red.

Cyclic vs Acyclic Graphs

A cycle in a graph occurs when a sequence of edges forms a closed loop, allowing you to start and end at the same node by traversing different edges. It’s like taking a journey through the graph and returning to the starting point without retracing the same edge twice. In the graph shown below, if you take the path A->B->D->A, you will reach node A again after traversing the nodes B and D.

Any graph which has cycles similar to the one shown above is categorized as a cyclic graph and any graph without cycles is an Acyclic Graph.

Connected vs Disconnected Graphs

A connected graph is like a close-knit community where everyone knows each other, at least indirectly. In a connected graph, you can start at any point (vertex) and find a path to reach any other point in the graph. It’s similar to a group of friends where you can always find a way to connect with anyone else in the group, even if it’s through mutual acquaintances.

On the other hand, a disconnected graph is like multiple separate communities that have no interaction with each other. In a disconnected graph, there are at least two points (vertices) that have no path between them. It’s comparable to having distinct social circles that don’t overlap at all i.e, there’s no way to get from one group to another by following the existing connections. Below is an example disconnected graphs with two different groups:

Graph Representations

Below are some of the common ways of representing a graph data structure:

Edge List: An edge list is a list of all edges in the graph, where each edge is represented as a pair of vertices (or tuples for weighted graphs). Click here to learn more about Edge List.
Adjacency List: An adjacency list uses an array or list where each element represents a vertex and contains a list of its neighboring vertices. Click here to learn more about Adjacency List.
Adjacency Matrix: An adjacency matrix is a 2D array where rows and columns represent vertices, and entries indicate the presence or weight of edges between them. Click here to learn more about Adjacency Matrix.

Basic Graph Operations

Below are some of the fundamental operations performed on graph data structure. Each operation is explained using social network analogy.

Adding a vertex: This operation relates to adding a new person to the social network. It’s like creating a new user profile without any connections yet.
Adding an edge: This operation relates to forming a new friendship between two people in the network. It’s equivalent to two users becoming friends or connecting on the platform.
Removing a vertex: This operation relates to deleting a person from the social network. It’s similar to a user deleting their account, which would also remove all their friendships.
Removing an edge: This represents the end of a friendship between two people. It’s like two users unfriending or disconnecting from each other on the platform.
Finding adjacent vertices or neighbors: This operation identifies all direct friends of a particular person in the network. It’s akin to viewing someone’s friend list on a social media platform.
Checking if two vertices are connected: This determines if two people in the network are friends, either directly or through a chain of mutual friends. It’s similar to checking if two users are connected or if there’s a “friend of a friend” relationship between them.

Common Graph Algorithms

Advanced Graph Concepts

Applications of Graphs

Social Networks: Graphs are used in social networks to represent connections between users, analyze relationships, recommend friends, detect influential users etc. Sure, here are the merged points for each category:
Transportation Systems: Graphs can be used to model road networks and traffic flow, find optimal routes for navigation, and plan public transit systems.
Computer Networks: Graphs can be used represent network topology, facilitate routing algorithms and packet transmission, and aid in network analysis and optimization.
Web Crawling and Search Engines: Graphs can be used to map links between web pages, implement various algorithms for search result ranking, and discover related content.
Recommendation Systems: Graphs can be used to model user preferences and item relationships to suggest products, movies, or content.