What is a graph and what are the differences between directed and undirected graphs? What are basic traversal algorithms?

• A. A graph is a set of vertices and edges; directed graphs have oriented edges; undirected graphs have bidirectional edges; traversals include DFS and BFS.
• B. A graph is a linear sequence of nodes; it has no edges; traversals include sorting.
• C. A graph is a type of database; directed graphs have no edges; traversals include merge.
• D. A graph is a two-dimensional array; edge orientation irrelevant.

Answer: (A)

A graph is made up of vertices (nodes) connected by edges. In a directed graph, each edge has a direction, pointing from one vertex to another, so you can only move along that edge in its specified direction. In an undirected graph, edges connect two vertices without a direction, so you can traverse the edge in either direction.

The basic traversal algorithms are depth-first search and breadth-first search. Depth-first search explores as far as possible along a branch before backtracking, typically using recursion or a stack. It’s useful for tasks like exploring all connected nodes or performing operations that depend on diving deep into a path. Breadth-first search visits neighbors level by level, using a queue, which makes it ideal for finding the shortest path in terms of the number of edges in unweighted graphs.

The direction of edges matters for reachability: in directed graphs, some nodes may not be reachable from others due to edge directions, whereas in undirected graphs you can generally reach connected nodes along edges in either direction. Both traversal methods run in time proportional to the number of vertices plus edges (O(V+E)).