BFS to find unreachable pair of vertices (s, t) from given sets S and T in V of digraph G=(V, E)

40 Views Asked by At

I want to find unreachable source-sink-Pairs and get an algorithm with time complexity of O(mn).

And my idea is it to solve it with BFS, because DFS could get stuck in a loop.

Input: G = (V, E), S in V, T in V

> Queue Q;
> 
> Reach[][] = bool[|S|][|T|];
> 
> For w in (s, w) in E:
>     if w in T:
>         Reach[s][w] = 1;
>     Q.enqueue(w);
>     w.sources.add(s);
> 
> 
> While Q != empty:
>     v = Q.dequeue();
>     forall w in (v, w) in E:
>         w.sources.add(v.sources);
          Q.enqueue(w);
>         if w in T:
              forall s in v.sources:
>                 Reach[s][w] = 1;
> 
> print(not(Reach));

Is this algorithm correct?

Now I know that the time complexity of BFS is O(|V| + |E|).

Now let m be |S| and n be |T|. Then we time complexity would be O(|V| + |E| + mn), right? Because not(Reach) would have to iterate over m*n combinations?

And how could I proof the correctness of this algorithm?

Thanks for any help. Maybe someone knows a good resource for this kind of problems that I could read. Probably graph theory books.

I tried to realize the BFS algorithm and I tried to read about the theory behind BFS.

Btw. is there no way to embed LaTeX in blockcodes?

0

There are 0 best solutions below