Data Structures for Graphs Edge list Adjacency lists Adjacency matrix NW 35 DL 247 BOS AA 49 LAX E DL 335 AA 1387 AA 523 DFW JFK V AA 411 UA 120 MIA AA 903 ORD UA 877 TW 45 SFO 1 Data Structures for Graphs
A Graph! How can we represent it? To start with, we store the vertices and the edges into two containers, and each edge object has references to the vertices it TW 45 BOS connects. ORD JFK SFO LAX DFW MIA Additional structures can be used to perform efficiently the methods of the Graph ADT 2 Edge List The edge list structure simply stores the vertices and the edges into unsorted sequences. Easy to implement. Finding the edges incident on a given vertex is inefficient since it requires examining the entire edge sequence E NW 35 DL 247 BOS AA 49 LAX DL 335 AA 1387 AA 523 DFW JFK
AA 411 UA 120 MIA AA 903 ORD UA 877 TW 45 SFO 3 V Performance of the Edge List Structure Operation Time size, isEmpty, replaceElement, swap O(1) numVertices, numEdges O(1) vertices O(n) edges, directedEdges, undirectedEdges O(m) elements, positions
O(n+m) endVertices, opposite, origin, destination, isDirected O(1) incidentEdges, inIncidentEdges, outIncidentEdges, adjacent Vertices , inAdjacentVertices, outAdjacentVertices,areAdjacent, degree, inDegree, outDegree O(m) insertVertex, insertEdge, insertDirectedEdge, removeEdge, makeUndirected, reverseDirection, setDirectionFrom, setDirectionTo O(1) removeVertex 4 O(m) Adjacency List (traditional) adjacency list of a vertex v: sequence of vertices adjacent to v represent the graph by the adjacency lists of all the vertices a b c e d b c a
e a d e a c e b c d d Space = (N + deg(v)) = (N + M)) 5 Adjacency List (modern) The adjacency list structure extends the edge list structure by adding incidence containers to each vertex. NW 35 DL 247 BOS in out NW 35 DL 247
AA 49 LAX in out AA 49 UA 120 AA 411 DL 335 AA 1387 AA 523 DFW JFK in in out AA1387 DL335 UA 877 AA 49 AA 523 AA 411 out NW 35 AA1387 AA 903 UA 120 MIA
in out DL 247 AA523 AA 903 AA 411 AA 903 UA 877 ORD in out UA 120 UA 877 TW 45 SFO in out TW 45 DL 335 TW 45 The space requirement is O(n + m). 6 Performance of the Adjacency List Structure size, isEmpty, replaceElement, swap O(1)
numVertices, numEdges O(1) vertices O(n) edges, directedEdges, undirectedEdges O(m) elements, positions O(n+m) endVertices, opposite, origin, destination, isDirected, degree, inDegree, outDegree O(1) incidentEdges(v), inIncidentEdges(v), outIncidentEdges(v), adjacentVertices(v), inAdjacentVertices(v), outAdjacentVertices(v) O(deg(v)) areAdjacent(u, v) O(min(deg(u ),deg(v))) insertVertex, insertEdge, insertDirectedEdge, removeEdge, makeUndirected, reverseDirection, insertVertex, insertEdge, insertDirectedEdge, removeEdge, makeUndirected, reverseDirection, O(1) removeVertex(v) O(deg(v))
7 Adjacency M)atrix (traditional) a b c d e a b c d e a F T T T F b T F F F T c T F F T T
d T F T F T e F T T T F matrix M with entries for all pairs of vertices M[i,j] = true means that there is an edge (i,j) in the graph. M[i,j] = false means that there is no edge (i,j) in the graph. There is an entry for every possible edge, therefore: Space = (N2) 8 Adjacency M)atrix (modern) The adjacency matrix structures augments the edge list structure with a matrix where each row and column corresponds to a vertex. 9 Performance of the Adjacency M)atrix Structure 10