Notes for Tuesday November 30, 2004

• Return to the main FrontPage.

• Scribe = Kathy King
• Editor =

What's coming up

• Tue, 11/30 (today) - graph algorithms, WrittenAssignment6 to be posted later today

• Fri, 12/3 - NP completeness
• Tue, 12/7 - Allen Downey lecturing on programming languages

• Fri, 12/10 - summary of semester, feedback, WrittenAssignment6 due

• Tue, 12/14 - no regular class (although maybe optional review session), Final Exam posted

• Fri, 12/17 - Final Exam due by 4 pm (official final slot: 1:00 - 4:00, Friday)

Graphs: the Basics

• Graphs have two parts:
  • vertices (sometimes called nodes)
  • edges (which connect vertices)
    • Edges can be directed or undirected (an undirected edge is the same as having 2 directed edges, one pointing each direction
    • Edges can be weighted or unweighted (having unweighted edges just means that all of the edges have the same weight)
• Trees are a special kind of directed graph
• What can be represented as a graph? Lots of stuff! Here are a few examples:
  • Games! Like Tic-Tac-Toe or Towers of Hanoi
    • For games like these, a vertex is used to represent each game state (which would be the particular configuration of disks in Towers of Hanoi, or the layout of x's and o's in Tic-Tac-Toe)
    • Legal moves would be represented by edges connecting different vertices
  • Maps (each state is a vertex, and adjacent states are connected by an edge)
  • Networks (graphs can represent friend-of-a-friend mappings and six degrees of separation or six degrees from Kevin Bacon, not to mention the Internet and telephone networks)
  • RDF (which allows you to talk about the relationships between different things
    • Here's an example:

The code: 
 <course id = "FOCS">
     <student>
       Chris
     <\student>
     <student>
       Kathy
     <\student>

is a text-based representation of this graph (where "FOCS", "Chris", and "Kathy" are the names of vertices):

                 Chris 
                 /
                /student
               /
            FOCS
               \
                \student 
                 \
                Kathy

• Complexity of a graph varies relative to its vertices and edges

  • In a fully connected (or complete) graph, each vertex is connected to every other vertex. In this case, the number of edges (e) is proportional to the number of vertices (v) squared. So, e ~ v^2.

  • In a not very connected graph, where each vertex is connected to few (or no) other s, the number of edges is often less than the number of vertices. So, e < v.

  • For particular graph algorithms, we want to specify whether the number of steps taken by the algorithm is proportional to e, v, or some function of both.

Searching in Graphs

Sometimes, we want to determine whether a particular element is in a graph. This requires that we need an efficient way to step through each vertex of the graph. We can use a breadth first search or a depth first search to do this.

Breadth First Search

In doing a breadth first search, we will change our graph into a tree by keeping all of the vertices in the graph, but only some of the edges.

• Given a graph, we pick a starting vertex
• Then, we go to all of the things adjacent to our starting vertex. We place these vertices in a queue.
• We then take the first element from the queue and go to all of the vertices that are adjacent to it (that have not already been visited).
• We continue like this until we have gone through all of the vertices in the graph.

Depth First Search

• Again, pick a starting vertex. Add it to a queue.
• Then, go to an adjacent vertex. Add it to your queue.
• Choose a vertex adjacent to the last vertex which has not already been visited. Add it to the queue. Repeat this step until you cannot visit any vertices that you have not already visited.
• Then, get your starting vertex out of the queue, and go to another vertex adjacent to it that has not already been visited. If this is not possible, take the next vertex out of the the queue and try. Continue this until you find a vertex adjacent to at least one unvisited vertex.
• Now, repeat the earlier steps (pick a string of adjacent vertices until you can no longer do so, adding each one to the queue, etc.) until there are no unvisited vertices in the graph

Complexity of Searching Graphs

• The complexities of breadth and depth first searches are the same...? (Could someone please correct this or flesh it out? I was away from the class room when this was discussed. Thanks.)

Minimum Spanning Trees

Weighted edges can be used to indicate the distance between two objects (represented as nodes), or perhaps the cost or desireablity of connecting them. Because of this, it is sometimes desireable to know create a spanning tree of the graph. A spanning tree of a graph is a subset of the graph in which all of the vertices are connected. In a minimum spanning tree, the edges are chosen such that the sum of the edge weights is minimized. A maximum spanning tree is when the sum of the edge weights is maximized. Special algorithms have been created to find these trees.

Prim's Algorithm: how it works

Prim's Algorithm is a greedy algorithm that can be used to find the minimum spanning tree of a graph. Here's how:

• Pick any vertex
• Connect it to one of its adjacent vertices by its lowest weighted edge. (If there are more than one edges with the minimum weight, select one randomly.)
• Now, out of all the vertices adjacent to either of those selected, choose the one (or one of the ones) connected by the lowest weighted edge.
• Continue in this manner until all of the vertices have been included in the graph.

About Prim's Algorithm

• It is okay to be greedy here (pick the best thing at each step) because this will only eliminate worse choices; you won't get into trouble. We're making local decisions, so what we do now will not affect the possibilities open to us in the future.
• Kruskal's Algorithm is another greedy algorithm that can find minimum spanning trees. It is similar in complexity.
• Also, note that maximum spanning trees may be found with this algorithm; you simply choose the highest weighted edges rather than the lowest ones.
• To do Prim's algorithm, we basically need to do two things:
  • List the transitions that are available at each step
  • Choose the least cost one (lowest weighted edge)

• We can do this in ev steps or elog(e) steps.

Single Source Shortest Path: Dijkstra's Algorithm

It is often desireable to know the shortest path on a graph. Dijkstra's Algorithm works on directed graphs (which means that it will also work on undirected graphs, if you just put two directed edges in place of each undirected one). The best way to understand how it works is to look at the demo we saw in class.

Demo from class: http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/DijkstraApp.shtml?demo2

Miscellaneous

• All Pairs Shortest Path is another method we should be familiar with. Basically, for any first and second vertex, the algorithm checks to see if there exists a third vertex that would shorten the path.
• Dynamic program is important here, because it lets you keep track of intermediate steps, and see whether anything improves.
• All of these methods are linear or polynomial in e, v.

Reading

Corman - ch 22, 23, and 24 (through 588, and then pgs 595-601)