CSC152 2006S, Class 51: Graphs
Admin:
* Those of you who have studied this topic in combinatorics should not volunteer too much.
* Reminder: Visitor on Friday.
* EC for attending talk Thursday at 7:30 p.m.
* EC for attending baseball game at 2ish tomorrow
* EC for attending paper-sculpture-dance thing on May 11
* Double EC for setting Danny Zamora on fire (THIS IS A JOKE, DON'T ARREST FOR TERRORISM) (AND BUSH SUCKS)
* EC for Orchestra Concert on Sunday
* EC for attending art show
* EC for attending Emanate concert if they ever get their act together and decide upon a time
* Are there questions on the exam?
Overview:
* Introduction: Modeling in CS.
* One Modeling ADT: The Graph.
* Some Graph Problems.
* A Graph ADT.
* Solving the Reachability Problem.
* Coding the Solution.
The kind of picture we draw for lots of problems should be
represented as an ADT. We call it a "Graph".
* The "places" we call "vertices" (each one is a vertex) (some call them vertexes)
* The connections between places we call "edges" (some folks call them edgi)
* Edges can be directed (one-direction) or undirected (two-direction)
* Edges may have an associated value which we call the "weight" (or cost)
General version of "Get Ian A home cheap": Shortest path
* Given a weighted, directed, graph, and two vertices, source and destination
* Find the sequence of edges that connects source to destination
* Which has the lowest total sum of edge weights
Weightless version of shortest path: Reachability
* Given a directed graph and two vertices, source and destiation,
* Determine whether there is a path from source to destination
The seven bridges of some place Kings town (Koenigsburg)
* Can you cross all of the bridges and return to your starting point?
* In general: Can you visit all of the vertices exactly once and return to your starting point?
* Sam thinks that there is no known efficient solution to this problem.
Variant of "cycle": Traveling Salescritter Problem
* In a weighted, directed graph, find the smallest cycle
* No known efficient solution
In order to code any algorithms we develop, we must have a
graph ADT.
What methods belong in that ADT? (Suppose weighted and directed.)
* makeEdge(Vertex source, Vertex target, int weight)
* Simplifying assumption: Use integers to represent vertices
* makeEdge(int source, int target, int weight)
* removeEdge(int source, int target)
* isEdge(int source, int target)
* Iterator getSources(int vertex)
* Iterator getTargets(int vertex)
* int weightOf(int source, int target)
* compare weight of edges
int cheapestEdge(int source)
How do we deal with the "creation" of vertices?
* When someone refers to a vertex, create it.
* Require the client to specify the vertices in advance [0..n-1]
Let's write
boolean reachable(WDG g, int source, int target)
* For each unmarked successor that follows source
* Mark the successor
* If successor = target, return true
* If not, recurse
* If we ran through all the successors, return false
* Problem: Might recursive infinitely