這篇文章主要為大家展示了“java如何實(shí)現(xiàn)查找無(wú)向連通圖中兩點(diǎn)間所有路徑的算法”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“java如何實(shí)現(xiàn)查找無(wú)向連通圖中兩點(diǎn)間所有路徑的算法”這篇文章吧。

成都創(chuàng)新互聯(lián)專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站建設(shè)、成都網(wǎng)站制作、忠縣網(wǎng)絡(luò)推廣、微信小程序開發(fā)、忠縣網(wǎng)絡(luò)營(yíng)銷、忠縣企業(yè)策劃、忠縣品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；成都創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供忠縣建站搭建服務(wù)，24小時(shí)服務(wù)熱線：028-86922220，官方網(wǎng)址：www.cdcxhl.com

算法要求：

1. 在一個(gè)無(wú)向連通圖中求出兩個(gè)給定點(diǎn)之間的所有路徑；
2. 在所得路徑上不能含有環(huán)路或重復(fù)的點(diǎn)；

算法思想描述：

1. 整理節(jié)點(diǎn)間的關(guān)系，為每個(gè)節(jié)點(diǎn)建立一個(gè)集合，該集合中保存所有與該節(jié)點(diǎn)直接相連的節(jié)點(diǎn)（不包括該節(jié)點(diǎn)自身）；

2. 定義兩點(diǎn)一個(gè)為起始節(jié)點(diǎn)，另一個(gè)為終點(diǎn)，求解兩者之間的所有路徑的問(wèn)題可以被分解為如下所述的子問(wèn)題：對(duì)每一個(gè)與起始節(jié)點(diǎn)直接相連的節(jié)點(diǎn)，求解它到終點(diǎn)的所有路徑（路徑上不包括起始節(jié)點(diǎn)）得到一個(gè)路徑集合，將這些路徑集合相加就可以得到起始節(jié)點(diǎn)到終點(diǎn)的所有路徑；依次類推就可以應(yīng)用遞歸的思想，層層遞歸直到終點(diǎn)，若發(fā)現(xiàn)希望得到的一條路徑，則轉(zhuǎn)儲(chǔ)并打印輸出；若發(fā)現(xiàn)環(huán)路，或發(fā)現(xiàn)死路，則停止尋路并返回；

3. 用棧保存當(dāng)前已經(jīng)尋到的路徑（不是完整路徑）上的節(jié)點(diǎn)，在每一次尋到完整路徑時(shí)彈出棧頂節(jié)點(diǎn)；而在遇到從棧頂節(jié)點(diǎn)無(wú)法繼續(xù)向下尋路時(shí)也彈出該棧頂節(jié)點(diǎn)，從而實(shí)現(xiàn)回溯。

算法偽碼(java描述)：

public Stack stack = new Stack();/*臨時(shí)保存路徑節(jié)點(diǎn)的棧*/
public ArrayList sers = new ArrayList();/*存儲(chǔ)路徑的集合*/

public class Node/*表示一個(gè)節(jié)點(diǎn)以及和這個(gè)節(jié)點(diǎn)相連的所有節(jié)點(diǎn)*/
  {
    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)/*判斷節(jié)點(diǎn)是否在棧中*/
  {
    Iterator it = stack.iterator();
    while(it.hasNext())
    {
      Node node1 = (Node)it.next();
      if(node == node1)
        return true;
    }
    return false;
  }

public void showAndSavePath ()/*此時(shí)棧中的節(jié)點(diǎn)組成一條所求路徑，轉(zhuǎn)儲(chǔ)并打印輸出*/
  {
    Object[] o = stack.toArray();
    for(int i = 0;i=cNode.getRelationNodes().size())
              nNode = null;
            else
              nNode = cNode.getRelationNodes().get(i);
            continue;
          }
/*以nNode為新的起始節(jié)點(diǎn)，當(dāng)前起始節(jié)點(diǎn)cNode為上一節(jié)點(diǎn)，遞歸調(diào)用尋路方法*/
          if(getPaths(nNode, cNode, sNode, eNode))/*遞歸調(diào)用*/
          {
            stack.pop();/*如果找到一條路徑，則彈出棧頂節(jié)點(diǎn)*/
          }
          i++;/*繼續(xù)在與cNode有連接關(guān)系的節(jié)點(diǎn)集中測(cè)試nNode*/
          if(i>=cNode.getRelationNodes().size())
            nNode = null;
          else
            nNode = cNode.getRelationNodes().get(i);
        }
        stack.pop();/*當(dāng)遍歷完所有與cNode有連接關(guān)系的節(jié)點(diǎn)后，說(shuō)明在以cNode為起始節(jié)點(diǎn)到終點(diǎn)的路徑已經(jīng)全部找到*/
        return false;
      }
    }
    else
      return false;
}

以上是“java如何實(shí)現(xiàn)查找無(wú)向連通圖中兩點(diǎn)間所有路徑的算法”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！