廣度優先，深度優先，尋求最短路徑。

bawn 發布于2019-08-16 18:32 / 3315人閱讀

一、應用

深度優先：是否存在通路，尋找所有解。

廣度優先遍歷：尋求最優解，尋求最短路徑

1.鄰接矩陣JAVA代碼實現

鄰接矩陣可以使用一個二維數組來表示

public class GraphTest {

  // 節點
  public static class Vertex {
    public String name;
    private boolean isVisited;

    public Vertex(String name) {
      this.name = name;
      this.isVisited = false;
    }

    public void displayName() {
      System.out.println("name:" + name);
    }
  }

  // 圖
  public static class Graph {
    // 存節點數據
    private Vertex[] vertices;
    // 矩陣
    private int[][] matrix;
    // 隊列，用于BFS
    private Queue queue = new LinkedList<>();
    // 棧，用于DFS
    private Stack stack = new Stack<>();

    private Map dependencyMap = new HashMap<>();

    public Graph(Vertex[] vertices, int[][] matrix) {
      this.vertices = vertices;
      this.matrix = matrix;
    }

    // 找到未訪問過的鄰接點
    public List getUnvisitedVertex(int i) {
      List unvisitedVertices = new ArrayList<>();
      for (int j = 0; j < matrix.length; j++) {
        if (matrix[i][j] > 0 && !vertices[j].isVisited) {
          unvisitedVertices.add(j);
        }
      }
      return unvisitedVertices;
    }

    // 廣度優先
    public void bfs(int vertex) {
      queue.offer(vertex);

      while (!queue.isEmpty()) {
        int v = queue.poll();
        if (!vertices[v].isVisited) {
          vertices[v].displayName();
          vertices[v].isVisited = true;

          List unvisitedVertices = getUnvisitedVertex(v);
          unvisitedVertices.forEach(uv -> {
            queue.offer(uv);
            dependencyMap.putIfAbsent(uv, v);
          });
        }
      }
    }

    // 深度優先
    public void dfs(int vertex) {
      stack.push(vertex);

      while (!stack.isEmpty()) {
        int v = stack.pop();
        if (!vertices[v].isVisited) {
          vertices[v].displayName();
          vertices[v].isVisited = true;

          List unvisitedVertices = getUnvisitedVertex(v);
          unvisitedVertices.forEach(uv -> stack.push(uv));
        }
      }
    }

    // 深度優先遞歸實現
    public void dfsRecursion(int vertex) {
      if (!vertices[vertex].isVisited) {
        vertices[vertex].displayName();
        vertices[vertex].isVisited = true;

        List unvisitedVertices = getUnvisitedVertex(vertex);
        unvisitedVertices.forEach(this::dfsRecursion);
      }
    }

    public void printShortestPath(int start, int end) {
      bfs(start);

      String symbol = "-->";
      StringBuilder sb = new StringBuilder();
      sb.append(vertices[end].name);
      sb.append(symbol);
      while (dependencyMap.get(end) != null) {
        sb.append(vertices[dependencyMap.get(end)].name);
        sb.append(symbol);
        end = dependencyMap.get(end);
      }
      String path = sb.substring(0, sb.lastIndexOf(symbol));
      System.out.println(path);
    }

    public void clear() {
      stack.clear();
      queue.clear();
      dependencyMap.clear();
      for (int i = 0; i < vertices.length; i++) {
        vertices[i].isVisited = false;
      }
    }

  }

  public static void main(String[] args) {
    Vertex[] vertices = {
            new Vertex("v0"),
            new Vertex("v1"),
            new Vertex("v2"),
            new Vertex("v3"),
            new Vertex("v4")
    };

    int[][] matrix = new int[][]{
            {0, 0, 1, 1, 0},
            {0, 0, 1, 0, 1},
            {1, 1, 0, 0, 1},
            {1, 0, 0, 0, 1},
            {0, 1, 1, 1, 0}
    };

    Graph graph = new Graph(vertices, matrix);

    System.out.println("廣度優先搜索：");
    graph.bfs(0);
    graph.clear();

    System.out.println("深度優先搜索：");

    graph.dfs(0);
    graph.clear();

    System.out.println("遞歸深度優先搜索：");

    graph.dfsRecursion(0);
    graph.clear();

    System.out.println("打印最短路徑：");

    graph.printShortestPath(0, 4);
  }
}

打印結果
廣度優先搜索：
name:v0
name:v2
name:v3
name:v1
name:v4
深度優先搜索：
name:v0
name:v3
name:v4
name:v2
name:v1
遞歸深度優先搜索：
name:v0
name:v2
name:v1
name:v4
name:v3
打印最短路徑：
name:v0
name:v2
name:v3
name:v1
name:v4
v4-->v2-->v0

2.鄰接表JAVA代碼實現

鄰接表可以使用數組+鏈表，鏈表+鏈表，哈希表等等數據結構來表示。在java中，map結構非常適合表示鄰接表

public class GraphTest {
  public static void main(String[] args){
    //初始化先建立起各個節點信息，以及對應的直接子節點列表
    HashMap map = new HashMap<>();
    map.put("V0", new String[] {"V2","V3"});
    map.put("V1", new String[] {"V2","V4"});
    map.put("V2", new String[] {"V0","V1","V4"});
    map.put("V3", new String[] {"V0","V4"});
    map.put("V4", new String[] {"V1","V2","V3"});
    //獲取從A到H的最短路徑節點鏈表
    Node target = findTarget("V0","V4",map);
    //打印出最短路徑的各個節點信息
    printSearPath(target);

  }

