CODEWITHSUNDEEP
graph
Retr0spect
Retr0spect

Reputation: 187

Algorithm: Find if a there's a path from a vertex to every other vertices in a directed graph?

Given a directed graph. I want an algorithm that finds, if there is a path between a vertex v to all other vertices in the graph? In time complexity (|V| + |E|).

I'm not sure how to proceed with this problem. A little help will be greatly appreciated.

Thanks.

Upvotes: 1

Views: 1278

Answers (2)

Codor
Codor

Reputation: 17605

If the problem is just finding out if a path between a single pair of vertices exists, depth-first search can be used. If the existence of a path for a specific fixed graph, but various combinations of vertices is to be repeated, a connected component analysis might be more suitable.

Upvotes: 2

Netwave
Netwave

Reputation: 42796

Recursive version for check connected vertex Pseudocode:

Object Vertex {position, list_of_connected_vertex, already_checked}
Object Graph  {list_of_all_vertex}

function checkConnected(initial_vertex):
    if initial_vertex is already_checked:
        return
    else:
        initial_vertex.already_checked = true
        for vertex in initial_vertex.list_of_connected_vertex:
            checkConnected(vertex)

if all_are_checked(Graph.list_of_all_vertex) then Vertex is connected.

(Clear the flags already_checked for other vertex and graph check)

Is a natural way of think about the problem, not the best performance way for it probably.

Upvotes: 2

Related Questions