Data Structures and Algorithms - Old Questions

12. Describe strong and weekly connected graphs with examples. What is weighted graph?

A graph is said to be strongly connected if every pair of vertices(u, v) in the graph contains a path between each other. In an unweighted directed graph G, every pair of vertices u and v should have a path in each direction between them i.e., bidirectional path. The elements of the path matrix of such a graph will contain all 1’s. For e.g.

A graph is said to be weakly connected if there doesn’t exist any path between any two pairs of vertices. Hence, if a graph G doesn’t contain a directed path (from u to v or from v to u for every pair of vertices u, v) then it is weakly connected. The elements of such a path matrix of this graph would be random. For e.g.

Weighted Graph

A weighted graph is a graph G, in which each edge, e, is assigned a non-negative real number, w(e), called the weight of e. For e.g.