Search code examples
graphtheory

Easy way to find a graph edge between graph vertexes

if there are 100 graph vertexes, each graph vertex has 4 graph edges toward another graph vertex, and are stored in an array, X. "X(100, 4)" is the array's size, while "X(38, 2)" means the contents of the array at two dimensional index 38, 2.

Is there any simple way to find a way form a given starting graph vertex to another given graph vertex?

It does not have to be the shortest wat, as long as the destination can be reached. Thanks!

Solution

  • Yes. This is the same as finding a path between two vertices in an undirected graph, and is a thoroughly studied concept in mathematics and computer science. The usual method is a "Depth First Search" (DFS). A suitable algorithm is described here.

    Essentially it follows this pattern:

    1. Start with x equal to the start node.
    2. If x is the end node, then we're done.
    3. If we've already visited x then abandon this path.
    4. For each of the nodes y connected to x,
    5. Add x to the current path and set y=x.
    6. Run algorithm from step 2.
    7. Loop to step 4.

    That will explore every possible path from x, going as deep down each branch as possible to find the goal or a deadend. Hence "depth first".