图的路由查找

图的路由查找算法：
1、 STEP ONE
定义节点对象
package com.huawei.ams5000.util.routesearcher;

import java.util.ArrayList;
import java.util.List;

/**
*  节点对象
*
* @author zWX144601
*
*/
public class RouteSearcherNodeInfo
{
    /**
     * 节点ID
     */
    private int siteId;
   
    /**
     * TOPO图ID
     */
    private int topoId;
   
    /**
     * 节点名称
     */
    private String name = null;
   
    /**
     * 关联的站点
     */
    public List<RouteSearcherNodeInfo> relationNodes = new ArrayList<RouteSearcherNodeInfo>();
   
    /**
    * 关联的链路ID
    */
    public List<List<Integer>> relationNmsPGIDS = new ArrayList<List<Integer>>();
   
    public String getName()
    {
        return name;
    }
   
    public void setName(String name)
    {
        this.name = name;
    }
   
    public List<RouteSearcherNodeInfo> getRelationNodes()
    {
        return relationNodes;
    }
   
    public void setRelationNodes(List<RouteSearcherNodeInfo> relationNodes)
    {
        this.relationNodes = relationNodes;
    }
   
    public int getSiteId()
    {
        return siteId;
    }
   
    public void setSiteId(int siteId)
    {
        this.siteId = siteId;
    }
   
    public int getTopoId()
    {
        return topoId;
    }
   
    public void setTopoId(int topoId)
    {
        this.topoId = topoId;
    }

    public List<List<Integer>> getRelationNmsPGIDS()
    {
        return relationNmsPGIDS;
    }

    public void setRelationNmsPGIDS(List<List<Integer>> relationNmsPGIDS)
    {
        this.relationNmsPGIDS = relationNmsPGIDS;
    }  
}

2 STEP TWO
实现查找递归算法
package com.huawei.ams5000.util.routesearcher;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Stack;

import com.huawei.ams5000.util.routesearcher.RouteSearcherNodeInfo;

public class RouteSearcher
{
   
    private Stack<RouteSearcherNodeInfo> stack;
   
    private List<List<String>> resultPath = new ArrayList<List<String>>();
   
    public RouteSearcher(Stack<RouteSearcherNodeInfo> stack)
    {
        this.stack = stack;
        stack.clear();
    }
   
    public boolean isNodeInStack(RouteSearcherNodeInfo node)
    {
        Iterator<RouteSearcherNodeInfo> it = stack.iterator();
        while (it.hasNext())
        {
            RouteSearcherNodeInfo node1 = (RouteSearcherNodeInfo)it.next();
            if (node == node1)
                return true;
        }
        return false;
    }
   
    public void savePath()
    {
        Object[] o = stack.toArray();
        List<String> asList = new ArrayList<String>(o.length);
        for (Object object : o)
        {
            RouteSearcherNodeInfo node = (RouteSearcherNodeInfo)object;
            asList.add(node.getName());
        }
        resultPath.add(asList);
    }
   
    /**
     * 查找路由
     * @param cNode 当前查找节点
     * @param pNode 前一个节点
     * @param sNode 开始节点
     * @param eNode 结束节点
     * @return [参数说明]
     *
     * @return boolean [返回类型说明] 是否超找通路
     * @exception throws [违例类型] [违例说明]
     * @see [类、类#方法、类#成员]
     */
    public boolean getPaths(RouteSearcherNodeInfo cNode, RouteSearcherNodeInfo pNode, RouteSearcherNodeInfo sNode,
            RouteSearcherNodeInfo eNode)
    {
        RouteSearcherNodeInfo nNode = null;
        if (cNode != null && pNode != null && cNode == pNode)  //判断环的情况
            return false;
        if (cNode != null)
        {
            int i = 0;
            stack.push(cNode); //压入当前节点
            if (cNode == eNode) //递归结束条件  如果当前查找的节点为终结点，则stack中保存了一条通路
            {
                savePath();   //获取通路
                return true;  //标记找到通路
            }
            else
            {  //如果当前节点不是目标节点，则循环找当前节点的关联节点，视图找到关联节点的每一条通路
                nNode = cNode.getRelationNodes().get(i);
                while (nNode != null)
                {
                    /*
                     * pNode != null标记 pNode ,cNOde,nNode能组成通路，否则为断开的路，没必要处理;
                     * nNode == sNode标记关联节点是开始节点，开始节点没必要找通路，所有通路均由开始节点开始
                     * nNode == pNode标记关联节点已经所搜，没必要继续搜索
                     * isNodeInStack，标记nNode曾经搜索过，没必要继续搜索
                     */
                    if (pNode != null && (nNode == sNode || nNode == pNode || isNodeInStack(nNode)))
                    {
                        i++;
                        if (i >= cNode.getRelationNodes().size())
                            nNode = null;
                        else
                            nNode = cNode.getRelationNodes().get(i);
                        continue;
                    }
                    //以nNode出发，看能否找到一条通路，如果找到，再找下一个节点，stack.pop()即找下一个cNode的子节点
                    if (getPaths(nNode, cNode, sNode, eNode) && !stack.isEmpty())
                    {
                        stack.pop();
                    }
                    //下一个子节点
                    i++;
                    if (i >= cNode.getRelationNodes().size())
                        nNode = null;
                    else
                        nNode = cNode.getRelationNodes().get(i);
                }
                stack.pop();//相对应 cNode = eNode的判断，对于当前节点来说，如果不是end节点，以为这此路不通，此节点不保存（从stack中弹出）
                return false;//此路不通，return false
            }
        }
        else
            return false;
    }
   
    public Stack<RouteSearcherNodeInfo> getStack()
    {
        return stack;
    }
   
    public void setStack(Stack<RouteSearcherNodeInfo> stack)
    {
        this.stack = stack;
    }
   
    public List<List<String>> getResultPath()
    {
        return resultPath;
    }
   
    public void setResultPath(List<List<String>> resultPath)
    {
        this.resultPath = resultPath;
    }
   
}