COSC 350: Data Structures
April 27, 2009

Graphs

Terms

vertix (set of vertices), edge (set of edges)
directed, undirected,
weight, cardinality,
degree, degree in, degree out
path, cycle, acyclic, directed acyclic graph (DAG)
connected, multiple edges, loops, complete,

Representations and Tradeoffs

Adjacency Matrix—best for dense graphs, matrix is symmetric when graph is not directed, weights vs counts as values, use numarray or numpy in Python
Adjacency List—best for sparse graphs, use dictionaries in python

Homework

Wednesday, April 29:

Revised Sorting Report. Include the original with the revised report.

This page was created by Joe Sloan.
It was last modified on or after: 29 April 2009
Send mail to: sloanjd@wofford.edu