Example: biology

Basic Graph Algorithms - Stanford University

Basic Graph AlgorithmsJaehyun ParkCS 97 SIStanford UniversityJune 29, 2015 OutlineGraphsAdjacency Matrix and Adjacency ListSpecial GraphsDepth-First and Breadth-First SearchTopological SortEulerian CircuitMinimum Spanning Tree (MST)Strongly Connected Components (SCC)Graphs2 Graphs An abstract way of representing connectivity using nodes (alsocalled vertices) and edges We will label the nodes from1ton medges connect some pairs of nodes Edges can be either one-directional (directed) or bidirectional Nodes and edges can have some auxiliary informationGraphs3 Why Study Graphs? Lots of problems formulated and solved in terms of graphs Shortest path problems Network flow problems Matching problems 2-SAT problem Graph coloring problem Traveling Salesman Problem (TSP):still unsolved! and many Matrix and Adjacency ListSpecial GraphsDepth-First and Breadth-First SearchTopological SortEulerian CircuitMinimum Spanning Tree (MST)Strongly Connected Components (SCC)Adjacency Matrix and Adjacency List5 Storing Graphs Need to store both the set of nodesVand the set of edgesE Nodes can be stored in an array Edges must be stored in some other way Want to support operations such as: Retrieving all edges incident to a particular node Testing if given two nodes are directly

Basic Graph Algorithms Jaehyun Park CS 97SI Stanford University June 29, 2015. Outline Graphs Adjacency Matrix and Adjacency List Special Graphs Depth-First and Breadth-First Search Topological Sort Eulerian Circuit ... The most basic graph algorithm that visits nodes of a graph

Tags:

  Basics, Algorithm, Graph, Basic graph algorithms

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Other abuse

Transcription of Basic Graph Algorithms - Stanford University

1 Basic Graph AlgorithmsJaehyun ParkCS 97 SIStanford UniversityJune 29, 2015 OutlineGraphsAdjacency Matrix and Adjacency ListSpecial GraphsDepth-First and Breadth-First SearchTopological SortEulerian CircuitMinimum Spanning Tree (MST)Strongly Connected Components (SCC)Graphs2 Graphs An abstract way of representing connectivity using nodes (alsocalled vertices) and edges We will label the nodes from1ton medges connect some pairs of nodes Edges can be either one-directional (directed) or bidirectional Nodes and edges can have some auxiliary informationGraphs3 Why Study Graphs? Lots of problems formulated and solved in terms of graphs Shortest path problems Network flow problems Matching problems 2-SAT problem Graph coloring problem Traveling Salesman Problem (TSP):still unsolved! and many Matrix and Adjacency ListSpecial GraphsDepth-First and Breadth-First SearchTopological SortEulerian CircuitMinimum Spanning Tree (MST)Strongly Connected Components (SCC)Adjacency Matrix and Adjacency List5 Storing Graphs Need to store both the set of nodesVand the set of edgesE Nodes can be stored in an array Edges must be stored in some other way Want to support operations such as: Retrieving all edges incident to a particular node Testing if given two nodes are directly connected Use either adjacency matrix or adjacency list to store theedgesAdjacency Matrix and Adjacency List6 Adjacency Matrix An easy way to store connectivity information Checking if two nodes are directly connected.

2 O(1)time Make ann nmatrixA aij= 1if there is an edge fromitoj aij= 0otherwise Uses (n2)memory Only use whennis less than a few thousands, andwhen the Graph is denseAdjacency Matrix and Adjacency List7 Adjacency List Each node has a list of outgoing edges from it Easy to iterate over edges incident to a certain node The lists have variable lengths Space usage: (n+m)Adjacency Matrix and Adjacency List8 Implementing Adjacency List Solution 1. Using linked lists Too much memory/time overhead Using dynamic allocated memory or pointers is bad Solution 2. Using an array ofvectors Easier to code, no bad memory issues But very slow Solution 3. Using arrays (!) Assuming the total number of edges is known Very fast and memory-efficientAdjacency Matrix and Adjacency List9 Implementation Using ArraysAdjacency Matrix and Adjacency List10 Implementation Using Arrays Have two arraysEof sizemandLEof sizen Econtains the edges LEcontains the starting pointers of the edge lists InitializeLE[i] = -1for alli LE[i] = 0is also fine if the arrays are 1-indexed Inserting a new edge fromutovwith IDkE[k].

