Graph Data Structure

Subsections

• Spanning Tree
• Strongly Connected Components and Kosarajus Algorithm
• Adjacency Matrix
• Adjacency List
• Depth-First Search
• Breadth-First Search
• Bellman Ford's Algorithm

Overview

• collection of nodes that have data and are connected to other nodes
• graph is a data structure (V, E) that consists of:
  • collection of vertices V
  • collection of edges E, represented as ordered pairs of vertices (u,v)

// vertices and edges

0 --- 3
| \
|  2
| /
1


// Graph

V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}

Graph Terminology

• Adjacency: vertex is said to be adjacent to another vertex if they are connected by an edge
• Path: sequence of edges which allows going from vertex A to vertex B
• Directed Graph: graph in which an edge (u,v) doesn't necessarily mean that there is also an edge (v,u); edges in this type of graph represented by arrows to show directionj

Graph Representation

1. Adjacency Matrix

• 2D array of V x V vertices, each row and column representing a vertex
• if value of any element a[i][j] is 1, it represents that there is an edge connecting vertex i and vertex j

// vertices and edges

0 --- 3
| \
|  2
| /
1


// Graph adjacency matrix

    0   1   2   3
  -----------------
0 | 0 | 1 | 1 | 1 |
  -----------------
1 | 1 | 0 | 1 | 0 |
  -----------------
2 | 1 | 1 | 0 | 0 |
  -----------------
3 | 1 | 0 | 0 | 0 |
  -----------------

• edge lookup is extremely fast in adjacency matrix representation
• requires more space, since we must reserve space for every possible link between all vertices (V x V)

2. Adjacency List

• represents graph as array of linked lists
• index of array represents vertex and each element in linked list represents other vertices that form an edge with that vertex

// vertices and edges

0 --- 3
| \
|  2
| /
1


// Graph adjacency list representation

| V |
| 0 | -> 1 -> 2 -> 3
| 1 | -> 0 -> 2
| 2 | -> 0 -> 1
| 3 | -> 0

• adjacency list is efficient in terms of storage because only need to store values of edges

Graph Operations

most common are:

• check if element is present in graph
• graph traversal
• add elements(vertex, edges) to graph
• finding path from one vertex to another