What does a '1' represent in an adjacency matrix of an undirected graph?
The direction of the edge.
The presence of an edge between two vertices.
The weight of the edge.
The degree of the vertex.
You remove an edge from a connected graph. What is a possible consequence of this action?
The graph may become disconnected.
The number of cycles in the graph will always decrease.
The number of edges and vertices in the graph will decrease.
The graph will always become disconnected.
In an undirected graph with 5 vertices, what is the maximum number of edges you can add without creating a cycle?
5
10
6
4
Which of the following graph representations is most efficient for checking if two vertices are adjacent?
Edge List
Adjacency Matrix
Incidence Matrix
Adjacency List
What is the degree of a vertex in a graph?
The total number of vertices in the graph.
The length of the longest path starting from that vertex.
The number of edges connected to that vertex.
The number of self-loops on that vertex.
You are performing a Breadth-First Search on a graph. Which of the following best describes the order in which vertices are visited?
Increasing order of their degree (number of connections)
Random order
Vertices at the same distance from the source vertex are visited before moving to vertices further away
Alphabetical order
Which algorithm is typically used to find the shortest path in a weighted graph where edge weights are non-negative?
Bellman-Ford Algorithm
Breadth First Search (BFS)
Dijkstra's Algorithm
Depth First Search (DFS)
How does the iterative implementation of Depth-First Search (DFS) typically differ from its recursive counterpart?
The iterative approach is generally less efficient in terms of space complexity than recursion.
The iterative approach is not suitable for traversing graphs with cycles.
The iterative approach uses a stack to mimic the function call stack used in recursion.
The iterative and recursive approaches produce fundamentally different traversal orders.
Consider a graph where you want to find if a path exists between two given nodes. Which traversal algorithm would be generally more efficient for this task?
Depth-First Search (DFS)
Both DFS and BFS have the same efficiency for this task.
Neither DFS nor BFS can determine if a path exists between two nodes.
Breadth-First Search (BFS)
Which of the following scenarios is particularly well-suited for applying a Depth-First Search (DFS) algorithm?
Solving mazes or navigating through grid-based environments.
Simulating the spread of information or a virus in a social network.
Finding the shortest path between two locations on a map.
Crawling and indexing web pages starting from a seed URL.