Graph ADT
Data
- Vertices and edges
Methods
endVertices(e): an array of two endvertices of e.opposite(v, e): the vertex opposite of v on e.areAdjacent(v, w): true if and only if v and w are adjacent.getAdjacent(v): return a list of the vertices adjacent to vertex v.insertVertex(o): insert a vertex storing element o.insertEdge(v, w, o): insert an edge (v, w) storing element o.removeVertex(v): remove vertex v (and its incident edges).removeEdge(e): remove edge e.incidentEdges(v): edges incident to v.getDegree(v): return the degree of vertex v.
Can be represented by Adjacency Matrix, Adjacency List
Matrix
- Useful for dense graph.
- space requirement : O(|V|^2)
List
- Useful for sparse graph.
- space requirement
- if graph is sparse : O(|V| + |E|)
- if graph is dense : O(|V|^2)
Performance
