Course topics 10, 11 and 12

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

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 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

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¶

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.

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

Course topics 10, 11 and 12¶

Course topic 10¶

Self-study¶

Graphs and Trees¶

Breadth first search¶

Depth first search¶

Implementing graphs in C++¶

Submit weekly exercises¶

Self-study¶

Weighted graphs and their implmentation in C++¶

Dijkstra’s algorithm¶

The A-star algorithm¶

The efficiency of three graph algorithms¶

Weighted graphs¶

Dijkstra’s algorithm¶

The A-star algorithm¶

Submit weekly exercises¶