Week 3: Graph Data Structures and Algorithms (25)

Array-of-edges Representation (cont)

Graph initialisation

newGraph(V):
|  Input  number of nodes V
|  Output new empty graph
|
|  g.nV = V   // #vertices (numbered 0..V-1)
|  g.nE = 0   // #edges
|  allocate enough memory for g.edges[]
|  return g

How much is enough? … No more than V(V-1)/2 … Much less in practice (sparse graph)