Algorithms and Data Structures: Graphs

[CSE2304], [FAQ], [progress] & [plan], Bib', Alg's, C - L.A., Sem'1, 2006, FIT, Monash, .au
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

Graphs: Introduction

The bad news?

Lists are easiest
Trees are harder
Graphs are hardest

Graphs consist of vertices (nodes) and edges (arcs)
can be weighted / unweighted
and directed / undirected / directed-acyclic graphs (DAG)

(also many other special types of graph)

Undirected Graph

Directed Graph

Weighted Undirected Graph

Weighted Directed Graph

Formally a Graph, G, is:

G = < V, E >, a pair of sets, where
V is a set of Vertices
E is a set of edges, where
each e in E is a pair <v₁, v₂>, and v₁ & v₂ are in V.

Undirected Graphs

edges are unordered pairs, often written (v₁, v₂), and (v₁, v₂) = (v₂, v₁),

(Edge-) Weighted Graphs

each edge is a triple <v₁, v₂, w>, where w is a weight (a number/ length/ time/...etc.)

Graphs

[lecturer: derive a graph from some real example; class: take notes!]

A Graph G = < V, E >

max number of edges is
- |V|² for a directed graph
- |V|*(|V|+1)/2 for an undirected graph
graph is
- sparse if |E| < < |V|²
- dense if |E| ~ |V|²

Graph by Adjacency Matrix:

v₂ is adjacent to v₁ iff <v₁, v₂> is an edge in E. e.g. A directed graph:
read on . . .

[fill in missing bits]

directed, by adjacency matrix:

	1	2	3	4	5	6
1	.	.	.	.	.	.
2	.	.	.	.	.	.
3	.	.	.	.	.	.
4	.	.	.	.	.	.
5	.	.	.	.	.	.
6	.	.	.	.	.	.

[fill in the missing bits]

-undirected, by adjacency matrix:

	1	2	3	4	5	6
1	.
2	.	.
3	.	.	.
4	.	.	.	.
5	.	.	.	.	.
6	.	.	.	.	.	.

Undirected graph - adjacency matrix is symmetric, or lower- (or upper-) triangular.

Adjacency Matrices of (Un)weighted graphs, a tricky point:

Unweighted graph
- m[i,j] = true iff v_j is adjacent to v_i
Weighted graph
- m[i,j] = weight(<v_i, v_j>) if v_j adjacent to v_i
- m[i,j] = some "special" value if v_j not adjacent to v_i (must suit problem)
  - somtimes use zero (provided it cannot be a weight)
  - sometimes use a big value for "infinity"

[fill in missing bits]

by adjacency lists:

1: ----> [__, -]-----> nil

2: ----> [__, -]-----> nil

3: ----> [__, -]-----> nil

4: ----> [__, -]-----> [__, -]-----> [__, -]-----> nil

5: ----> [__, -]-----> [__, -]-----> [__, -]-----> nil

6: ----> [__, -] ----> nil

Graph Summary

can represent
- road, & other transport networks
- electronic circuits, telecommunications networks
- relationships
directed / undirected
weighted / unweighted
sparse / dense
NB. Adjacent (by an edge) and connected (by a path) are not the samething.
Adjacency matrix good for [_____?_____] graphs
Adjacency lists good for [_____?_____] graphs

Read about: path problems in Graphs.
2006 © L.Allison, Faculty of Information Technology (Clayton School), Monash University, Australia 3800.