2. Algorithmic Primitives for Graphs

Question 1

What is a directed graph?

Answer 1

A graph where all the edges are directed from one vertex to another.

Sometimes called a digraph or a directed network.

Question 2

What is an undirected graph?

Answer 2

A graph where all the edges are bidirectional.

Sometimes called an undirected network.

Question 3

Matrix

Answer 3

A rectangular array of numbers, symbols, or expressions, arranged in rows and columns.

Question 4

Tree

Answer 4

Connected undirected graph with no cycles.

Question 5

Connectivity

Answer 5

u and w are connected iff there is a path between them

A graph is connected iff all pairs of vertices are connected

Question 6

Cycle

Answer 6

Sequence of k vertices connected by edges.

The first k-1 edges are distinct.

Question 7

Rooted tree

Answer 7

Pick a node to be the root of the tree and let the rest of the tree hang under “gravity”

Question 8

Distance

Answer 8

Length of the shortest path between u and v

INFINITY represents the distance between two paths which are not connected

Question 9

Breadth First Search (BFS)

Answer 9

Searches a tree or graph at the root (or arbitrary node of a graph) and explores the neighbor (child) nodes first, before moving on to the next level of neighbors (children)

Question 10

BFS Pseudocode (version 1)

Answer 10

for each node n in Graph:

n. distance = INFINITY
n. parent = NULL

create empty queue Q

root.distance = 0
Q.enqueue(root)

while Q is not empty:
current = Q.dequeue()

for each node n that is adjacent to current:
if n.distance == INFINITY:
n.distance = current.distance + 1
n.parent = current
Q.enqueue(n)

Question 11

Adjacency Matrices

Answer 11

A two-dimensional array A, with n rows and n columns, where n = |V|. The entry A[i,j] is equal to 1 if there is an edge joining i and j, and it is equal to 0 otherwise.

Thus, row i of A corresponds to the node i, in that the sequence of 0s and 1s in row i indicate precisely the nodes to which i has edges.

Column i of A performs the same function; notice that since G is undirected, A is symmetric: A[i,j] = A[j,i]

Question 12

Adjacency Matrices

Answer 12

A two-dimensional array A, with n rows and n columns, where n = |V|. The entry A[i,j] is equal to 1 if there is an edge joining i and j, and it is equal to 0 otherwise.

Thus, row i of A corresponds to the node i, in that the sequence of 0s and 1s in row i indicate precisely the nodes to which i has edges.

Column i of A performs the same function; notice that since G is undirected, A is symmetric: A[i,j] = A[j,i]

Question 13

Two flaws of adjacency matrices

Answer 13

1. They are huge objects. They have a size of n^2.
2. Determining the number of edges for any node i takes O(n) because every element in row i has to be checked to see if it’s a 1.

Question 14

Adjacency list

Answer 14

An n-element array V, where V[i] represents node i. V[i] simply points to a doubly linked list Li that contains an entry for each edge e=(i,j) incident to i.

If we want to enumerate all the edges incident to node i, we first locate entry V[i] and then walk through the doubly linked list of edges that it points to. If there are d incident edges, this takes time O(d), independent of n.

Interesting phenomenon, each edge is represented twice. Once as V[i] -> (i,j) and once as V[j] -> (j,i)

Question 15

When is an adjacency matrix better than an adjacency list?

Answer 15

Adjacency matrix (AM) tell us if a pair of nodes contain an edge in constant time.

Question 16

What are the 3 self-proving statements about graphs?

Answer 16

1. G is connected
2. G does not contain a cycle
3. G has n-1 edges

Any two of these statements implies the third.

Question 17

Graph connectivity pseudocode

Answer 17

R will consist of nodes to which s has a path
Initially R = {s}
While there is an edge (u,v) where u w/in R and v !w/in R
Add v to R
Endwhile

Question 18

Connectivity Algo (2.3)
The set R produces at the end of the algorithm consists of precisely the nodes to which s has a path.

Answer 18

Assuming that the set R produces after k steps of the loop contain only nodes reachable from R, then the node added in the (k+1)th step must also be reachable from s.

Consider a node w !w/in R, and suppose by way of contradiction that there is an s-w path in G. Since s w/in R, but w !w/in R, there must be a first node v on P that does not belong to R; and this node v is not equal to s.

Thus, there is a node u immediately preceding v on P, so (u,v) is an edge. Since v is the first node on P that does not belong to R, we must have u w/in R.

It follows that (u,v) is an edge where u w/in R and v !w/in R; this contradicts the stopping rule for the algorithm.

Question 19

Breadth-First Search pseudocode (version 2)

Answer 19

BFS(s):

Mark s as "visited"
Initialize R = {s}
Define layer L0 = {s}
While Li is not empty:
     for each node u w/in Li:
          consider each edge (u,v) incident to v
          If v is not marked "visited" then:
               mark v "visited"
               add v to the set R and to layer Li+1
          endif
      endfor
endwhile

Question 20

BFS algo (2.4)
Let T be a breadth-first search tree, let x and y be nodes in T belonging to layers Li and Lj respectively, and let (x,y) be an edge of G that is not an edge of T. Then i and j differ by at most 1.

Answer 20

Suppose by way of contradiction that i and j differed by more than 1.
Suppose i

Question 21

Depth-First Search (DFS)

Answer 21

Starting at a specified node, a neighboring node is checked to see if it is the sought-after node. If not, the algo checks an unvisited neighbor of that node. This process continues until a dead-end is reached. The algo then moves back to the most recently checked node and checks any of its unvisited neighbors.

This continues until there are no unchecked nodes or until the search query is found.

Question 22

DFS algo (2.5)
For a given recursive call DFS(u), all nodes that are marked "visited" between the invocation and end of this recursive call are descendants of u in T

Answer 22

Observed property - proof not needed.

Question 23

DFS algo (2.6)
Let T be a depth-first search tree, let x and y be nodes in T, and let (x,y) be an edge of G that is not an edge of T. Then one of x or y is an ancestor of the other.

Answer 23

Suppose that (x,y) is an edge of G that is not an edge of T, and suppose without loss of generality that x is reached first by the DFS algorithm.

When the edge (x,y) is examined during the execution, it is not added to T because y is marked “visited.” Since y was not marked “visited” when DFS was first invoked, it is a node that was discovered between the invocation and end of the recursive call DFS(x).

It follows from (2.5) (all nodes marked visited between invocation and end are descendants of u) that y is a descendant of x.

Question 24

Why is the runtime of BFS O(m+n)?

Answer 24

A node is visited (constant time) and each edge incident to the vertex (from the adjacency list), that node is added to the queue as well.
This continues for each node.
Each edge (m) is checked twice and each node (n) is checked once.

2m + n = O(m+n)

Question 25

Why is the runtime of DFS O(m+n)?

Answer 25

IDK