How to Find Paths in Graphs using Artificial Intelligence algorothm Java programming

Finding Paths in Graphs:

      The common type of search space is represented by a graph. A graph is a set of nodes and links.
We characterize nodes as containing the following data:

• A name and/or other data.
• Zero or more links to other nodes
• A position in space (this is optional, usually for display or visualization purposes)

     Links between nodes are often called edges. The algorithms used for finding paths in graphs are very similar to finding paths in a two-dimensional maze. The primary difference is the operators that allow us to move from one node to another. In the last section we saw that in a maze, an agent can move from one grid space to another if the target space is empty. For graph search, a movement operator allows movement to another node if there is a link to the target node.

Fig: UML class diagram for the graph search classes

         As seen in Figure, most of the data for the search operations (i.e., nodes, links, etc.) is defined in the abstract class AbstractGraphSearch. This abstract class is customized through inheritance to use a stack for storing possible moves (i.e., the array path) for depth-first search and a queue for breadth-first search. The abstract class AbstractGraphSearch allocates data required by both derived classes:

final public static int MAX = 50;

protected int [] path = new int[AbstractGraphSearch.MAX];

protected int num_path = 0;

// for nodes:

protected String [] nodeNames =  new String[MAX];

protected int [] node_x = new int[MAX];

protected int [] node_y = new int[MAX];

 // for links between nodes:

protected int [] link_1 = new int[MAX];

protected int [] link_2 = new int[MAX];

protected int [] lengths = new int[MAX];

protected int numNodes = 0;

protected int numLinks = 0;

protected int goalNodeIndex = -1,

startNodeIndex = -1;