Data Structures for Graphs - ERNET

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

Recently Viewed Presentations

  • CSE 171 Lab 11 Digital Voltmeter Objective:  a

    CSE 171 Lab 11 Digital Voltmeter Objective: a

    Download a copy of the div16cnt.abl program from the class website. Write an ABEL program, VM.abl, that provides the control signals for an ADC0831 chip and collects and displays the value of the measured voltage. Pre-Lab: Create a new project,...
  • Characteristics of an effective law - Weebly

    Characteristics of an effective law - Weebly

    Characteristics of an effective law. Known to the public. For a new law to be enforceable, the public need to know about it. If people do not know about it- they will not follow it. It is the responsibility of...
  • Presentation Title

    Presentation Title

    Section 8C - treatment as dividends of ordinary income. SAIT agrees with the principle that "amounts in cash or in kind that are received or accrue in respect or by virtue of services or employment are treated, as a point...
  • Tenure Group Definitions Chart

    Tenure Group Definitions Chart

    Tenure Group Definitions Chart. Initiating Recruitment Request. Approved Hiring Freeze Exception Request. Standard Form (SF) 52 - Request for Personnel Action. Position Description including OF-8 Coversheet and Amendments. Outreach and Recruitment Strategy Plan.
  • Higher History Britain: Women's' Suffrage

    Higher History Britain: Women's' Suffrage

    The National Union of Women's' Suffrage Societies (NUWSS) was founded in 1897 under the leadership of Millicent Fawcett and campaigned for women's suffrage. They believed in moderate, peaceful tactics or 'peaceful persuasion to win the vote for middle class women...
  • Cat Fanciers Federation 2009 - 2010 Awards Banquet

    Cat Fanciers Federation 2009 - 2010 Awards Banquet

    18. Musette of . Pinetree. Farms. Owner: Hollyanne. Dustin. Household Pets. Brown Mkl Tabby • Spay
  • A Class of Problems We use Numerical continuation

    A Class of Problems We use Numerical continuation

    The symmetry is that F(q, ) is invariant to relabeling of the N classes of Z The symmetry group of all permutations on N symbols is SN. The action of SN on and q, L (q, , ) is represented...
  • Acids & Bases - ohio.k12.ky.us

    Acids & Bases - ohio.k12.ky.us

    (Milk of Magnesia) It feels slippery. (Soapy Water) It turns Red Litmus Blue. Examples of Acids Lemon Juice Vinegar Orange Juice Coffee Human stomach acid Examples of Bases Blood Baking soda Hand soap Bleach Ammonia We can neutralize an acid...