Graph Representation
Overview
Since Graphs are not 'native' structures to computers or to programming languages, we need ways to store them in the memory of a computer along with all the information about the graph - all verticies, edges, etc.
There are different ways we can use to store a graph and each one is better for different purposes.
Adjacency Matrix - The name sounds fancy but using an adjacency matrix simply means creating a square table, where the rows and columns represent the vertices of the graph which results in space complexity of O(V^2). The cells in the table store information about the presence or absence of edges between vertices, making it efficient for dense graphs.
The main advantages are constant-time edge queries, space-efficient for dense graphs.
Adjacency List - The adjacency list is like having a collection of small notebooks, where each notebook is associated with a vertex and lists its neighboring vertices. This representation is more space-efficient for graphs with fewer edges, as it only records the connected vertices explicitly resulting in space complexity of O(V + E). So for graphs with not many edges, this could save up a lot of memory.
The main advantages are space-efficiency for sparse graphs, efficient traversal, easy to add/remove edges.
Edge List - The edge list is a straightforward list of pairs or triplets that define the edges of the graph. It's like writing down all the relationships between vertices in a simple, easy-to-read format resulting in space complexity of O(E)
The main advantages are how simple and compact an edge list is and how easy to construct it is. It's also flexible and easy to comprehend.
Here's also a comparison between the time complexities of different graph operations depending on the used representation:
Adding/Removing a Vertex:
Adjacency Matrix: O(V^2)
Adjacency List: O(1)
Edge List: O(E)
Adding/Removing an Edge:
Adjacency Matrix: O(1)
Adjacency List: O(1) (with known vertices), O(degree) (without)
Edge List: O(1) (with known edge), O(E) (without)
Finding Neighbors of a Vertex:
Adjacency Matrix: O(V)
Adjacency List: O(degree)
Edge List: O(E)
Checking Edge Existence:
Adjacency Matrix: O(1)
Adjacency List: O(degree)
Edge List: O(E)
Iterating Over Edges:
Adjacency Matrix: O(V^2)
Adjacency List: O(E)
Edge List: O(E)
In conclusion - like everything else in life, there's no silver bullet or best type of graph representation. Each one has its own advantages and can be used for different purposes. Adjacency List is probably the most commonly used graph type due to it's aforementioned advantages and that it matches a wide range of graphs in practice so the code examples below show Graph from the animation, represented by an Adjacency List.
Code
class Graph:
def __init__(self):
self.adjacency_list = {}
def add_vertex(self, vertex):
if vertex not in self.adjacency_list:
self.adjacency_list[vertex] = []
def add_edge(self, vertex1, vertex2):
self.adjacency_list[vertex1].append(vertex2)
self.adjacency_list[vertex2].append(vertex1) # For undirected graphs (both ways)
def __str__(self):
result = ''
for vertex, neighbors in self.adjacency_list.items():
result += f'{vertex} -> {", ".join(map(str, neighbors))}\n'
return result
# Example usage:
graph = Graph()
vertices = [0, 1, 2, 3]
edges = [
[0, 1],
[1, 2],
[1, 3],
[2, 3],
[3, 0],
]
for vertex in vertices:
graph.add_vertex(vertex)
for edge in edges:
graph.add_edge(edge[0], edge[1])
print(graph)
class Graph {
constructor() {
this.adjacencyList = new Map();
}
addVertex(vertex) {
if (!this.adjacencyList.has(vertex)) {
this.adjacencyList.set(vertex, []);
}
}
addEdge(vertex1, vertex2) {
this.adjacencyList.get(vertex1).push(vertex2);
this.adjacencyList.get(vertex2).push(vertex1); // For undirected graphs (both ways)
}
toString() {
let result = '';
for (let [vertex, neighbors] of this.adjacencyList) {
result += `${vertex} -> ${neighbors.join(', ')}\n`;
}
return result;
}
}
const graph = new Graph();
const vertices = [0, 1, 2, 3];
const edges = [
[0, 1],
[1, 2],
[1, 3],
[2, 3],
[3, 0],
];
vertices.forEach((vertex) => graph.addVertex(vertex));
edges.forEach((edge) => graph.addEdge(edge[0], edge[1]));
console.log(graph.toString());
import java.util.*;
class Graph {
private Map<Integer, List<Integer>> adjacencyList;
public Graph() {
this.adjacencyList = new HashMap<>();
}
public void addVertex(int vertex) {
if (!adjacencyList.containsKey(vertex)) {
adjacencyList.put(vertex, new ArrayList<>());
}
}
public void addEdge(int vertex1, int vertex2) {
adjacencyList.get(vertex1).add(vertex2);
adjacencyList.get(vertex2).add(vertex1); // For undirected graphs (both ways)
}
public String toString() {
StringBuilder result = new StringBuilder();
for (Map.Entry<Integer, List<Integer>> entry : adjacencyList.entrySet()) {
int vertex = entry.getKey();
List<Integer> neighbors = entry.getValue();
result.append(vertex).append(" -> ").append(neighbors).append("\n");
}
return result.toString();
}
// Example usage:
public static void main(String[] args) {
Graph graph = new Graph();
int[] vertices = {0, 1, 2, 3};
int[][] edges = {
{0, 1},
{1, 2},
{1, 3},
{2, 3},
{3, 0}
};
for (int vertex : vertices) {
graph.addVertex(vertex);
}
for (int[] edge : edges) {
graph.addEdge(edge[0], edge[1]);
}
System.out.println(graph);
}
}
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int vertex;
struct Node* next;
} Node;
typedef struct {
int num_vertices;
Node** adjacency_list;
} Graph;
Graph* createGraph(int num_vertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->num_vertices = num_vertices;
graph->adjacency_list = (Node**)malloc(num_vertices * sizeof(Node*));
for (int i = 0; i < num_vertices; i++) {
graph->adjacency_list[i] = NULL;
}
return graph;
}
void addEdge(Graph* graph, int vertex1, int vertex2) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = vertex2;
newNode->next = graph->adjacency_list[vertex1];
graph->adjacency_list[vertex1] = newNode;
newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = vertex1;
newNode->next = graph->adjacency_list[vertex2];
graph->adjacency_list[vertex2] = newNode;
}
void printGraph(Graph* graph) {
for (int i = 0; i < graph->num_vertices; i++) {
printf("%d -> ", i);
Node* currentNode = graph->adjacency_list[i];
while (currentNode != NULL) {
printf("%d ", currentNode->vertex);
currentNode = currentNode->next;
}
printf("\n");
}
}
void destroyGraph(Graph* graph) {
for (int i = 0; i < graph->num_vertices; i++) {
Node* currentNode = graph->adjacency_list[i];
while (currentNode != NULL) {
Node* temp = currentNode;
currentNode = currentNode->next;
free(temp);
}
}
free(graph->adjacency_list);
free(graph);
}
int main() {
int num_vertices = 4;
Graph* graph = createGraph(num_vertices);
int edges[][2] = {
{0, 1},
{1, 2},
{1, 3},
{2, 3},
{3, 0}
};
int num_edges = sizeof(edges) / sizeof(edges[0]);
for (int i = 0; i < num_edges; i++) {
addEdge(graph, edges[i][0], edges[i][1]);
}
printGraph(graph);
destroyGraph(graph);
return 0;
}
<?php
class Graph {
private $adjacencyList = [];
public function addVertex($vertex) {
if (!isset($this->adjacencyList[$vertex])) {
$this->adjacencyList[$vertex] = [];
}
}
public function addEdge($vertex1, $vertex2) {
$this->adjacencyList[$vertex1][] = $vertex2;
$this->adjacencyList[$vertex2][] = $vertex1; // For undirected graphs (both ways)
}
public function __toString() {
$result = '';
foreach ($this->adjacencyList as $vertex => $neighbors) {
$result .= $vertex . ' -> ' . implode(', ', $neighbors) . "\n";
}
return $result;
}
}
// Example usage:
$graph = new Graph();
$vertices = [0, 1, 2, 3];
$edges = [
[0, 1],
[1, 2],
[1, 3],
[2, 3],
[3, 0],
];
foreach ($vertices as $vertex) {
$graph->addVertex($vertex);
}
foreach ($edges as $edge) {
$graph->addEdge($edge[0], $edge[1]);
}
echo $graph;
?>