- Forward


Data Structures for Graphs/Networks
An Introduction


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Background
Back Forward
  • 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
Back Forward
  • Contiguous:
    • Possible when the numbers of vertices and edges are known
  • Linked:
    • Can be used in all situations
A Small Example
Back Forward

The Network

images/small-network.gif
A Small Example (cont.)
Back Forward

Using Contiguous Memory

images/small-network_contiguous.gif
A Small Example (cont.)
Back Forward

Using Linked Memory (With Known Size)

images/small-network_linked-node.gif
A Small Example (cont.)
Back Forward

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

images/small-network_linked-node-arc.gif
Linked Memory with Unknown Size
Back Forward
  • 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
There's Always More to Learn
Back -