CSCI 136 Data Structures & Advanced Programming

CSCI 136 Data Structures & Advanced Programming

Graph Implementations I

1

Outline

? Recall : Adjacency Matrix of a Graph ? Recall : Graph Interface ? GraphMatrix implementation

2

Adjacency Array: Directed Graph

AB CDE F GH A0 1 1 0 0 0 1 1 B00010011 C0 1 0 1 0 0 0 0 D0 0 0 0 0 0 0 0 E00010001 F00110000 G0 0 0 0 0 1 0 0 H0 0 0 0 1 0 0 0

Entry (i,j) stores 1 if there is an edge from i to j; 0 otherwise E.G.: edges(C,B) = 1 but edges(B,C) = 0

3

Adjacency Array: Undirected Graph

AB CDE F GH A0 1 1 0 0 0 1 1 B10110011 C1 1 0 1 0 1 0 0 D0 1 1 0 1 1 0 0 E00010001 F00110010 G1 1 0 0 0 1 0 0 H1 1 0 0 1 0 0 0

Entry (i,j) store 1 if there is an edge between i and j; else 0 E.G.: edges(B,C) = 1 = edges(C,B)

4

Aside : Adjacency Array Optimization

Halving the Space (not in structure5)

0123456 00110001 11011001 21101010 30110110 40001000 50011001 61100010

0123456

0 0110001

1

011001

2

01010

3

0110

4

000

5

01

6

0

0123456789... 0110001011001010100110000010

(r,c) maps to ? + - !(!#$) (here n = 7)

&

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download