GraphLab

Graph theory & algorithm visualizer
About Node base

GraphLab › Node base

Node Base of a Directed Graph: Find It Step by Step

A node base (also called a vertex basis) of a directed graph is a smallest set of vertices from which every vertex of the graph can be reached by following the edges.

How to find a node base

  1. Find the reachable set R(v) of every vertex v: all the vertices you can get to from v, including v itself.
  2. Group the vertices into strong components: u and w belong together when each can reach the other.
  3. A component with no edge coming in from another component cannot be reached from outside, so the node base needs exactly one of its vertices.
  4. Pick one vertex from each such component. If a component has several vertices, any of them works, so a graph can have more than one node base.

Try it in GraphLab

Step 1 shows the reachable set of every vertex. Step 2 shows the node base, or all possible node bases when there is more than one.

More topics