From charlesreid1

Graphs abstract data types.

See also: Graphs/Java/ADT


Graphs are composed of three basic object types:

  • Vertex/Node
  • Edge
  • Graph

The vertex stores information specific to the vertex - typically a data element, plus additional info required by the data structure used (see Graphs/Data Structures).

Vertex ADT

  • element() - get the data element associated with this node

Edge ADT

  • element() - get the data element associated with this edge

Graph ADT


  • Nearly every implementation of a graph maintains two lists: a list of vertices and a list of edges

Size/count methods:

  • numVertices() - returns number of vertices on graph
  • numEdges() - returns number of edges on graph

Sets methods:

  • vertices() - return set of vertices V
  • edges() - return set of edges E

Get methods:

  • getEdge(u,v) - given two vertices, return the edge that connects them (if any)
  • endVertices(e) - get a pair of vertices at the endpoints of the given edge
  • opposite(v,e) - for a given vertex and edge, get the vertex at the other end of the edge
  • outgoingEdges(v) - return a set of outgoing edges from vertex v
  • incomingEdges(v) - return a set of incoming edges to vertex v

Modification methods:

  • insertVertex(x) - insert a new Vertex object storing data element x
  • insertEdge(u,v,y) - insert a new Edge object storing data element y that connects vertices u and v
  • removeVertex(v) - remove vertex v and any connecting edges from the graph
  • removeEdge(e) - remove edge e from the graph


See repository, graphs folder.