Computer Science Test 8 Nddc Scholarship

Depth First Search (DFS) is the most natural strategy for solving a maze. In a physical maze, a person can only be in one spot at a time and moves forward along a path until they hit a dead end, at which point they backtrack to the last junction and try a different path.
This is exactly how DFS operates. BFS, while effective for finding the shortest path, would require the 'traveller' to simultaneously explore all possible paths from a junction, which is physically impossible for a single entity in a real-world maze environment.

Breadth First Search (BFS) explores a graph level by level, moving outward from the starting node. Because it visits all nodes at distance 1, then all nodes at distance 2, and so on, the first time it reaches a target node, it is guaranteed to have followed the path with the fewest number of edges.
This makes BFS a perfect shortest-path algorithm for 'un-weighted' graphs (where all edges have an equal cost of 1). DFS does not share this property, as it might explore a very long, deep path to a node before finding a much shorter one.

A forward edge is a non-tree edge \((u, v)\) that connects an ancestor node \(u\) to a descendant node \(v\) that has already been discovered in the search.
Unlike a 'tree edge', which is the first edge used to discover a node, a forward edge provides an alternative, non-essential path 'forward' deeper into the same branch of the tree. Mathematically, it connects a node \(u\) to a proper descendant \(v\) that is not its direct child in the DFS forest. Both options B and D describe this relationship, but D specifically uses the standard terminology 'u is an ancestor of v'.

A Directed Acyclic Graph (DAG) is defined by the absence of back edges during a Depth First Search (DFS) traversal. A back edge is an edge \((u, v)\) where \(v\) is an ancestor of \(u\) in the DFS tree.
Because an ancestor is visited before its descendants, a back edge creates a path from a descendant back to a node currently in the recursion stack, completing a circular path. Therefore, the existence of a back edge is both a necessary and sufficient condition for the existence of a cycle in a directed graph.

Depth First Search (DFS) is the standard algorithm for maze navigation because it follows a single path as deep as possible until it hits a dead end, at which point it backtracks to the most recent junction.
This 'backtracking' method is physically possible for a single person to perform. Breadth First Search (BFS), while mathematically valid for finding the shortest path, would require a person to simultaneously exist in multiple corridors at once to explore 'levels' of distance, which is not feasible in a real-world, physical environment.

Kruskal's algorithm follows a 'Greedy' paradigm. It starts by sorting all the edges of a graph by weight. It then builds the Minimum Spanning Tree by repeatedly picking the smallest available edge that does not create a cycle with the edges already selected.
By making the 'best' local choice (the edge with the minimum weight) at every single step, Kruskal's algorithm is guaranteed to produce a global optimum, which is the spanning tree with the minimum possible total weight.

This is true. Kruskal’s algorithm's complexity is \(O(E \log E)\) or \(O(E \log V)\), meaning its performance is largely determined by the number of edges due to the sorting process.
In sparse graphs, where the number of edges is small (closer to \(V\) than \(V^2\)), sorting the edges is very fast. Prim's algorithm, depending on the implementation, can be more efficient for dense graphs, but for sparse graphs, Kruskal’s simple greedy approach using a Disjoint Set Union (DSU) structure is usually superior.

Strong connectivity in a directed graph requires that there is a directed path from every vertex to every other vertex.
This means that for any two nodes \(u\) and \(v\) in the set of vertices \(V\), you must be able to travel from \(u\) to \(v\) following the direction of the edges, AND you must be able to travel back from \(v\) to \(u\). If this 'vice versa' condition is met for all pairs, the graph is a single strongly connected component.

While it is true that every back edge identifies the existence of a cycle, there is no fixed mathematical formula relating the 'count' of back edges to the 'count' of cycles.
A single back edge might complete several different cycles if there are multiple paths leading to the source of that edge. Conversely, many back edges might exist in a complex graph that contribute to a smaller number of intertwined cycles. Therefore, they are qualitative indicators of each other, but not quantitatively proportional.