Graph Data Structure

Introduction to Graph Data Structure with Examples
🔗
Click here to suggest a better video
Click here to view videos suggested by visitors

A graph in computer science is a data structure which expresses connections between different objects. Many common problems like finding shortest path among all possible paths between two destinations, finding the order in which courses have to be taken when there are pre-requisite courses for each course etc., require information about all the relations to be stored in a data structure on which different algorithms can be operated. That is where a graph data structure is useful.

Anatomy of a Graph

A graph data structure is composed 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” and the connections between any object to another object is termed as an “edge”. Below is how a sample graph looks like:

One way to relate the above graph to real world example is: you can think of each node as a city or a place. Each place is directly connected to 1 or more other places. For example place A is connected to places B and C. Place C is connected to place A and place D, and so on. If, for example, one needs to move from place A to place E, they have two options: Take the path A->B->E or A->C->D->E.

In short, each graph is made up of several nodes and certain nodes are interconnected to each other through edges. The sequence of moves from one node to another through edges is known as a “path” in the graph.

Different Graphs and Terminologies

Un-Directed Graph

An undirected graph is a type of graph where edges have no direction. The relationship between nodes is symmetrical, meaning if node A is connected to node B, then node B is also connected to node A. You can think of it as a two way road network where streets connect locations in both directions.

Directed Graph

In a directed graph (also known as a digraph), edges have a direction. The relationship between nodes is one-way, indicating that if node A is connected to node B, it doesn’t necessarily mean that node B is connected to node A. This can be visualized as a system of one-way streets.

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 from nodes A, B, F is made up of the edges highlighted in red.

Cycles in a Graph

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 illustration below, if you take the path from node A towards C, you will reach node A again after traversing the nodes C, D, E, B.

Weighted Graph

A weighted graph is a graph where each edge has an associated numerical value called a weight. These weights represent some metric like distance, cost, or any other measure. It’s similar to having different weights assigned to different roads in a map, indicating their length, toll, or time required to traverse.

Below is an example weighted graph. It is useful for algorithms which make use of edge weights to optimize for overall costs. For example if you consider the below graph as cities connected by roads with different distances, and if we need to move from A to E, we can either take the path A->B->E or the path A->C->D->E. If you consider the overall weights of each path, the first path has more distance (20+20=40) than the second path (5+5+5=15). So the algorithm would chose the second combination.

In the next section we will go through different techniques of representing a graph.