Graphs：練習問題

In the context of graph theory, what is the defining characteristic of a weighted graph?

Which graph traversal algorithm uses a stack (either explicitly or via recursion) to explore as far as possible along each branch before backtracking?

In an algorithm designed to navigate a maze, why is Depth-First Search (DFS) often preferred over Breadth-First Search (BFS) if the goal is simply to find any path to the exit rather than the shortest one?

A directed graph has 5 vertices. What is the maximum number of edges this graph can have, assuming no more than one edge exists between any two vertices in the same direction and there are no self-loops?

When comparing an adjacency matrix to an adjacency list for representing a directed graph with \( V \) vertices and \( E \) edges, what is the time complexity required to determine if a specific edge exists between vertex \( i \) and vertex \( j \) in the matrix representation?

An adjacency matrix is used to represent an undirected graph with 5 vertices. How many cells in the matrix must be updated if a single new edge is added between two existing vertices?

A directed graph is represented using an adjacency matrix. If there are \( n \) vertices and the matrix is sparse, what is the space complexity of this representation, and why might an adjacency list be preferred for such a graph?

A programmer needs to decide between an Adjacency Matrix and an Adjacency List for a graph with 5,000 vertices and only 6,000 edges. Identify which structure is more memory-efficient and justify why.

An unweighted graph is represented using an adjacency matrix.

(a) Define what an adjacency matrix is and how it represents edges between vertices.
(b) State one advantage of using an adjacency list over an adjacency matrix for a sparse graph.
(c) If an undirected graph has 4 vertices (A, B, C, D) and edges (A,B), (B,C), (C,D), draw the corresponding adjacency matrix (assume 1 for edge, 0 for no edge).

A programmer is choosing between an adjacency matrix and an adjacency list for a graph representation.

(a) Define a weighted graph and explain how weights are stored in an adjacency matrix compared to an adjacency list.

(b) For a sparse graph with \( V \) vertices and \( E \) edges, justify which representation is more memory-efficient using Big-O notation for space complexity.

(c) State the time complexity for checking if an edge exists between two specific nodes in both representations.