What does a '1' represent in an adjacency matrix of an undirected graph?
The degree of the vertex.
The presence of an edge between two vertices.
The weight of the edge.
The direction of the edge.
In an undirected graph, if the sum of the degrees of all vertices is 30, how many edges are there in the graph?
30
Cannot be determined.
15
60
Which of the following is NOT a characteristic of a bipartite graph?
It can be used to model matching problems.
Edges can only connect vertices from different sets.
It can have an odd-length cycle.
Vertices can be divided into two disjoint sets.
Which data structure is commonly used to represent the order of visited vertices during a Depth-First Search?
Heap
Linked List
Stack
Queue
In the context of Breadth-First Search (BFS), what does it mean for a node to be at 'level i' from the starting node?
The node has a priority value of 'i' in the BFS traversal order.
The node has 'i' neighbors in the graph.
The node is at a distance of 'i' edges away from the starting node.
The node is the i-th node discovered by the BFS algorithm.
A graph where edges have a direction associated with them is called a:
Weighted Graph
Directed Graph
Cyclic Graph
Undirected Graph
How does the iterative implementation of Depth-First Search (DFS) typically differ from its recursive counterpart?
The iterative approach is not suitable for traversing graphs with cycles.
The iterative and recursive approaches produce fundamentally different traversal orders.
The iterative approach is generally less efficient in terms of space complexity than recursion.
The iterative approach uses a stack to mimic the function call stack used in recursion.
In a directed graph, if vertex A has an outgoing edge to vertex B, then:
Vertex A is adjacent to vertex B.
Vertex B is adjacent to vertex A.
There must be an edge from vertex B to vertex A.
Vertex A and B have the same degree.
Which of the following scenarios is particularly well-suited for applying a Depth-First Search (DFS) algorithm?
Finding the shortest path between two locations on a map.
Crawling and indexing web pages starting from a seed URL.
Simulating the spread of information or a virus in a social network.
Solving mazes or navigating through grid-based environments.
Which data structure is most efficient for checking if an edge exists between two vertices in a sparse graph?
Adjacency Matrix
Adjacency List