3 To = vE[k].nextID = LE[u]LE[u] = kAdjacency Matrix and Adjacency List11 Implementation Using Arrays Iterating over all edges starting at u:for(ID = LE[u]; ID != -1; ID = E[ID].nextID)// E[ID] is an edge starting from u Once built, it s hard to modify the edges The Graph better be static! But adding more edges is easyAdjacency Matrix and Adjacency List12 OutlineGraphsAdjacency Matrix and Adjacency ListSpecial GraphsDepth-First and Breadth-First SearchTopological SortEulerian CircuitMinimum Spanning Tree (MST)Strongly Connected Components (SCC)Special Graphs13 Tree A connected acyclic Graph Most important type of special graphs Many problems are easier to solve on trees Alternate equivalent definitions: A connected Graph withn 1edges An acyclic Graph withn 1edges There is exactly one path between every pair of nodes An acyclic Graph but adding any edge results in a cycle A connected Graph but removing any edge disconnects itSpecial Graphs14 Other Special Graphs Directed Acyclic Graph (DAG): the name says what it is Equivalent to a partial ordering of nodes Bipartite Graph .

4 Nodes can be separated into two groupsSandTsuch that edges exist betweenSandTonly (no edgeswithinSor withinT)Special Graphs15 OutlineGraphsAdjacency Matrix and Adjacency ListSpecial GraphsDepth-First and Breadth-First SearchTopological SortEulerian CircuitMinimum Spanning Tree (MST)Strongly Connected Components (SCC)Depth-First and Breadth-First Search16 Graph Traversal The most Basic Graph algorithm that visits nodes of a graphin certain order Used as a subroutine in many other Algorithms We will cover two Algorithms Depth-First Search (DFS): uses recursion (stack) Breadth-First Search (BFS): uses queueDepth-First and Breadth-First Search17 Depth-First SearchDFS(v): visits all the nodes reachable fromvin depth-first order Markvas visited For each edgev u: Ifuis not visited, call DFS(u) Use non-recursive version if recursion depth is too big (overafew thousands) Replace recursive calls with a stackDepth-First and Breadth-First Search18 Breadth-First SearchBFS(v): visits all the nodes reachable fromvin breadth-first order Initialize a queueQ Markvas visited and push it toQ WhileQis not empty: Take the front element ofQand call itw For each edgew u: Ifuis not visited, mark it as visited and push it toQDepth-First and Breadth-First Search19 OutlineGraphsAdjacency Matrix and Adjacency ListSpecial GraphsDepth-First and Breadth-First SearchTopological SortEulerian CircuitMinimum Spanning Tree (MST)Strongly Connected Components (SCC)Topological Sort20 Topological Sort Input: a DAGG= (V, E) Output.

5 An ordering of nodes such that for each edgeu v,ucomes beforev There can be many answers , both{6,1,3,2,7,4,5,8}and{1,6,2,3,4,5,7,8 }arevalid orderings for the Graph belowTopological Sort21 Topological Sort Any node without an incoming edge can be the first element After deciding the first node, remove outgoing edges from it Repeat! Time complexity:O(n2+m) Too Sort22 Topological Sort (faster version) Precompute the number of incoming edgesdeg(v)for eachnodev Put all nodesvwithdeg(v) = 0into a queueQ Repeat untilQbecomes empty: TakevfromQ For each edgev u: Decrementdeg(u)(essentially removing the edgev u) Ifdeg(u) = 0, pushutoQ Time complexity: (n+m)Topological Sort23 OutlineGraphsAdjacency Matrix and Adjacency ListSpecial GraphsDepth-First and Breadth-First SearchTopological SortEulerian CircuitMinimum Spanning Tree (MST)Strongly Connected Components (SCC)

6 Eulerian Circuit24 Eulerian Circuit Given an undirected graphG Want to find a sequence of nodes that visits every edgeexactly once and comes back to the starting point Eulerian circuits exist if and only if Gis connected andeach node has an even degreeEulerian Circuit25 Constructive Proof of Existence Pick any node inGand walk randomly without using thesame edge more than once Each node is of even degree, so when you enter a node, therewill be an unused edge you exit through Except at the starting point, at which you can get stuck When you get stuck, what you have is a cycle Remove the cycle and repeat the process in each connectedcomponent Glue the cycles together to finish!Eulerian Circuit26 Related Problems Eulerian path: exists if and only if the Graph is connected andthe number of nodes with odd degree is0or2. Hamiltonian path/cycle: a path/cycle that visits everynodeinthe Graph exactly once.

