Course week 10

Question 1

Which of the following statements are true? (More than 1 statement may be true.)

If a path exists from node \(x\) to node \(y\), then an edge exists from \(x\) to \(y\).

In an undirected graph, if a path exists from node \(x\) to node \(y\), then a path exists from a path exists from \(y\) to \(x\).

An undirected graph can have a cycle, but a directed graph cannot.

In a directed graph, if an edge from node \(x\) to node \(y\) exists, then an edge from \(y\) to \(x\) must exist.

Each tree is a graph, but not all graphs are trees.

Question 2

Which of the following statements are true regarding connected graphs? (More than 1 statement may be true.)

In a connected graph there exists an edge from each node \(x\) to every other node \(y\).

In a connected graph, each node has at least one edge connected to it.

An unconnected graph has at least one node that has no edges connected to it.

If a graph is connected and there is no edge between nodes \(x\) and \(y\), then the path to get from \(x\) to \(y\) has at least 2 edges.

Question 1

Given a directed graph, in which of the following situations would a breadth first search (BFS) be useful?

When one wants to find the path of smallest length from one particular node to all other nodes.

When one wants to find the path of longest length from one particular node to some other particular node.

When one wants to find the shortest cycles in a graph.

When one wants to find the node having the largest number of adjacent nodes.

Question 2

Suppose a directed graph has 4 nodes \(s\), \(a\), \(b\) and \(c\). Suppose in addition the graph has all possible edges except 2: the edge from \(s\) to \(a\) and the edge from \(a\) to \(b\). What are the distances from \(s\) to each of the other nodes?

from \(s\) to \(a\) 2, from \(s\) to \(b\) 2, from \(s\) to \(c\) 1

from \(s\) to \(a\) 1, from \(s\) to \(b\) 2, from \(s\) to \(c\) 1

from \(s\) to \(a\) 2, from \(s\) to \(b\) 1, from \(s\) to \(c\) 2

from \(s\) to \(a\) 2, from \(s\) to \(b\) 1, from \(s\) to \(c\) 1

Question 3

Suppose a BFS algorithm starts from node \(s\). Suppose \(x\) is some other node and a path from \(s\) to \(x\) exists. Why does the BFS algorithm assign different colors to \(x\)?

To indicate the number of adjacent nodes to \(x\).

To monitor whether the path from \(s\) to \(x\) has been discovered and whether \(x\) has been completely processed.

To ensure that when BFS is finished no two adjacent nodes have the same color.

To ensure that in the queue used by BFS, no two nodes have the same color.

Question 4

Suppose a directed graph is input to a BFS algorithm. In addition suppose that BFS starts from node \(s\) and that a path from \(s\) to each other node exists. When BFS has finished executing, which of the following are true? (Note: more than one statement might be true.)

The queue in BFS contains all the nodes.

From the results of BFS we can form a path from \(s\) to any other node.

BFS ensures that no two nodes have the same color at the end of executing.

For each node other than \(s\), BFS has computed a positive distance.

Question 1

Given a directed graph, in which of the following situations would a depth first search (DFS) be useful?

When one wants to find all the paths from one particular node to another particular node.

When one wants to find out, whether there are cycles in the directed graph or not.

When one wants to find the longest path from one particular node to another particular node.

When one wants to find all the paths of a certain length from one particular node to another particular node.

Question 2

In the DFS algorithm a stack is used. Suppose \(x\) and \(y\) are two different nodes in a directed graph. According to what rule does the DFS stack operate?

If \(x\) is the topmost node on the stack and we want to add \(y\) to the stack, we must first remove \(x\) from the stack.

If an edge from \(x\) to \(y\) exists, then \(x\) and \(y\) will never be on the stack at the same time.

If both \(x\) and \(y\) are on the stack at the same time and \(x\) has been added to the stack before \(y\), then \(x\) will be removed from the stack before \(y\).

If both \(x\) and \(y\) are on the stack at the same time and \(x\) has been added to the stack before \(y\), then \(y\) will be removed from the stack before \(x\).

Question 1

Suppose we are storing a graph in C++ and we have a node struct, in which we store all the adjacent nodes in either a vector container or an unordered_set container. In what situtation would it make sense to prefer an unordered_set over a vector?

When each node in the graph has at most 1 adjacent node and the adjacent node never changes .

When edges are very often added to the graph or deleted from the graph.

When we must always process all the adjacent nodes to any given node in some particular order.

When each node is assigned a name and the name never changes.

Question 2

When implementing a graph in C++, which of the following is true?

One should always use the available std::graph-structure container from STL.

A node should always allow for some color to be assigned to it.

There is only one correct way to store the nodes that are adjacent to a given node.

For each node, some storage is needed for all the nodes that are adjacent it.

Course week 10¶

Self-study¶

Graphs and Trees¶

Breadth first search¶

Depth first search¶

Implementing graphs in C++¶

Submit weekly exercises¶