Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Traversal algorithms.
• Marking vertices and edges.
• Three graph implementations and their costs.

Preliminaries

Admin

• Hallow Happyween!
• Friday PSA.

Upcoming Work

• HW (Due Monday): 5-1, 5-2, 5-6, 5-7, 5-13, 5-20, 5-23, 5-28
• Finish chapter 5 for Monday.

Extra Credit

Academic

• R.L. Stephens II events Friday.
• CS Table next Tuesday: Why is everyone so mean on the Internet?
• Sexual Misconduct at Grinnell College: Results from the 2013 and 2015

Peer Support

• Metal Show tonight at 11pm.
• Women's Soccer, Saturday, 11 a.m. vs. Beloit (Senior day!)
• Men's Soccer, Saturday, 1:30 p.m. vs. Beloit (Senior day!)
• Halloween Day on Saturday.

Questions

Traversal algorithms

• Two kinds: Breadth-first and depth-first.
  • Differ in the order in which we visit nodes.
  • In breadth first, you process the neighbors before processing the descendants. (Visit all the nodes one edge away, then all the nodes two edges away, then all the nodes three edges away.)
  • In depth-first traversal, you follow one child as far as you can before proceding on to the next child
  • We can think of each traversal as making a tree.
• How do we implement each? (see below)
• How do the implementations differ from the similar algorithms for trees? (see below)

Breadth-First Search

define bfs(Vertex v) { Queue q = new Queue(); q.enqueue(v); mark(v,"discovered"); while (!q.isEmpty()) { c = q.dequeue(); for each n in c.neighbors() { if (! (marked(n, "processed") || marked(n, "discovered"))) { mark(n, "discovered"); q.enqueue(n); } } mark(c, "processed"); } // while }

define bfs(Vertex v) { bfsKernel(v, new Queue()) }

define bfs(Vertex v, Queue q) { mark(v, "visited"); for each n in v.neighbors() { if (! marked(n, "visited")) { q.enqueue(n); } } // for bfs(q.dequeue(), q); } // bfs

Depth-First Search

Key operations

• mark(Vertex, Mark)
• marked?(Vertex, Mark)
• neighbors iterator

Breadth-First Search (Trees vs. Graphs)

Depth-First Search (Trees vs. Graphs)

Marking vertices and edges

Three graph implementations and their costs

• Edge list: List of all the edges in the graph (and maybe a list of all the vertices)
• Neighbor list: Array/hash of all the vertices, each vertex has a list of its neighbors
• Adjacency matrix: Two-dimensional array. A cell holds the weight of an edge if there is an edge, holds some special value if there is no edge.

What is the cost of the key operations for each of these representations?

• Iterate all the neighbors of a node
• Get the weight of the edge from A to B
• Iterate all of the edges in the graph
• Add a vertex
• Add an edge

Group 1: Edge list Group 2: Neighbor list Group 3: Adjacency Matrix Group 4: Neighbor list Group 5: Adjacency Matrix

In terms of n - number of vertices, m - number of edges

Edge list

• Iterate all the neighbors of a node:
• Get the weight of the edge from A to B: O(m)
• Iterate all of the edges in the graph: O(m)
• Add a vertex: O(1)
• Add an edge: O(1)

Neighbor list

• Iterate all the neighbors of a node:
• Get the weight of the edge from A to B: O(n)
• Iterate all of the edges in the graph: O(n*n), O(n+m)
• Add a vertex: O(1)
• Add an edge: O(1) if we don't have to check, O(n) otherwise

Adjacency matrix

• Iterate all the neighbors of a node:
• Get the weight of the edge from A to B: O(1)
• Iterate all of the edges in the graph: O(n*n)
• Add a vertex: Potentially O(n^2)
• Add an edge: O(1)