Description
1. Consider the directed graph shown below in Fig. 1
(a) (10 pts) Perform breadth first search (BFS), starting from node 1 and draw the tree on the
figure and label each node by the depth of the node, d(i), and its parent (or predecessor), p(i)
for i = 1, 2, · · · |E|. Give a list of the order in which the nodes leave the queue. Assume that
arcs out of a node will be examined in order of increasing end node; i.e. break
ties in order of arc selection by examining the arc with the smallest value of end
node first.
(b) (10 pts) For the same directed graph in Fig. 1 , use depth first search (DFS), starting from
node 1. Give two lists for the order in which nodes entered into the stack and the
order they leave the stack. (An extra figure is appended to this Homework below.) Draw
the stack in enough detail to understand its function. Again assume that arcs out of a
node will be examined in order of increasing end node; i.e. break ties in order of
arc selection by examining the arc with the smallest value of end node first. Is the
reverse order a topological sort? (Explain)
Figure 1
1
Figure 1
Figure 1
2
2. (10 pts) Compute a minimum spanning tree for Fig. 2 below, and evaluate the weight of that
spanning tree using Kruskal’s algorithm. Draw the tree and list in order the edges that are added
to arrive at the tree. (HINT: You may check this by using Prim’s algorithm, which will get the
same MST but of course the order of adding edges is very different.)
10
1
2
3
4
5
6
7
8
9
10
11
3
13
1
17 8
4
14
15 7
5
20
17
16
12
11
4 6
30
Figure 2:
3
3. (20 pts) This is a forward star representation for a directed graph with |V | = 11 vertices and
|E| = 16 edges.
Vertex Number: 1 2 3 4 5 6 7 8 9 10 11 12
Array First: { 1, 3, 4, 5, 7, 8, 12, 12, 14, 14, 15, 17 }
Edge Number: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
Array Edge: { 2, 6, 6, 7, 3, 7, 8, 5, 8, 9, 10, 9, 11, 9, 9, 10, -1 }
(a) Draw the graph on the template in Fig. 3. (HINT: You may want to do part b first.)
1
2
4
5
6
8
9
1
1
7 10
3
Figure 3:
(b) Represent this graph as an adjacency list.
(c) Is this graph a DAG?
4
4. An undirected bipartite graph G(V, E) is one where its nodes can be partitioned into two disjoint
sets V = V1 ∪ V2, such that that every edge e ∈ E is an arc {v1, v2}, where v1 ∈ V1 and v2 ∈ V2.
Note that, in a bipartite graph, the length of every cycle must be an even number.
Define a pseudo code for an algorithm to determine whether an undirected graph is bipartite with
worst case complexity O(m), where m is the number of edges in the graph.
5. While Euler’s theorem gives a characterization of planar graphs in terms of numbers of vertices,
edges and faces, it is hard to establish whether a graph is planar or not if it is difficult to count
faces. There are a couple of other properties of simple, connected planar graphs that derive from
Euler’s theorem:
• A simple, connected planar graph with n ≥ 3 vertices and e edges must satisfy e ≤ 3n − 6
• A simple, connected planar graph with n ≥ 3 vertices, e edges and no cycles of length 3 must
satisfy e ≤ 2n − 4
A popular architecture for parallel computers is a hypercube. A hypercube of dimension k, denoted
by Qk, has 2k nodes, and each node is connected to k other nodes. The nodes can be embedded into
a k-dimensional boolean vector, and nodes are connected to other nodes that differ along one of
its coordinates. Thus, Q2 has nodes (0, 0),(0, 1),(1, 0),(1, 1), and has 4 edges. The node (0,0) is connected to (0,1) and (1,0). Q3 has nodes (0, 0, 0),(0, 0, 1),(0, 1, 0),(0, 1, 1),(1, 0, 0),(1, 0, 0),(1, 1, 0),(1, 1, 1).
Node (1,1,1) is connected to nodes (0,1,1), (1,0,1) and (1,1,0). Note that the number of edges in a
hypercube of dimension k is k ∗ 2
k−1
, since each node has k edges, and we divide by 2 so as not to
count the number of arcs twice. Other important facts about hypercubes is that every hypercube
is a bipartite graph.
(a) Using the above facts, verify that Q3 is a planar graph.
(b) Using the above facts, show that Q4 cannot be a planar graph.
6. Suppose you have computed a minimum spanning tree T for a graph G(V, E). Assume you now
add a new vertex n and undirected arcs En = {{n, vi}, for some vi ∈ V }, with new weights
wnvi
. Provide the pseudocode for an algorithm to find the minimum weight spanning tree in the
augmented graph Ga(V ∪ {n}, E ∪ En). Estimate the complexity of this algorithm.
5
7. (20 pts) An undirected graph G(V,E) is defined interm of two arrays: First[0:Vsize] and
Edge[0:Esize] that label the Vertice(nodes) from 0, 1, · · · , V size − 1 and Edges (arcs) from
0, 1, · · · , Esize − 1 respectively. The last “fake” vertex ( Frist[Vsize] = Esize) point to the
null “fake” edge with ”null” value ( Edge[Esize] = -1), See Exercise 3 above for an small example.
Implement your algorithm as a C/C++ function that counts the number of connected components.
On GitHub there is the main file that reads input and writes output the result. You only write the
required functions. A code makeGraph.cpp has been posted that generates “random” undirected
graphs, which you use for you amusement if you want to test your algorithm small or large graphs
of varying sparsity.
Your connected component function needs to call over and over again a Grow(…) function
using either BFS (or DFS) until you have visited all the nodes in the graph. It is preferable to use
BFS as a more efficient way to grow each connected componet from its start node. The functions
for BFS have been included. The number of time you call Grow(..) is the number of connected
components. All you need to return is one extra a global array Found[0:Vsize] initialize to −1
for not found and then set to something else when each node is visited so your next call to search
Grow(..) goes only to nodes that have been left out.
The task is to first implement connected components with BFS and a Queue and then to add to
the code another function doing DFS using a stack.
Write the function:
int find_connected_components_BFS()
Stack * createStack()
Push(..)
Pop(..)
int find_connected_compoents_DFS()
Find the number of time and connected components using BFS and then add the find DFS method
so you can compare the time of execution and show that the number of connected components are
the same of course!
Do not make any changes to the infield reading format. so that it easy for the grader to run you
code against a set of input files to test the code correctness. When you implement the DFS version
the outfile writing format in main() You are given as set of input graphs and few solutions.
Analysis For extra credit if you pick the label found as a distinct number inside each connected
component (e.g. 1, 2, · · · , NumberConnectCompoents), you can learn a lot more – like how many
live in the largest most popular cluster etc.
Let’s discuss more extension class and how to graph resutls. Might lead to a fun project as well.
More fun on conected components
Google look at the curious
Regular graphs
Cluster finding variations etc
6
