Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2008·March 26, 2008 7:28:15 AMUndirected GraphsReferences: Algorithms in Java, Chapters 17 and 18 http://www.cs.princeton.edu/algs4/51undirected‣graph API‣maze exploration‣depth-first search‣breadth-first search‣connected components‣challenges2Undirected graphsGraph. Set of vertices connected pairwise by edges.Why study graph algorithms?•Interesting and broadly useful abstraction.•Challenging branch of computer science and discrete math.•Hundreds of graph algorithms known.•Thousands of practical applications.3Social networksReference: Bearman, Moody and Stovel, 2004image by Mark Newmanhigh school datingReference: Adamic and Adar, 2004corporate e-mail4Protein interaction networkReference: Jeong et al, Nature Review | Genetics5The Internet as mapped by the Opte Projecthttp://en.wikipedia.org/wiki/Internet6Graph applicationsgraphvertexedgecommunicationtelephone, computerfiber optic cablecircuitgate, register, processorwiremechanicaljointrod, beam, springfinancialstock, currencytransactionstransportationstreet intersection, airporthighway, airway routeinternetclass C networkconnectiongameboard positionlegal movesocial relationshipperson, actorfriendship, movie castneural networkneuronsynapseprotein networkproteinprotein-protein interactionchemical compoundmoleculebond7Graph terminology8Some graph-processing problemsPath. Is there a path between s and t?Shortest path. What is the shortest path between s and t?Cycle. Is there a cycle in the graph?Euler tour. Is there a cycle that uses each edge exactly once?Hamilton tour. Is there a cycle that uses each vertex exactly once? Connectivity. Is there a way to connect all of the vertices?MST. What is the best way to connect all of the vertices?Biconnectivity. Is there a vertex whose removal disconnects the graph?Planarity. Can you draw the graph in the plane with no crossing edges?Graph isomorphism. Do two adjacency matrices represent the same graph?First challenge. Which of these problems are easy? difficult? intractable?9‣graph API‣maze exploration‣depth-first search‣breadth-first search‣connected components‣challengesVertex representation.•This lecture: use integers between 0 and V-1.•Real world: convert between names and integers with symbol table.Other issues. Parallel edges, self-loops.AGECBFD10Graph representationsymbol table064215311Graph API public class Graphgraph data typeGraph(int V)create an empty graph with V verticesGraph(In in)create a graph from input streamvoidaddEdge(int v, int w)add an edge v-wIterable<Integer>adj(int v)return an iterator over the neighbors of vint V()return number of verticesStringtoString()return a string representation In in = new In(); Graph G = new Graph(in); StdOut.println(G); for (int v = 0; v < G.V(); v++) for (int w : G.adj(v)) /* process edge v-w */read graph from standard inputprocess bothv-w and w-v% more tiny.txt70 10 20 50 63 43 54 6Store a list of the edges (linked list or array).12Set of edges representation8710912110642153 0 1 0 2 0 5 0 6 3 4 3 5 4 6 7 8 9 10 9 11 9 12Maintain a two-dimensional V-by-V boolean array;for each edge v-w in graph: adj[v][w] = adj[w][v] = true.01234567891011120123456789101112011001100000010000000000001000000000000000011000000000010100000001001100000000100000000000000000000100000000000100000000000000011100000000010000000000001001000000000101013Adjacency-matrix representationtwo entriesfor each edge871091211064215314Adjacency-matrix representation: Java implementationpublic class Graph{ private final int V; private final boolean[][] adj; public Graph(int V) { this.V = V; adj = new boolean[V][V]; } public void addEdge(int v, int w) { adj[v][w] = true; adj[w][v] = true; } public Iterable<Integer> adj(int v) { return new AdjIterator(v); }}adjacency matrixcreate empty graph with V vertices add edge v-w(no parallel edges)iterator for v's neighbors(code for AdjIterator omitted)15Adjacency-list representationMaintain vertex-indexed array of lists (implementation omitted).5 2 1 600546 5 30 434 08710 11 1299 129 11two entriesfor each edge87109121106421530:1:2:3:4:5:6:7:8:9:10:11:12:Maintain vertex-indexed array of sets.0:1:2:3:4:5:6:7:8:9:10:11:12:{ 1 2 5 6 }{ 0 }{ 0 }{ 4, 5 }{ 3, 5, 6 }{ 0, 3, 4 }{ 0, 4 }{ 8 }{ 7 }{ 10, 11, 12 }{ 9 }{ 9, 12 }{ 1, 9 }16Adjacency-set graph representationtwo entriesfor each edge871091211064215317Adjacency-set representation: Java implementationpublic class Graph{ private final int V; private final SET<Integer>[] adj; public Graph(int V) { this.V = V; adj = (SET<Integer>[]) new SET[V]; for (int v = 0; v < V; v++) adj[v] = new SET<Integer>(); } public void addEdge(int v, int w) { adj[v].add(w); adj[w].add(v); } public Iterable<Integer> adj(int v) { return adj[v]; }}adjacency setscreate empty graphwith V verticesadd edge v-w(no parallel edges)iterator for v's neighborsGraphs are abstract mathematical objects, but:•ADT implementation requires specific representation.•Efficiency depends on matching algorithms to representations.In practice. Use adjacency-set (or adjacency-list) representation.•Algs all based on iterating over edges incident to v.•Real-world graphs tend to be “sparse.”18Graph representationsrepresentationspaceedge betweenv and w?iterate over edgesincident to v?list of edgesEEEadjacency matrixV21Vadjacency listE + Vdegree(v)degree(v)adjacency setE + Vlog (degree(v))degree(v)huge number of vertices,small average vertex degree19‣graph API‣maze exploration‣depth-first search‣breadth-first search‣connected components‣challenges20Maze explorationMaze graphs.•Vertex = intersection.•Edge = passage.Goal. Explore every passage in the maze.21Trémaux maze explorationAlgorithm.•Unroll a ball of string behind you.•Mark each visited intersection by turning on a light.•Mark each visited passage by opening a door.First use? Theseus entered labyrinth to kill the monstrous Minotaur;Ariadne held ball of string.Claude Shannon (with Theseus mouse)2223Maze exploration24Maze exploration25Rat in a maze26‣graph API‣maze exploration‣depth-first search‣breadth-first search‣connected components‣challengesGoal. Systematically search through a graph.Idea. Mimic maze exploration.Running time.•O(E) since each edge examined at most twice.•Usually less
View Full Document