DOC PREVIEW
Princeton COS 226 - Undirected Graphs

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Princeton COS 226 - Undirected Graphs

Documents in this Course
QUICKSORT

QUICKSORT

14 pages

QUICKSORT

QUICKSORT

55 pages

STRINGS

STRINGS

69 pages

Lecture

Lecture

4 pages

STRINGS

STRINGS

18 pages

Hashing

Hashing

7 pages

MERGESORT

MERGESORT

14 pages

Quicksort

Quicksort

12 pages

Strings

Strings

10 pages

Overview

Overview

15 pages

Hashing

Hashing

13 pages

Mergesort

Mergesort

15 pages

Tries

Tries

13 pages

Final

Final

12 pages

Final

Final

12 pages

Mergesort

Mergesort

13 pages

Final

Final

10 pages

Load more
Download Undirected Graphs
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Undirected Graphs and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Undirected Graphs 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?