Given a graph G and a subset of vertices A, write an efficient algorithm that prints, if they exist, two sets B, C subsets of V such that:(continue)

Viewed 52

Given a graph G and a subset of vertices A, write an efficient algorithm that prints if they exist, two sets B, C subsets of V such that:

  1. B intersected C is a subset of A
  2. Each vertex of B has a path that reaches at least one vertex of A
  3. Each vertex of C is reachable from at least one vertex of A

my solution(I'm not sure of it) The idea is to construct B by verifying which are the vertices that reach at least one vertex in A through a DFS_Visit on the transposed graph. I construct in a similar way, but on the non-transposed graph, the set C. Finally, I paint the vertices of A with a color that is neither white nor gray nor black, for example, red. If there are vertices that are in both B and C but not A, I return false. If the sets do not exist, the absence of a solution must be reported some pseudocode

Algo(G,A)
    B = C = empty
    
Init(G,A,c1,c2)

Gt = traspose(G)

for each a in A do
    if c1[a] = c2[a] = B then
        DFS_Visit(Gt,a,c1)
        DFS_Visit(G,a,c2)
        
for each v in V do
    if c1[v] = N then
        B = B U {v}
    if c2[v] = N then
        C = C U {v}
        
for each v in V do
    if c1[v] = c2[v] = N and c3[v] != Red then
        print "A and B not exist"
        return false
    
Stampa(B,C)
return true


Init(G,A)
    for each v in V do
        c1[v] = c2[v] = B
    for each a in A do
        c1[a] = c2[a] = Red
0 Answers
Related