7 Looks similar but very hard (stillunsolved)!Eulerian Circuit27 OutlineGraphsAdjacency Matrix and Adjacency ListSpecial GraphsDepth-First and Breadth-First SearchTopological SortEulerian CircuitMinimum Spanning Tree (MST)Strongly Connected Components (SCC)Minimum Spanning Tree (MST)28 Minimum Spanning Tree (MST) Given an undirected weighted graphG= (V, E) Want to find a subset ofEwith the minimum total weightthat connects all the nodes into a tree We will cover two Algorithms : Kruskal s algorithm Prim s algorithmMinimum Spanning Tree (MST)29 Kruskal s algorithm Main idea: the edgee with the smallest weight has to be inthe MST Simple proof: Assume not. Take the MSTT that doesn t containe . Adde toT, which results in a cycle. Remove the edge with the highest weight from the cycle. The removed edge cannot bee since it has the smallestweight. Now we have a better spanning tree thanT Contradiction!

8 Minimum Spanning Tree (MST)30 Kruskal s algorithm Another main idea: after an edge is chosen, the two nodes atthe ends can be merged and considered as a single node(supernode) Pseudocode: Sort the edges in increasing order of weight Repeat until there is one supernode left: Take the minimum weight edgee Ife connects two different supernodes, then connect themand merge the supernodes (use union-find) Otherwise, ignoree and try the next edgeMinimum Spanning Tree (MST)31 Prim s algorithm Main idea: Maintain a setSthat starts out with a single nodes Find the smallest weighted edgee = (u, v)that connectsu Sandv / S Adde to the MST, addvtoS Repeat untilS=V Differs from Kruskal s in that we grow a single supernodeSinstead of growing multiple ones at the same timeMinimum Spanning Tree (MST)32 Prim s algorithm Pseudocode InitializeS:={s},Dv:= cost(s, v)for everyv If there is no edge betweensandv,cost(s, v) = Repeat untilS=V: Findv / Swith smallestDv Use a priority queue or a simple linear search AddvtoS, addDvto the total weight of the MST For each edge(v, w): UpdateDw:= min(Dw,cost(v, w)) Can be modified to compute the actual MST along with thetotal weightMinimum Spanning Tree (MST)33 Kruskal s vs Prim s Kruskal s algorithm TakesO(mlogm)time Pretty easy to code Generally slower than Prim s Prim s algorithm Time complexity depends on the implementation.

9 Can beO(n2+m),O(mlogn), orO(m+nlogn) A bit trickier to code Generally faster than Kruskal sMinimum Spanning Tree (MST)34 OutlineGraphsAdjacency Matrix and Adjacency ListSpecial GraphsDepth-First and Breadth-First SearchTopological SortEulerian CircuitMinimum Spanning Tree (MST)Strongly Connected Components (SCC)Strongly Connected Components (SCC)35 Strongly Connected Components (SCC) Given adirectedgraphG= (V, E) A Graph isstrongly connectedif all nodes are reachable fromevery single node inV Strongly connected components ofGare maximal stronglyconnected subgraphs ofG The Graph below has 3 SCCs:{a, b, e},{c, d, h},{f, g}Strongly Connected Components (SCC)36 Kosaraju s algorithm Initialize counterc:= 0 While not all nodes are labeled: Choose an arbitrary unlabeled nodev Start DFS fromv Check the current nodexas visited Recurse on all unvisited neighbors After the DFS calls are finished, incrementcand set the labelofxasc Reverse the direction of all the edges For nodevwith labeln, n 1.

10 ,1: Find all reachable nodes fromvand group them as an SCCS trongly Connected Components (SCC)37 Kosaraju s algorithm We won t prove why this works Two Graph traversals are performed Running time: (n+m) Other SCC Algorithms exist but this one is particularly easy tocode and asymptotically optimalStrongly Connected Components (SCC)38


Related search queries