Project Links Logo Artwork
Graph Theory: Networking
Home > Graph Theory: Networking > Foundations > Definitions
Crib Sheet
Library
Help
Map
Problem List
Module Home
Links Home


conceptsdiscoverapplycollaboratepractice
 
 
go backgo forward
go backgo forward

Definitions

Applications: Representing a Graph in Computer Memory

Representing any graph, directed or undirected, in computer memory is accomplished with the use of an array of linked lists or an adjacency matrix.

Let the vertices of a graph be .

The linked-list representation of is given by an array of linked lists, where is a linked list of vertices for which is an edge of .

Example


Figure 3:





Below is the linked-list representation of the above graph.



Figure 4:





The adjacency matrix of is the square matrix of order , where if is adjacent to otherwise.

Example

01234
000000
100110
210000
310001
401010

This is the 5x5 adjacency matrix for the graph of the previous example. The row and column indices (0 through 4) are highlighted. The entry also is highlighted (for no reason other than to demonstrate the notation).

 
 
go backgo forward
go backgo forward