Data Structures for Graphs/Networks

Data Structures for Graphs/Networks
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Background

Graphs/Networks:
- A finite set of vertices/nodes
- A finite set of edges/arcs/links
Some Observations:
- Graphs/networks are used in many disciplines
- Some graphs/networks correspond to physical objects (e.g., electrical networks) and some do not (e.g., organizational charts)
- The correspondence between physical objects and vertices and edges is not always obvious (e.g., in road networks)

Types of Structures

A Small Example

The Network

A Small Example (cont.)

Using Contiguous Memory

A Small Example (cont.)

Using Linked Memory (With Known Size)

A Small Example (cont.)

Using Linked Memory (With Known Size) - Flexible Node and Arc Attributes

Linked Memory with Unknown Size

Node Based:
- Each node has access to a collection of reachable nodes
Node and Arc Based:
- Each node has access to a collection of inbound and/or outbound arcs
- Each arc has access to its tail and head node