Which of these scenarios is BEST represented using a weighted graph?
Storing the friendship relations between people on a social media platform.
Representing the hierarchical structure of a company.
Finding the shortest path between two cities on a road network with distances.
Modeling the flow of information in a computer network.
In a connected graph, a path that visits every edge exactly once is known as:
Critical Path
Shortest Path
Eulerian Path
Hamiltonian Path
Which data structure is commonly used to represent the order of visited vertices during a Depth-First Search?
Queue
Linked List
Stack
Heap
In an undirected graph with 5 vertices, what is the maximum number of edges you can add without creating a cycle?
5
6
4
10
What does a '1' represent in an adjacency matrix of an undirected graph?
The weight of the edge.
The direction of the edge.
The presence of an edge between two vertices.
The degree of the vertex.
In the context of graph traversal, what does 'backtracking' refer to in Depth-First Search (DFS)?
Using a heuristic function to guide the search towards the goal node.
Returning to the parent node after exploring all descendants of a node.
Revisiting already explored nodes to find alternative paths.
Skipping certain branches of the graph to improve efficiency.
A graph is said to be __________ if there is a path from any vertex to any other vertex.
Connected
Bipartite
Disconnected
Complete
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?
Both DFS and BFS have the same efficiency for this task.
Breadth-First Search (BFS)
Neither DFS nor BFS can determine if a path exists between two nodes.
Depth-First Search (DFS)
Removing a vertex from a graph also requires you to remove:
All cycles in the graph.
All vertices connected to it.
All edges connected to it.
The vertex with the highest degree.
In a directed graph, if vertex A has an outgoing edge to vertex B, then:
There must be an edge from vertex B to vertex A.
Vertex A is adjacent to vertex B.
Vertex A and B have the same degree.
Vertex B is adjacent to vertex A.