  /**
   * 打印出到達節點target所經過的各個節點信息
   * @param target
   */
  static void printSearPath(Node target) {
    if (target != null) {
      System.out.print("找到了目標節點:" + target.id + "
");

      List searchPath = new ArrayList();
      searchPath.add(target);
      Node node = target.parent;
      while(node!=null) {
        searchPath.add(node);
        node = node.parent;
      }
      String path = "";
      for(int i=searchPath.size()-1;i>=0;i--) {
        path += searchPath.get(i).id;
        if(i!=0) {
          path += "-->";
        }
      }
      System.out.print("步數最短："+path);
    } else {
      System.out.print("未找到了目標節點");
    }
  }

  /**
   * 從指定的開始節點 startId ，查詢到目標節點targetId 的最短路徑
   * @param startId
   * @param targetId
   * @param map
   * @return
   */
  static Node findTarget(String startId,String targetId,HashMap map) {
    List hasSearchList = new ArrayList();
    LinkedList queue = new LinkedList();
    queue.offer(new Node(startId,null));
    while(!queue.isEmpty()) {
      Node node = queue.poll();

      if(hasSearchList.contains(node.id)) {
        //跳過已經搜索過的，避免重復或者死循環
        continue;
      }
      System.out.print("判斷節點:" + node.id +"
");
      if (targetId.equals(node.id)) {
        return node;
      }
      hasSearchList.add(node.id);
      if (map.get(node.id) != null && map.get(node.id).length > 0) {
        for (String childId : map.get(node.id)) {
          queue.offer(new Node(childId,node));
        }
      }
    }

    return null;
  }

  /**
   * 節點對象
   * @author Administrator
   *
   */
  static class Node{
    //節點唯一id
    public String id;
    //該節點的直接父節點
    public Node parent;
    //該節點的直接子節點
    public List childs = new ArrayList();
    public Node(String id,Node parent) {
      this.id = id;
      this.parent = parent;
    }
  }
}

打印：
判斷節點:V0
判斷節點:V2
判斷節點:V3
判斷節點:V1
判斷節點:V4
找到了目標節點:V4
步數最短：V0-->V2-->V4

云服務器 GPU云服務器最短路徑優先算法最短路徑優先算法c 廣度優先遍歷廣度優先搜索

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/75297.html

算法-圖和圖算法

摘要：圖的定義用圖對現實中的系統建模可以用圖對現實中的很多系統建模比如對交通流量建模頂點可以表示街道的十字路口邊可以表示街道加權的邊可以表示限速或者車道的數量建模人員可以用這個系統來判斷最佳路線及最有可能堵車的街道任何運輸系統都可以用圖來建模比如圖的定義用圖對現實中的系統建模可以用圖對現實中的很多系統建模. 比如對交通流量建模, 頂點可以表示街道的十字路口, 邊可以表示街道. 加權的邊...

Anshiii 2019-08-23 12:15 評論0 收藏0
圖的JS實現

摘要：圖的實現如下采用鄰接表結構實現。由于本次示例的是無向圖，因此每個頂點都互相增加為鄰接點。然而由于本次示例的圖為無向圖，會出現重復遍歷的情況，例如頂點的鄰接點有，的鄰接點有。圖的定義圖就是由若干個頂點和邊連接起來的一種結構。很多東西都可以用圖來說明，例如人際關系，或者地圖。其中圖還分為有向圖和無向圖。如下就是有向圖圖的數據結構對于圖這種關系，可以通過兩種方式來存儲。領接表將...

LeanCloud 2019-08-21 17:00 評論0 收藏0
基于JavaScript求解八數碼最短路徑并生成動畫效果

摘要：寫在最前本次分享一下通過廣度優先搜索解決八數碼問題并展示其最短路徑的動畫效果。一個排列中逆序的總數就稱為這個排列的逆序數。如果起始狀態與結束狀態的逆序數的奇偶性相同，則說明狀態可達，反之亦然。寫在最前本次分享一下通過廣度優先搜索解決八數碼問題并展示其最短路徑的動畫效果。歡迎關注我的博客，不定期更新中—— 效果預覽該效果為從[[2, 6, 3],[4, 8, 0],[7, 1, ...

Jioby 2019-08-26 11:30 評論0 收藏0
隊列和 BFS —— 棧和 DFS

摘要：隊列和廣度優先搜索的一個常見應用是找出從根結點到目標結點的最短路徑。然后在每一輪中，我們逐個處理已經在隊列中的結點，并將所有鄰居添加到隊列中。這就是我們在中使用隊列的原因。隊列和 BFS：廣度優先搜索（BFS）的一個常見應用是找出從根結點到目標結點的最短路徑。示例這里我們提供一個示例來說明如何使用 BFS 來找出根結點 A 和目標結點 G 之間的最短路徑。 showImg(h...

Kyxy 2019-08-19 10:31 評論0 收藏0
算法系列——JavaScript中廣度優先搜索思想實現

摘要：散列表上面的地圖向我們展示了如何用廣度優先搜索的思想找到北京到廣州的最短路線。在廣度優先搜索中，我們需要用到隊列的這種思想來實現查找。建立了下面這個模型武漢廣州西藏上海上海武漢廣州代碼完整實現，利用遞歸和廣度優先搜索的思想實現。什么是廣度優先搜索？如果只是是背概念，幼兒園的小朋友都能背下來念給你聽。假設看這篇文章的都和我一樣是個前端工程師，我們要從廣度優先搜索（BFS）中學到什么...

everfly 2019-08-21 17:36 評論0 收藏0