Algorithms, Data Structures and Computability: Counting Islands Problem

The chapter discusses how to find the shortest path between two nodes in an undirected graph.

The problem of finding connected components in a graph is the same for both undirected and directed graphs.

The goal of finding connected components in a graph is to determine which areas are cut off from a power generator.

The graph shown in Figure 21.1.1 has two connected components.

Analyzing the complexity of algorithms is important to support software design choices.

The chapter assumes the reader has no prior knowledge of graph-related concepts and algorithms.

Two land squares belong to the same island if they are diagonally adjacent.

The image grid uses the letter W to represent water squares.

The problem of counting islands on a satellite image is most similar to a sorting problem.

The input format for counting islands is a list of integers instead of a list of strings.

Islands are defined as vertically or horizontally adjacent land squares.

The pathfinding algorithm needed to solve the island counting problem is Dijkstra's algorithm.

In the BFS algorithm for the knight moves problem, it is more efficient to add edge (A, B) with the length of the path to B to the queue.

When solving graph problems, it is recommended to invent a new graph algorithm instead of modeling the problem with a graph that allows you to apply a standard graph algorithm.

Nodes in graph theory can only represent places and tasks, but not events or states.

Edges in a graph can only be weighted, not directed.

The complexity of transforming input into a graph and applying a graph algorithm is always Θ(n^2 + e).

For the BFS algorithm used in a specific problem, the overall complexity is Θ(2n + 2e).

A weakly connected component of a digraph is a largest possible subgraph of mutually reachable nodes, if we ignore the direction of ______.

These components can be found by computing the connected components of the undirected version of the ______.

The worst-case complexity of finding strongly connected components in a digraph is Θ(n×(n+______)).

The reverse graph of a digraph represents the inverse relation of the original graph, e.g. 'A follows B' becomes 'B is followed by ______'.

A topological sort of a directed acyclic graph (DAG) is a permutation of its nodes so that for every edge A−→B, node A comes before node B in the ______.

Kahn’s algorithm computes a topological sort in a ______ fashion.

In each iteration, Kahn’s algorithm (virtually) removes one node with in-degree zero from the digraph and appends it to an initially empty ______.

If the digraph has a cycle, Kahn’s algorithm returns a sequence without all the graph’s nodes, thus making it easy to detect cycles in ______.

A DAG has one or more topological ______.

Cyclic digraphs have no topological ______.