Algorithms in Java, 4th Edition·Robert Sedgewick and Kevin Wayne·Copyright © 2009·March 7, 2010 5:41:48 PM4.1 Undirected GraphsReferences: Algorithms in Java (Part 5), 3rd edition, Chapters 17 and 18‣graph API‣maze exploration‣depth-first search‣breadth-first search‣connected components‣challengesGraph. 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.2Undirected graphs3Protein interaction networkReference: Jeong et al, Nature Review | Genetics4The Internet as mapped by the Opte Projecthttp://en.wikipedia.org/wiki/Internet5Map of science clickstreamshttp://www.plosone.org/article/info:doi/10.1371/journal.pone.00048036High-school datingReference: Bearman, Moody and Stovel, 2004image by Mark Newman7Kevin's facebook friends (Princeton network)8One week of Enron emails9Graph 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 compoundmoleculebond10Graph terminology11Some 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?Challenge. Which of these problems are easy? difficult? intractable?12‣graph API‣maze exploration‣depth-first search‣breadth-first search‣connected components‣challengesVertex representation.•This lecture: use integers between 0 and V-1.•Applications: convert between names and integers with symbol table.Issues. Parallel edges, self-loops.AGECBFD13Graph representationsymbol table064215314Graph API public class Graph public class Graphgraph data typegraph data typeGraph(int V)Graph(int V)create an empty graph with V verticesGraph(In in)Graph(In in)create a graph from input streamvoidaddEdge(int v, int w)addEdge(int v, int w)add an edge v-wIterable<Integer>adj(int v)adj(int v)return an iterator over the neighbors of vint V()V()return number of vertices In in = new In(); Graph G = new Graph(in); for (int v = 0; v < G.V(); v++) for (int w : G.adj(v)) /* process edge v-w */read graph from standard inputprocesses bothv-w and w-v% more tiny.txt70 10 20 50 63 43 54 6Maintain a list of the edges (linked list or array).15Set 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.01234567891011120123456789101112011001100000010000000000001000000000000000011000000000010100000001001100000000100000000000000000000100000000000100000000000000011100000000010000000000001001000000000101016Adjacency-matrix representationtwo entriesfor each edge871091211064215317Adjacency-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)18Adjacency-list representationMaintain vertex-indexed array of lists (use Bag abstraction)5 2 1 600546 5 30 434 08710 11 1299 129 11two entriesfor each edge0:1:2:3:4:5:6:7:8:9:10:11:12:8710912110642153Bag objects19Adjacency-list representation: Java implementationpublic class Graph{ private final int V; private final Bag<Integer>[] adj; public Graph(int V) { this.V = V; adj = (Bag<Integer>[]) new Bag[V]; for (int v = 0; v < V; v++) adj[v] = new Bag<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 lists( use Bag ADT )create empty graphwith V verticesadd edge v-w( parallel edges allowed)iterator for v's neighborsIn practice. Use adjacency-set (or adjacency-list) representation.•Algorithms based on iterating over edges incident to v.•Real-world graphs tend to be “sparse.”20Graph representationsrepresentationspaceinsert edgeedge betweenv and w?iterate over edgesincident to v?list of edgesEEEEadjacency matrixV211Vadjacency listE + V1 *degree(v)degree(v)adjacency setE + Vlog (degree(v))log (degree(v))degree(v)huge number of vertices,small average vertex degree* only if parallel edges allowedused in IntroJava21‣graph API‣maze exploration‣depth-first search‣breadth-first search‣connected components‣challenges22Maze explorationMaze graphs.•Vertex = intersection.•Edge = passage.Goal. Explore every passage in the maze.23Trémaux maze explorationAlgorithm.•Unroll a ball of string behind you.•Mark each visited intersection and each visited passage.•Retrace steps when no unvisited options.First use? Theseus entered labyrinth to kill the monstrous Minotaur;Ariadne held ball of string.Claude Shannon (with Theseus mouse)24Maze exploration25Maze exploration26Rat in a maze27‣graph API‣maze exploration‣depth-first search‣breadth-first search‣connected components‣challengesGoal. Systematically search through a graph.Idea. Mimic maze exploration.Challenge.•Masks a complex recursive process.•[stay tuned]Typical applications.•Find all vertices connected to a given s.•Find a path from s to t. Depth-first searchMark s as visited.Recursively visit all unmarked vertices v adjacent to s.DFS (to visit a
View Full Document
Unlocking...