All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Description

CSCI 136 Data Structures & Advanced Programming Lecture 31 Fall 2019 Instructors: Sam Bill L Bill L Sam Last Time Graph Data Structures: Implementation Graph Interface Graph Matrix 2 Today s Outline Graph

Transcript

CSCI 136 Data Structures & Advanced Programming Lecture 31 Fall 2019 Instructors: Sam Bill L Bill L Sam Last Time Graph Data Structures: Implementation Graph Interface Graph Matrix 2 Today s Outline Graph Data Structures: Implementation Adjacency List Implementation Featuring many Iterators! Minimum Spanning Tree Prim s algorithm 3 Adjacency Array: Undirected Graph A B C D E F G H A B C D E F G H Entry (i,j) store 1 if there is an edge between i and j; else 0 E.G.: edges(b,c) = 1 = edges(c,b) 4 Efficiency : Assuming Fast Map Ops GraphMatrix add addedge getedge removeedge remove O(1) O(1) O(1) O(1) O( V ) space O( V 2 ) 5 Adjacency List : Directed Graph The vertices are stored in an array V[] V[] contains a linked list of edges having a given source 6 Adjacency List : Undirected Graph The vertices are stored in an array V[] V[] contains a linked list of edges incident to a given vertex 7 GraphList Rather than keep an adjacency matrix, maintain an adjacency list of edges at each vertex (only keep outgoing edges for directed graphs) Support both directed and undirected graphs (GraphListDirected, GraphListUndirected) 8 Vertex and GraphListVertex We use the same Edge class for list-based graphs We extend Vertex to include an Edge list GraphListVertex class adds to Vertex class A Structure to store edges adjacent to the vertex protected Structure Edge V,E adjacencies; // adjacent edges adjacencies is created as a SinglyLinkedList of edges Several methods public void addedge(edge v,e e) public boolean containsedge(edge v,e e) public Edge V,E removeedge(edge v,e e) public Edge V,E getedge(edge v,e e) public int degree() // and methods to produce Iterators... 9 GraphListVertex public GraphListVertex(V key){ super(key); // init Vertex fields adjacencies = new SinglyLinkedList Edge V,E (); } public void addedge(edge v,e e){ if (!containsedge(e)) adjacencies.add(e); } public boolean containsedge(edge v,e e){ return adjacencies.contains(e); } public Edge V,E removeedge(edge v,e e) { return adjacencies.remove(e); } 10 GraphListVertex Iterators // Iterator for incident edges public Iterator Edge V,E adjacentedges() { return adjacencies.iterator(); } // Iterator for adjacent vertices public Iterator V adjacentvertices() { return new GraphListAIterator V,E (adjacentedges(), label()); } GraphListAIterator creates an Iterator over vertices based on The Iterator over edges produced by adjacentedges() 11 GraphListAIterator GraphListAIterator uses two instance variables protected AbstractIterator Edge V,E edges; protected V vertex; public GraphListAIterator(Iterator Edge V,E i, V v) { edges = (AbstractIterator Edge V,E )i; vertex = v; } public V next() { Edge V,E e = edges.next(); if (vertex.equals(e.here())) return e.there(); else { // could be an undirected edge! return e.here(); } 12 GraphListEIterator GraphListEIterator uses one instance variable protected AbstractIterator Edge V,E edges; GraphListEIterator Takes the Map storing the vertices Uses it to build a linked list of all edges Gets an iterator for this linked list and stores it, using it in its own methods 13 GraphList To implement GraphList, we use the GraphListVertex (GLV) class GraphListVertex class Maintain linked list of edges at each vertex Instance vars: label, visited flag, linked list of edges GraphList abstract class Instance vars: Map V,GraphListVertex V,E dict; // label - vertex boolean directed; // is graph directed? How do we implement key GL methods? GraphList(), add(), getedge(), 14 protected GraphList(boolean dir){ dict = new Hashtable V,GraphListVertex V,E (); directed = dir; } public void add(v label) { } if (dict.containskey(label)) return; GraphListVertex V,E v = new GraphListVertex V,E (label); dict.put(label,v); public Edge V,E getedge(v label1, V label2) { } Edge V,E e = new Edge V,E (get(label1), get(label2), null, directed); return dict.get(label1).getedge(e); 15 GraphListDirected GraphListDirected (GraphListUndirected) implements the methods requiring different treatment due to (un)directedness of edges addedge, remove, removeedge, 16 // addedge in GraphListDirected.java // first vertex is source, second is destination } public void addedge(v vlabel1, V vlabel2, E label) { // first get the vertices GraphListVertex V,E v1 = dict.get(vlabel1); GraphListVertex V,E v2 = dict.get(vlabel2); // create the new edge Edge V,E e = new Edge V,E (v1.label(), v2.label(), label, true); // add edge only to source vertex linked list (aka adjacency list) v1.addedge(e); 17 public V remove(v label) { //Get vertex out of map/dictionary GraphListVertex V,E v = dict.get(label); //Iterate over all vertex labels (called the map keyset ) Iterator V vi = iterator(); while (vi.hasnext()) { //Get next vertex label in iterator V v2 = vi.next(); } //Skip over the vertex label we're removing //(Nodes don't have edges to themselves...) if (!label.equals(v2)) { } //Remove all edges to label //If edge does not exist, removeedge returns null removeedge(v2,label); } //Remove vertex from map dict.remove(label); return v.label(); 18 public E removeedge(v vlabel1, V vlabel2) { //Get vertices out of map GraphListVertex V,E v1 = dict.get(vlabel1); GraphListVertex V,E v2 = dict.get(vlabel2); //Create a temporary edge connecting two vertices Edge V,E e = new Edge V,E (v1.label(), v2.label(), null, true); } //Remove edge from source vertex linked list e = v1.removeedge(e); if (e == null) return null; else return e.label(); 19 Efficiency Revisited Assume Map operations are O(1) (for now) E = number of edges V = number of vertices Runtime of add, addedge, getedge, removeedge, remove? Space usage? Conclusions Matrix is better for dense graphs List is better for sparse graphs For graphs in the middle there is no clear winner 20 Efficiency : Assuming Fast Map Matrix GraphList add O(1) O(1) addedge O(1) O(1) getedge O(1) O( V ) removeedge O(1) O( V ) remove O( V ) O( E ) space O( V 2 ) O( V + E ) 21 Minimum-Cost Spanning Trees 22 Minimum-Cost Spanning Trees 23 MST: Applications Cable/phone/ethernet network Circuit design Subroutine for other algorithms Travelling salesman approximation Financial markets 24 Basic Graph Properties Recall: An undirected graph G=(V,E) is connected if for every pair u,v in V, there is a path from u to v (and so from v to u) The maximal sized connected subgraphs of G are called its connected components Note: They are induced subgraphs of G An undirected graph without cycles is a forest A connected forest is called a tree. Not to be confused with the data structure! 25 Facts About Graphs Thm: Every connected graph G=(V,E) contains a spanning subgraph G =(V,E ) that is a tree That is, a spanning tree Proof idea: If G is not a tree, then it contains a cycle C Removing an edge from C leaves G connected (why) Repeat until no more cycles remain 26 Edge-Weighted Graphs An edge-weighting of a graph G=(V,E) is an assignment of a number (weight) to each edge of G We write the weight of e as w(e) or w e The weight w(g ) of any subgraph G of G is the sum of the weights of the edges in G 27 A Famous Problem Given a connected, undirected graph G=(V,E) with non-negative edge weights, find a minimum-weight, connected, spanning subgraph of G. Frequently, we refer to the edge weights as costs and so this problem becomes: Given an undirected graph G with edge costs, compute a minimum-cost spanning tree of G. 28 Minimum-Cost Spanning Trees 29 Minimum-Cost Spanning Trees 30 Finding a MCST Suppose we just wanted to find a PCST (pretty cheap spanning tree), here s one idea: Grow It Greedily! Pick a vertex and find its cheapest incident edge. Now we have a (small) tree Repeatedly add the cheapest edge to the tree that keeps it a tree (connected, no cycles) This method is called Prim s Algorithm How close might this get us to the MCST? 31 An Amazing Fact Thm: (Prim 1957) The greedy tree-growing algorithm always finds a minimum-cost spanning tree for any connected graph. Contrast this with the greedy exam scheduling algorithm, which does not always find a minimum schedule (coloring) Why does this work? 32 Prim s Algorithm prim(g) // finds a MCST of connected G=(V,E) let v be a vertex of G; set V 1 ß{v} and V 2 ßV 1 - {v} let A be the set of all edges between V 1 and V 2 while( V 1 V ) let eßcheapest edge in A between V 1 and V 2 add e to MCST let ußthe vertex of e in V 2 move u from V 2 to V 1 ; add to A all edges incident to u // note: A may have edges with both ends in V 1 33 Implementing Prim s Algorithm We ll build the MCST by marking its edges as visited in G We ll build V 1 by marking its vertices visited How should we represent A? What operations are important to A? Add edges Remove cheapest edge A priority queue! When we remove an edge from A, check to ensure it has one end in each of V 1 and V 2 34 ComparableEdge Class Values in a PriorityQueue need to implement Comparable We wrap edges of the PQ in a class called ComparableEdge It requires the label used by graph edges to be of a Comparable type 35 MCST: The Code PriorityQueue ComparableEdge String,Integer q = new VectorHeap ComparableEdge String,Integer (); String v = null; // current vertex Edge String,Integer e; // current edge boolean searching; // still building tree g.reset(); // clear visited flags // select a node from the graph, if any Iterator String vi = g.iterator(); if (!vi.hasnext()) return; v = vi.next(); 36 MCST: The Code do { // visit the vertex and add all outgoing edges to the priority queue g.visit(v); Iterator String ai = g.neighbors(v); while (ai.hasnext()) { }... // turn it into outgoing edge e = g.getedge(v,ai.next()); // add the edge to the queue q.add(new ComparableEdge String,Integer (e)); 37 MCST: The Code searching = true; while (searching &&!q.isempty()) { } } while (!searching); // grab next shortest edge e = q.remove(); // Is e between V 1 and V 2 (subtle code!!) v = e.there(); // does e connect V 1 to V 2? if (g.isvisited(v)) v = e.here(); if (!g.isvisited(v)) { searching = false; } g.visitedge(g.getedge(e.here(), e.there())); 38 Prim : Space Complexity Graph: O( V + E ) Each vertex and edge uses a constant amount of space Priority Queue O( E ) Each edge takes up constant amount of space Every other object (including the neighbor iterator) uses a constant amount of space Result: O( V + E ) Optimal in Big-O sense! 39 Prim : Time Complexity Assume Map ops are O(1) time (not quite true!) For each iteration of do... while loop Add neighbors to queue: O(log E ) time each Find next edge: O(log E ) time each Each edge is added to the queue at most once O(E log E ) time 40

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks