GRAPH TRAVERSAL

Which statement best defines graph traversal in computer science?

• A method for drawing graphs on a plane without edge crossings

• The process of visiting all vertices (nodes) and edges of a graph in a systematic manner

• A technique for storing graph data in adjacency matrices

• An approach to compressing network data for faster transmission

In a graph, what are vertices and edges respectively?

• Vertices are lines; edges are points

• Vertices are points; edges are lines connecting points

• Vertices are weights; edges are labels

• Vertices are directions; edges are routes only in directed graphs

Select the applications that directly illustrate the importance of graph traversal.

• Finding connections in social networks

• Indexing webpages using web crawlers

• GPS path navigation

• Formatting text in a word processor

Why is graph traversal considered essential in computer science according to the material?

• It guarantees minimal memory usage for all graph problems

• It forms the basis for solving tasks like searching, pathfinding, and network analysis

• It replaces the need for data structures such as queues and stacks

• It is only relevant for undirected graphs

Which goal is NOT typically associated with graph traversal algorithms as presented?

• Finding a path between nodes

• Determining connectivity within the graph

• Analyzing relationships in the graph

• Rendering 3D graphics with shaders

What is an algorithm in graph traversal?

• A random walk used to sample nodes periodically

• A step-by-step procedure with clear rules to systematically explore all nodes and edges

• A hardware accelerator for graph computation

• A visual diagram that labels vertices and edges

Which statements correctly describe the role of rules in a graph traversal algorithm? Select all that apply.

• Rules specify how to visit nodes to achieve goals like finding paths

• Rules ensure edges are colored differently for readability

• Rules help determine connectivity among nodes

• Rules define relationships to be analyzed within the graph

Choose the most accurate summary of why learning graph traversal benefits problem-solving across domains.

• It enables problem-solving in areas like artificial intelligence, network security, and resource optimization by exploring and analyzing graph structures

• It primarily improves spreadsheet formulas and email filtering

• It guarantees every optimization problem has a unique solution

• It eliminates the need for algorithms in databases

Which statement best captures the defining behavior of Depth-First Search (DFS)?

• It visits all neighbors of a node level by level before moving deeper.

• It explores as far as possible along one branch before backtracking to explore other branches.

• It randomly samples nodes to avoid getting stuck in cycles.

• It prioritizes nodes with the smallest degree first.

In DFS, what data structure is used to keep track of the next vertices to visit?

• Queue, maintained in FIFO order

• Priority queue, ordered by edge weights

• Stack, either explicitly or via recursion

• Hash table, keyed by vertex labels