This post is completed by 2 users
|Add to List|
Check if given undirected graph is connected or not
Objective: Given an undirected graph, write an algorithm to find out whether the graph is connected or not.
Graph Connectivity: If each vertex of a graph is connected to one or multiple vertices then the graph is called a Connected graph whereas if there exists even one vertex which is not connected to any vertex of the graph then it is called Disconnect or not connected graph.
Approach: Use Depth-First Search (DFS)
Create a boolean visited  array. Start DFS from any vertex and mark the visited vertices in the visited array. Once DFS is completed check the iterate the visited  and count all the true's. If this count is equal to no of vertices means all vertices are traveled during DFS implies graph is connected if the count is not equal to no of vertices implies all the vertices are not traveled means graph is not connected or disconnected.
Given graph is not connected Given graph is connected
- Prim’s – Minimum Spanning Tree (MST) |using Adjacency List and Priority Queue with decrease key Hard
- Prim’s – Minimum Spanning Tree (MST) |using Adjacency List and Priority Queue without decrease key in O(ElogV) Hard
- Find the nearest building which has bike | Find nearest specific vertex from source in a graph. Hard