How does the concept of 'distance' in a weighted graph differ from that in an unweighted graph?
There is no difference; 'distance' has the same meaning in both types of graphs.
In a weighted graph, 'distance' represents the sum of edge weights along a path, while in an unweighted graph, it's the number of edges.
In weighted graphs, 'distance' always refers to geographical distance, while in unweighted graphs, it can represent abstract relationships.
Distance is only defined for unweighted graphs.
In an undirected graph represented using an incidence matrix, what would be the sum of the values in a single column?
1
0
2
V (number of vertices)
Which graph representation is particularly well-suited for representing graphs with parallel edges (multiple edges between the same pair of vertices)?
Edge List
None of the above
Adjacency Matrix
Incidence Matrix
What is the purpose of topological sorting in directed acyclic graphs (DAGs)?
Finding a linear ordering of vertices where for every edge (u, v), u comes before v.
Finding the shortest path between any two vertices.
Determining if the graph has a Hamiltonian cycle.
Calculating the minimum spanning tree of the graph.
Kruskal's algorithm sorts edges in ascending order of their weights. What data structure is typically used for this sorting step?
Queue
Linked List
Stack
Heap
Which of the following operations is typically less efficient with an edge list representation compared to an adjacency matrix?
Finding all edges connected to a specific vertex
Determining the degree of a vertex
Checking if the graph is connected
Adding a new edge
In a GPS navigation system, what graph algorithm is commonly used to find the shortest route between two locations represented as nodes on a road network?
Topological Sort
A* Search Algorithm
Floyd-Warshall Algorithm
Dijkstra's Algorithm
You are designing a social network and want to recommend friends to users. What graph algorithm would be most suitable for identifying potential friends based on shared connections?
Breadth-First Search (BFS)
Depth-First Search (DFS)
Bellman-Ford Algorithm
Which algorithm efficiently calculates the shortest paths between all pairs of nodes in a weighted graph, useful for analyzing network connectivity in social networks?
Kruskal's Algorithm
In a graph with a large number of vertices but relatively few edges (sparse graph), which representation would be most space-efficient?