Path Checking in Graph

Revision en1, by gXa, 2019-06-07 06:20:01

A graph has N vertices numbered from 1 to N. We have two lists. One list M consisted of edges between vertices. The other list K consists of restricted paths. We have to add edges one by one from M and check whether the addition of the particular edge leads to a path between the restricted edges given in K. If it creates a path, we have to discard the edge.

Example: N = 4; K = {(1, 4)}; M = {(1, 2), (2, 3), (3, 4)}. Here, addition of edge (3, 4) will create a path between 1 and 4. Hence we discard edge (3, 4)

Tags #graph, connected component

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English gXa 2019-06-07 06:20:29 19
en1 English gXa 2019-06-07 06:20:01 543 Initial revision (published)