[Math] Find if we can reach all nodes in a directed graph starting from one node s

algorithmsgraph theory

If we have a directed graph $G = (V,E)$ and we want to find if there is such node $s \in V$ that we can reach all other nodes of $G$

What is a good algorithm to solve this problem and what is its execution time?

Best Answer

Run Tarjan's linear-time algorithm for finding strongly connected components.

If there is more than one component with no incoming edges, then there can be no node that can reach everywhere.

On the other hand, if there is exactly one component with no incoming edges, each node in that component (and no other nodes) can reach everywhere in the graph.

(If you're looking for nodes that are reachable from everywhere -- as in the original the title of the question said -- look instead for components with no outgoing edges).

Related Solutions

[Math] the maximum number of nodes I can traverse in an undirected graph visiting each node exactly once

This problem is still difficult, it is known as Hamiltonian path, and NP-complete. It doesn't really make a difference if the path is closed (a circuit) or not. Just ask the HAM-PATH problem for every pair of endpoints of all edges and you could solve HAM-CIRCUIT.

[Math] Algorithm that can divide all graph nodes N into two fully connected sets

Two observations: If you can find $A$ and $B$ so that their union is all of $G$ and they both induce cliques then you can find $A$ and $B$ that are disjoint cover all of $G$ and also induce cliques.}

Now notice that $A$ and $B$ induce cliques if and only if there are no edges between vertices of $A$ and no edges between vertices of $B$ in the complement of $G$.

So your problem is equivalent to determining if $G^c$ is bipartite, and if it is, finding a partition of $G^c$. This can easily be done in $\mathcal O(n^2)$ time.

Here is some c++11 code:

#include <bits/stdc++.h>
using namespace std;

const int MAX=1010; // maximum number of vertices
set <int> A[MAX];// A[i] stores all the neighbours of vertex i
int C[MAX]; // this store in which "part" we save vertex i

void impossible(){// I just use this to print when I realize its impossible
    printf("impossible\n");
    exit(0);
}

void dfs(int x){
    for(int y:A[x]){
        if(C[y]==C[x]) impossible();// this means the graph is not bipartite
        if(C[y]==0){
            if(C[x]==1) C[y]=2;
            else C[y]=1;
            dfs(y);
        }
    }
}

int main(){
    int n,m; // number of vertices and edges
    scanf("%d %d",&n,&m); // we read n and m
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i!=j) A[i].insert(j); // we want to build the complement, so we start adding every edge
        }
    }
    for(int i=0;i<m;i++){// we read the edges in G and erase them from G^c
        int u,v;
        scanf("%d %d",&u,&v);
        A[u].erase(v);
        A[v].erase(u);
    }
    for(int i=0;i<n;i++){
        if(C[i]==0){// if i has not been explored yet we dfs from i
            C[i]=1;
            dfs(i);
        }
    }
    printf("The set A contains:\n");
    for(int i=0;i<n;i++){
        if(C[i]==1) printf("%d ",i);
    }
    printf("\nThe set B contains:\n");
    for(int i=0;i<n;i++){
        if(C[i]==2) printf("%d ",i);
    }
    printf("\n");
}

Best Answer

Related Solutions

[Math] the maximum number of nodes I can traverse in an undirected graph visiting each node exactly once

[Math] Algorithm that can divide all graph nodes N into two fully connected sets

Related Question