Reachability

<p>In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, reachability refers to the ability to get from one <a href="/facts/Vertex_(graph_theory)/WhlWmL3o">vertex</a> to another within a graph. A vertex 
  
    
      
        s
      
    
    {\displaystyle s}
  
 can reach a vertex 
  
    
      
        t
      
    
    {\displaystyle t}
  
 (and 
  
    
      
        t
      
    
    {\displaystyle t}
  
 is reachable from 
  
    
      
        s
      
    
    {\displaystyle s}
  
) if there exists a sequence of <a href="/facts/Glossary_of_graph_theory/W0MqKkyE">adjacent</a> vertices (i.e. a <a href="/facts/Path_(graph_theory)/WMsq21Nf">walk</a>) which starts with 
  
    
      
        s
      
    
    {\displaystyle s}
  
 and ends with 
  
    
      
        t
      
    
    {\displaystyle t}
  
.
</p><p>In an undirected graph, reachability between all pairs of vertices can be determined by identifying the <a href="/facts/Connected_component_(graph_theory)/5owVSXtY">connected components</a> of the graph. Any pair of vertices in such a graph can reach each other <a href="/facts/Iff/bYSxGJ66">if and only if</a> they belong to the same connected component; therefore, in such a graph, reachability is symmetric (
  
    
      
        s
      
    
    {\displaystyle s}
  
 reaches 
  
    
      
        t
      
    
    {\displaystyle t}
  
 <a href="/facts/Iff/bYSxGJ66">iff</a> 
  
    
      
        t
      
    
    {\displaystyle t}
  
 reaches 
  
    
      
        s
      
    
    {\displaystyle s}
  
). The connected components of an undirected graph can be identified in linear time. The remainder of this article focuses on the more difficult problem of determining pairwise reachability in a <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a> (which, incidentally, need not be symmetric).
</p>

Reachability open-in-new

Reachability