本文共 5796 字，大约阅读时间需要 19 分钟。

图的深度优先搜索(Depth First Search)和广度优先搜索(Breadth First Search)实现

图的基本概念

图是一种用于表示多对多关系的数据结构，由顶点和边组成。顶点（Vertex）可以称为节点，边（Edge）表示顶点之间的连接。图可以分为无向图和有向图。无向图的边没有方向ality，而有向图的边具有明确的方向。边也可以带权重（Weight），这样的图也称为网（Graph with weights）。

顶点之间的连接可以通过边来表示，并形成路径。例如，从节点D到C的路径包括D→B→C和D→A→B→C两种可能。

图的表示方式

图的表示方式主要有两种：邻接矩阵和邻接表。

图的创建与代码实现

我们创建一个Graph类来处理图的操作。

import java.util.ArrayList;import java.util.Arrays;import java.util.LinkedList;public class Graph {    private ArrayList
   
     vertexList;    private int[][] edges;    private String[] vertexNames;    private int numOfEdges;    private boolean[] isVisited;    LinkedList
    
      queue;        public Graph(int n) {        edges = new int[n][n];        vertexList = new ArrayList<>();        numOfEdges = 0;        isVisited = new boolean[n];        queue = new LinkedList<>();    }    public void insertVertex(String vertex) {        vertexList.add(vertex);    }    public void insertEdge(int v1, int v2, int weight) {        if (v1 >= 0 && v1 < edges.length && v2 >= 0 && v2 < edges.length) {            edges[v1][v2] = weight;            edges[v2][v1] = weight;            numOfEdges++;        }    }    public void dfs() {        isVisited = new boolean[getMaxNodeId()];        for (int i = 0; i < getMaxNodeId(); i++) {            if (!isVisited[i]) {                dfsTraversal(isVisited, i);            }        }    }    private void dfsTraversal(boolean[] isVisited, int i) {        isVisited[i] = true;        printVertex(i);        int firstNeighbor = getFirstNeighbor(i);        while (firstNeighbor != -1) {            if (!isVisited[firstNeighbor]) {                dfsTraversal(isVisited, firstNeighbor);            }            firstNeighbor = getNextNeighbor(i, firstNeighbor);        }    }    public void bfs() {        isVisited = new boolean[getMaxNodeId()];        for (int i = 0; i < getMaxNodeId(); i++) {            if (!isVisited[i]) {                bfsTraversal(isVisited, i);            }        }    }    private void bfsTraversal(boolean[] isVisited, int i) {        isVisited[i] = true;        queue.add(i);        System.out.print(getValueByIndex(i) + "=>");        while (!queue.isEmpty()) {            int u = queue.poll();            int firstNeighbor = getFirstNeighbor(u);            while (firstNeighbor != -1) {                if (!isVisited[firstNeighbor]) {                    isVisited[firstNeighbor] = true;                    System.out.print(getValueByIndex(firstNeighbor) + "=>");                    queue.add(firstNeighbor);                }                firstNeighbor = getNextNeighbor(u, firstNeighbor);            }        }    }    private int getMaxNodeId() {        return vertexList.size();    }    private int getFirstNeighbor(int index) {        for (int j = 0; j < vertexList.size(); j++) {            if (edges[index][j] != 0) {                return j;            }        }        return -1;    }    private int getNextNeighbor(int v1, int v2) {        for (int j = v2 + 1; j < vertexList.size(); j++) {            if (edges[v1][j] != 0) {                return j;            }        }        return -1;    }    public void showGraph() {        for (int[] link : edges) {            System.out.println(Arrays.toString(link));        }    }    public String getValueByIndex(int i) {        return vertexList.get(i);    }    public static void main(String[] args) {        int n = 5;        String[] Vertexs = {"A", "B", "C", "D", "E"};        Graph graph = new Graph(n);        for (String vertex : Vertexs) {            graph.insertVertex(vertex);        }        graph.insertEdge(0, 1, 1);        graph.insertEdge(0, 2, 1);        graph.insertEdge(1, 2, 1);        graph.insertEdge(1, 3, 1);        graph.insertEdge(1, 4, 1);        graph.showGraph();        System.out.println("深度遍历");        graph.dfs();        System.out.println();        System.out.println("广度遍历");        graph.bfs();    }}
    
   

深度优先搜索(Depth First Search)实现

深度优先搜索是一个递归算法，它从图的起始顶点开始，尽可能深入访问它的邻接顶点，尽量避免回溯。一旦到达不能再继续深入的顶点时，才会回溯，从而访问另一个邻接顶点。这个过程直到所有顶点都被访问完毕。

深度优先遍历的步骤：

深度优先遍历示例代码注释：

private void dfsTraversal(boolean[] isVisited, int i) {    isVisited[i] = true;    printVertex(i); // 打印当前顶点    int firstNeighbor = getFirstNeighbor(i); // 获取当前顶点的第一个邻接顶点    while (firstNeighbor != -1) { // 确保有邻接顶点存在        if (!isVisited[firstNeighbor]) {            dfsTraversal(isVisited, firstNeighbor); // 递归深度优先访问邻接顶点        }        firstNeighbor = getNextNeighbor(i, firstNeighbor); // 获取当前顶点的下一个邻接顶点    }}

广度优先搜索(Breadth First Search)实现

广度优先搜索使用一个队列来维护访问顺序，它首先访问图的起始顶点，然后依次访问其邻接顶点，将每个新访问的顶点入队。队列的先进先出（FIFO）特性确保了每层顶点都被访问完毕。

广度优先遍历的步骤：

广度优先遍历示例代码注释：

private void bfsTraversal(boolean[] isVisited, int i) {    isVisited[i] = true;    System.out.print(getValueByIndex(i) + "=>");    queue.add(i);    while (!queue.isEmpty()) {        int u = queue.poll(); // 取出队列的顶点        int firstNeighbor = getFirstNeighbor(u); // 获取顶点u的第一个邻接顶点        while (firstNeighbor != -1) {            if (!isVisited[firstNeighbor]) {                isVisited[firstNeighbor] = true;                System.out.print(getValueByIndex(firstNeighbor) + "=>");                queue.add(firstNeighbor); // 将邻接顶点入队            }            firstNeighbor = getNextNeighbor(u, firstNeighbor); // 获取顶点u的下一个邻接顶点        }    }}

比较与优化

深度优先搜索和广度优先搜索各有优缺点。深度优先搜索在处理路径问题、中图形遍历和具有特定结构的图中表现优异，常用于实现查找最短路径或判定图的连通性。而广度优先搜索在处理图的遍历、网络传播和路径查找中表现更好，特别是在查找最短路径时更为高效。

通过合理选择算法和优化访问顺序，可以充分发挥图遍历技术的优势，实现更高效率的图形处理任务。

转载地址：http://trvqz.baihongyu.com/