Graph Algorithms

CS61B, Fall 2002 Discussion #15 Amir Kamil UC Berkeley 12/5/02 Topics: Graph Algorithms 1 Graph Algorithms There are many algorithms that can be applied to graphs. Many of these are actually used in the real world, such as Dijkstra’s algorithm to nd shortest paths. We will discuss a few here. 1.1 Topological Sort Graphs are sometimes used to represent before and after" relationships. For example, you need to think through a design for a program before you start coding. These

two steps can be represented as vertices, and the relationship between them as a directed edge from the rst to the second. On such graphs, it is useful to determine which steps must come before others. The topological sort algorithm computes an ordering on a graph such that if vertex is earlier than vertex in the ordering, there is no path from to . In other words, you cannot get from a vertex later in the ordering to a vertex earlier in the ordering. Of course, topological sort works only on directed acyclic graphs. The simplest topological sort algorithm is to repeatedly remove vertices with in-degree of 0 from the graph. The edges belonging to the vertex are also removed, reducing the in-degree of adjacent vertices. This is done until the graph is empty, or until no vertex without incoming edges exists, in which case the sort fails. 1.2 Dijkstra’s Algorithm Graphs are very often used to represent distances between locations, and an obvious necessity is to nd shortest paths between these locations. Dijkstra’s algorithm can be used to compute shortest paths from a starting vertex to each other vertex. We will discuss rst how to compute shortest distances. Dijkstra’s algorithm is in a class called greedy algorithms. Greedy algorithms work by choosing a local optimum value at each step. In the case of shortest paths, always choosing the local optimum results in the global optimum as well. A starting vertex is chosen, from which all distances will be computed. Each vertex in the graph is assigned a distance value, initially 1 for all but the starting vertex, which is given a distance of 0. Then the vertex with the minimum distance is examined, and any vertices adjacent to the current vertex have their distances updated to the current vertex’s distance plus the edge between the current and the adjacent vertex, if this update will reduce that distance value. Then the vertex with the next minimum distance is examined, and so on. Computation of the actual path is not much harder. Each vertex keeps track of a back edge. When a vertex’s distance is updated, the back edge is set to be an edge between that vertex and the vertex that caused the update. Then to get the path between a vertex and the starting vertex, follow the back edges from back to the start. The from the start to...

Website: www.cs.berkeley.edu | Filesize: -
No of Page(s): 7
Download 1 Graph Algorithms.pdf