| home page - news - syllabus - topics - schedule - assignments - tutorials - tests - java - references - Mike Jacobson |
| Introduction - Correctness of Algorithms - Analysis of Algorithms - ADTs, Stacks, Queues - Dictionaries - Searching and Sorting - Graph Algorithms |
| Graph Algorithms |
Graphs are commonly used in computer science to represent communications networks and other types of networks, as well as data and information structures. There are numerous interesting computational problems involving graphs.
Approximately the last three weeks of lectures will be devoted to a study of representations and computations on graphs.
We will begin with basic definitions and terminology for graphs as well as two commonly used representations of graphs on computers, namely, “adjacency-matrix representations” and “adjacency-list representations” of graphs. Notes based on the lecture presentation of this topic are now available.
Algorithms for search in graphs, including the “breadth-first search algorithm” and the “depth-firat search algorithm” will be studied next. Lecture notes on breadth-first search and depth-first search are now available.
A tutorial exercise on representations of graphs, and breadth-first search, is now available. Another tutorial exercise with additional problems on breadth-first search, as well as problems concerning depth-first search, is now available too.
Algorithms for the computation of spanning trees of weighted graphs will be considered after this. A first , second , and second set of lecture notes on this topic are now available.
This barely scratches the surface: There are numerous other graph problems and of interest. A brief survey of some of these will presented at the end of the course.
Section B.4 and B.5in Appendix B introduces undirected and directed graphs, along with a variety of basic definitions. It will be assumed that students have read and understood this material.
Graphs are studied for several weeks in Mathematics 271 as well. Hence most textbooks for this course include additional material about basic graph properties. In particular, Chapter 11 of Susaana' S. Epp's text “Discrete Mathematics with Applications” (Third Edition) can be consulted as a reference for these.
Finally, Chapters 22–23 include the material that will be presented in lectures on this topic. Additional chapters, including chapters 24–26, include additional problems and algorithms that would be included in this course if more time was available.
After studying this topic in this course (including attending lectures, completing assigned reading and working through the exercises), students should understand and be able to do the following.
Students should know the definitions of undirected, directed and weighted graphs. They should also be familiar with (and able to use) common graph notation and terminology.
Students should be able to explain the algorithms for graph searches, and computation of spanning trees that have been presented in lectures — using simple English or pseudocode.
Students should be able to apply the above algorithms by hand on small examples.
Students should be able to explain (at least, informally) why these algorithms are efficient and correct. They should also be able to describe the number of operations used by these algorithms.
Given sufficient time students should be able to write programs in Java that implement the above algorithms.
What is an undirected graph? What is a directed graph? What is a weighted graph?
What does it mean for a graph to be “dense”? What does it mean for a graph to be “sparse”?
What are “adjacency-matrix” and “adjacency-list” representations of graphs? Under what circumstances is each representation a better choice than the other?
What is a “breadth-first” search in a graph? What is a “depth-first” search?
Which basic data type (discussed much earlier in this course) is useful when each of these search algorithms is implemented?
What is the worst-case cost of each search?
What is a “minimum-cost spanning tree” for a (connected) weighted graph? How can this be computed? What is the worst-case running time of the algorithm for this computation that was presented in class?
What other graph problems are of interest? (You should be able to name at least a few of these.)
What is known about the worst-case cost to solve the problems you have mentioned?
|
This page last modified:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/W07/topics/graph_algorithms.html |