Course topics 10, 11 and 12

Course topic 10

Self-study

The topics for this week are the following: (i) Graphs (ii) Breadth first search, (iii) Depth first search, (iv) Implementing a graph in C++

The following links will take you to the video-lectures and the accompanying slides:

Graphs and Trees

The following three lecture videos were already part of the course topic on trees. However, since they also cover graphs, they are included here as well.

Graphs and Trees: part 1.

Graphs and Trees: part 2.

Graphs and Trees: part 3.

slides for Graphs and Trees

Breadth first search

Breadth first search (part 1)

Breadth first search (part 2)

Breadth first search (part 3)

Breadth first search (part 4)

slides

Depth first search

Depth first search (part 1)

Depth first search (part 2)

Depth first search (part 3)

slides

Implementing graphs in C++

Implementing graphs in C++

slides C++ code

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 with at least two nodes, 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.

Extra links on the topic:

Week10 - Glossary

Submit weekly exercises

Questions to be submitted this week

Self-study

The topics for this week are (i) Weighted graphs and their implmentation in C++, (ii) Dijkstra’s algorithm, (iii) The A-star algorithm and (iv) The efficiencies of graph search algorithms

The following links will take you to the video-lectures and the accompanying slides:

Weighted graphs and their implmentation in C++

video: Weighted graphs

slides C++ code

Dijkstra’s algorithm

video_dijkstra_01: Dijkstra (part 1)

video_dijkstra_02: Dijkstra (part 2)

video_dijkstra_03: Dijkstra (part 3)

slides

There is a mistake in section 4 of the slides used in the video. This mistake is corrected in the slides that you can download.

The A-star algorithm

video_astar_01: A-star (part 1)

video_astar_02: A-star (part 2)

slides

The efficiency of three graph algorithms

video: Graph algorithms’ efficiency

slides

Weighted graphs

Question 1

A weighted graph differs from a normal graph in that …

a weight is associated with each nodes and a node’s weight indicates how expensive it is to go through that particular node.

each edge has a weight, and the weights can be used to search for the cheapest or shortest route from some given node to some other given node.

a weighted graph must not have cycles.

each node has a weight which indicates that largest number of edges that can enter or leave that node.

Question 2

Suppose in C++ for each node \(x\) in a connected weighted graph we use the following vector to contain the adjacent nodes to \(x\) and the weight of each edge.

std::vector< std:pair<Node*,Weight>> to_neighbours;

Suppose we are accessing vector to_neighbours for node \(N\). What does a contain after the following line is executed?

auto a = to_neighbours[0].second;

zero always

a pointer to the second node adjacent to \(N\)

the weight of the edge connecting \(N\) to its first adjacent node

the number of nodes adjacent to \(N\) having zero weight

Dijkstra’s algorithm

Question 1

Dijkstra’s algorithm is most similar to which of the following algorithms?

depth first search

preorder traversal

breadth first search

insertion sort

Question 2

Suppose Dijkstra’s algorithm uses node \(s\) as the starting node. When, in Dijkstra’s algorithm, a node \(v\) having priority \(v.prior\) is extracted from the priority queue, what is the significance of \(v.prior\)?

The path from \(s\) to \(v\) having the fewest number of edges has \(v.prior\) edges.

There is no other node for which a path from \(s\) exists such that the total path length is equal to \(v.prior\).

There is only one path from \(s\) to \(v\) whose total length is equal to \(v.prior\).

The total length of the shortest path from \(s\) to \(v\) is \(v.prior\).

Question 3

Suppose Dijkstra’s algorithm uses node \(s\) as the starting node. What is the purpose of the Relax procedure?

When a new path from \(s\) to some other node has been found, Relax checks whether the total length of this new path is less than the total length of the shortest path that has been found thus far from \(s\) to this other node.

Relax reduces the priorities of all the nodes currently in the priority queue.

When a node \(x\) has been extracted from the priority queue, Relax removes from the graph all edges along the shortest path from node \(s\) to node \(x\).

When a new edge in the graph is first encountered, then Relax adds the edge to the priority queue if the edge’s weight is smaller than the priorities of all other elements in the priority queue.

Question 4

In Dijkstra’s algorithm many quantities or variables are associated with each node \(x\). Which of the following will not change during the execution of Dijkstra’s algorithm?

the position of node \(x\) in the priority queue

the priority associated with with node \(x\)

the node that comes before immediately before node \(x\) in the path from the starting node to node \(x\)

the number of adjacent nodes associated with node \(x\)

The A-star algorithm

Question 1

Suppose we have a directed weighted graph and a starting node \(s\). Which of the following describes one way in which the A-star algorithm and Dijkstra’s algorithm differ?

A-star finds the longest path from \(s\) to some target node, whereas Dijkstra’s algorithm finds the shortest path from node \(s\) to one or more other nodes.

A-star finds the shortest path from \(s\) to one other target node. Dijkstra’s algorithm can find the shortest paths from \(s\) to all other nodes.

A-star will only work when the input graph has no cycles. Dijkstra’s algorithm does not have this restriction.

A-star solves the problem of finding the shortest path from \(s\) to one other node, even when no such path exists. Dijkstra’s algorithm will only solve this problem when a path exists.

Question 2

In the A-star algorithm something is computed that is not computed in Dijkstra’s algorithm. What is it?

A-star needs two priority queues: one where the element with the smallest priority can be extracted quickly and another where the element with the largest priority can be extracted quickly. Dijkstra’s algorithm only needs one priority queue.

A-star needs to compute an upper bound on the number of edges in the shortest path from the starting nodes to the targest node. Dijkstra’s algorithm does not need this upper bound.

A-star needs to compute a lower bound on the length of the shortest path from a given node to the target node. Dijkstra’s algorithm does not need this lower bound.

A-star needs to compute an upper bound on the length of the shortest path from a given node to the target node. Dijkstra’s algorithm does not need this upper bound.

Question 1

What is a central question, related to this course, whose answer can be found in this week’s videos?

Question 2

Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?

Weighted graphs

Dijkstra’s algorithm

The A-star algorithm

The efficiencies of graph search algorithms

Question 3

Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

A site where you can visualize the progress of different graph search algorithms

Week11 - Glossary

Submit weekly exercises

Questions to be submitted this week

Posting submission...