java查找无向连通图中两点间所有路径的算法

Z时代
2024-01-10
分类：综合

之前就这个问题发帖求教过，过了几天没看到回复就没再关心。后来自己设计了一个算法，在公司的项目中实践了一下，效果还可以，贴出来供大家参考。

算法要求：

1. 在一个无向连通图中求出两个给定点之间的所有路径；

2. 在所得路径上不能含有环路或重复的点；

算法思想描述：

1. 整理节点间的关系，为每个节点建立一个集合，该集合中保存所有与该节点直接相连的节点（不包括该节点自身）；

2. 定义两点一个为起始节点，另一个为终点，求解两者之间的所有路径的问题可以被分解为如下所述的子问题：对每一个与起始节点直接相连的节点，求解它到终点的所有路径（路径上不包括起始节点）得到一个路径集合，将这些路径集合相加就可以得到起始节点到终点的所有路径；依次类推就可以应用递归的思想，层层递归直到终点，若发现希望得到的一条路径，则转储并打印输出；若发现环路，或发现死路，则停止寻路并返回；

3. 用栈保存当前已经寻到的路径（不是完整路径）上的节点，在每一次寻到完整路径时弹出栈顶节点；而在遇到从栈顶节点无法继续向下寻路时也弹出该栈顶节点，从而实现回溯。

算法伪码(java描述)：


public Stack stack = new Stack();/*临时保存路径节点的栈*/
public ArrayList sers = new ArrayList();/*存储路径的集合*/
public class Node/*表示一个节点以及和这个节点相连的所有节点*/
  {
    public String name = null; 
    public ArrayList relationNodes = new ArrayList();
    public String getName()
    {
      return name;
    }
    public void setName(String name)
    {
      this.name = name;
    }
    public ArrayList getRelationNodes()
    {
      return relationNodes;
    }
    public void setRelationNodes(ArrayList relationNodes)
    {
      this.relationNodes = relationNodes;
    }
  }
public boolean isNodeInStack(Node node)/*判断节点是否在栈中*/
  {
    Iterator it = stack.iterator();
    while(it.hasNext())
    {
      Node node1 = (Node)it.next();
      if(node == node1)
        return true;
    }
    return false;
  }
public void showAndSavePath ()/*此时栈中的节点组成一条所求路径，转储并打印输出*/
  {
    Object[] o = stack.toArray();
    for(int i = 0;i<o.length;i++)
    {
      System.out.print(o[i]);
    }
    sers.add(o); /*转储*/
    System.out.println("\n");
  }
/*寻找路径的方法*/
public boolean getPaths(Node cNode, Node pNode, Node sNode, Node eNode)
/*cNode表示当前的起始节点currentNode，pNode表示当前起始节点的上一节点previousNode，sNode表示最初的起始节点startNode，eNode表示终点endNode*/
  {
    Node nNode = null;
    if(cNode != null && pNode != null && cNode == pNode)
      return false;/*如果符合条件判断说明出现环路，不能再顺着该路径继续寻路，返回false*/
    if(cNode != null)
    {
      int i = 0;
      stack.push(cNode);/*起始节点入栈*/
      if(cNode == eNode)/*如果该起始节点就是终点，说明找到一条路径*/
      {
        showAndSavePath();/*转储并打印输出该路径，返回true*/
        return true;
      }
      Else/*如果不是,继续寻路*/
      {
        nNode = cNode.getRelationNodes().get(i);/*从与当前起始节点cNode有连接关系的节点集中按顺序遍历得到一个节点作为下一次递归寻路时的起始节点*/
        while(nNode != null)
        {
          if(pNode != null && (nNode == sNode 
              || nNode == pNode 
              || isNodeInStack(nNode)))/*如果nNode是最初的起始节点或者nNode就是cNode的上一节点或者nNode已经在栈中，说明产生环路，应重新在与当前起始节点有连接关系的节点集中寻找nNode*/
          {
            i++;
            if(i>=cNode.getRelationNodes().size())
              nNode = null;
            else
              nNode = cNode.getRelationNodes().get(i);
            continue;
          }
/*以nNode为新的起始节点，当前起始节点cNode为上一节点，递归调用寻路方法*/
          if(getPaths(nNode, cNode, sNode, eNode))/*递归调用*/
          {
            stack.pop();/*如果找到一条路径，则弹出栈顶节点*/
          }
          i++;/*继续在与cNode有连接关系的节点集中测试nNode*/
          if(i>=cNode.getRelationNodes().size())
            nNode = null;
          else
            nNode = cNode.getRelationNodes().get(i);
        }
        stack.pop();/*当遍历完所有与cNode有连接关系的节点后，说明在以cNode为起始节点到终点的路径已经全部找到*/
        return false;
      }
    }
    else
      return false;
}