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

1、图的引入

通过前面的学习可以看出，线性表与树均具有局限性：

• 线性表的局限性在于只有一个前驱结点和一个后继结点
• 树局限于只能有一个前驱结点
  而对于多对多问题的情况，线性表和树均无法解决

2、图的举例说明

3、图的常用概念

4、图的表示方式

注：上图中链表左侧的编号为起始结点，而该结点可达的其他结点组成链表中的各个元素，各元素间不一定具有可达关系

5、代码实现

1、图的邻接矩阵表示

public class Graph {       private ArrayList
   
     vertextList;      //存储顶点集合    private int[][] edges;      //存储图对应的邻接矩阵    private int numsOfEdges;    //接受图中边的数目        public Graph(int n) {   //        对边和点进行初始化        edges = new int[n][n];        vertextList = new ArrayList<>(n);        isVisited = new boolean[n];    }        public void insertVertex(String vertex) {           vertextList.add(vertex);    }    /**     * @param v1     表示连通的其中一个点，比如A-B相连，调用方法时传入参数为 0 ，1 ，1     * @param v2     * @param weight 若连通则设为1，反之为0     * @Method insertEdge     * @Author zhihua.Li     * @Version 1.0     * @Description 为连通的两个点设置边     * @Return void     * @Exception     * @Date 2021/3/5 18:10     */    public void insertEdge(int v1, int v2, int weight) {           edges[v1][v2] = weight;        edges[v2][v1] = weight;        numsOfEdges++;    }
   

2、常用方法

//    图中其他常见的方法	//    获取顶点个数    public int getNumOfVertex() {           return vertextList.size();    }    //    获取边的个数    public int getNumsOfEdges() {           return numsOfEdges;    }    //    通过index获取元素值    public String getValueByIndex(int i) {           return vertextList.get(i);    }    //    获取两元素间的权重    public int getWeight(int v1, int v2) {           return edges[v1][v2];    }    //    遍历获取图的邻接矩阵    public void show() {           for (int[] link : edges) {               System.out.println(Arrays.toString(link));        }

3、代码测试

public static void main(String[] args) {           String vertexs[] = {   "A","B","C","D","E","F"};        Graph graph = new Graph(vertexs.length);        for (String vertex : vertexs) {               graph.insertVertex(vertex);        }//        为AB/AC/BC/BD/BE添加边        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);//        显示邻接矩阵        System.out.println("图的邻接矩阵为：");        graph.show();      }

运行结果为：

6、图的遍历

1、深度优先遍历DFS

1、基本思想

2、思路分析

从某结点开始，找到该结点的第一个邻接结点，并对该结点递归，循环该操作，直到找不到结点的邻接结点再回归

3、代码实现

1. 在编写深度优先遍历算法之前，需要先编写出求某结点的第一个邻接结点及求某结点的下一个邻接结点的方法

//获取当前下标为index结点的第一个邻接结点    public int getFirstNeighbor(int index) {           for (int i = index + 1; i < vertextList.size(); i++) {               if (edges[index][i] == 1) {                   return i;            }        }        return -1;    }

//获取当前下标为index的下一个邻接结点    public int getNextNeighbor(int v1, int v2) {           for (int i = v2 + 1; i < vertextList.size(); i++) {               if (edges[v1][i] == 1) {                   return i;            }        }        return -1;    }

2. 除了上面的方法，还需要在结点的结构中增设一个标志位，避免循环遍历到该结点，默认都是false即未被遍历过

private boolean[] isVisited;

3.正式的深度优先遍历算法

/**     * @param isVisited 结点被遍历过的标志位     * @param index     当前节点的下标     * @Method deepFirstSearch     * @Author zhihua.Li     * @Version 1.0     * @Description     * @Return void     * @Exception     * @Date 2021/3/5 23:28     *///    可以用栈进行操作    public void deepFirstSearch(boolean[] isVisited, int index) {   //        首先将当前结点打印出来并将其标志位置为true        System.out.print(vertextList.get(index) + "\t");        isVisited[index] = true;//        获取该结点的第一个邻接结点        int firstNeighbor = getFirstNeighbor(index);        while (firstNeighbor != -1) {   //        若找到了该结点的邻接结点且该结点并没有被遍历过,就对该结点的邻接结点进行递归操作            if (!isVisited[firstNeighbor]) {                   deepFirstSearch(isVisited, firstNeighbor);            }//            将当前节点指向下一个邻接结点再次进行操作，直到该结点的所有邻接结点均被遍历到            firstNeighbor = getNextNeighbor(index, firstNeighbor);        }    }

4. 针对于图中的独立结点，需要额外讨论，因为该点不与任何结点相连，也就无法被遍历到

//    对深度优先遍历的方法进行重载以达到对所有结点均进行该操作    public void deepFirstSearch() {           isVisited = new boolean[getNumOfVertex()];//        对所有结点进行遍历，避免漏掉任何独立结点，若整个图连通，则只会调用一次        for (int i = 0; i < vertextList.size(); i++) {               if (!isVisited[i]) {                   deepFirstSearch(isVisited, i);            }        }        System.out.println();    }

4、代码测试

public static void main(String[] args) {           String vertexs[] = {   "A","B","C","D","E","F"};        Graph graph = new Graph(vertexs.length);        for (String vertex : vertexs) {               graph.insertVertex(vertex);        }//        为AB/AC/BC/BD/BE添加边        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);//        显示邻接矩阵        System.out.println("图的邻接矩阵为：");        graph.show();        System.out.println("图的深度优先遍历：");        graph.deepFirstSearch();      }

结果为：

从上图可以看出所有结点均被遍历到

2、广度优先遍历BFS

1、基本思想

2、思路分析

从某结点开始，找到该结点的第一个邻接结点，将该结点保存到队列中，接着再找出该结点的下一个邻接结点并入队…当当前节点的所有邻接结点均被遍历完毕，就出队一个元素并对该结点进行递归操作

3、代码实现

//图的广度优先遍历，队列的思想进行操作    public void boardFirstSearch(boolean[] isVisited, int i) {           int u;  //队列的头结点对应下标        int w;  //表示邻接结点        LinkedList queue = new LinkedList();    //使用链表的addLast和removeFirst模仿队列进行操作        System.out.print(getValueByIndex(i) + "\t"); //先打印输出下标为0的元素        isVisited[i] = true;    //设置该元素的true        queue.addLast(i);       //将该元素添加到队列尾部        while (!queue.isEmpty()) {               u = (Integer) queue.removeFirst();  //将队首元素出队并根据该元素获取其邻接结点的元素值            w = getFirstNeighbor(u);            while (w != -1) {               //没找到该结点的下一个邻接结点                if (!isVisited[w]) {                       //若该邻接结点并未被访问过就对该邻接结点打印输出并入队                    System.out.print(getValueByIndex(w) + "\t");                    isVisited[w] = true;                    queue.addLast(w);                }//                循环寻找移出队列元素的下一邻接结点                w = getNextNeighbor(u, w);            }        }    }

对方法进行封装达到对所有结点都遍历到，避免漏掉结点

public void boardFirstSearch() {           isVisited = new boolean[getNumOfVertex()];        for (int i = 0; i < getNumOfVertex(); i++) {               if (!isVisited[i]) {                   boardFirstSearch(isVisited, i);            }        }        System.out.println();    }

4、代码测试

public static void main(String[] args) {           String vertexs[] = {   "A","B","C","D","E","F"};        Graph graph = new Graph(vertexs.length);        for (String vertex : vertexs) {               graph.insertVertex(vertex);        }//        为AB/AC/BC/BD/BE添加边        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);//        显示邻接矩阵        System.out.println("图的邻接矩阵为：");        graph.show();        System.out.println("图的广度优先遍历：");        graph.boardFirstSearch();    }   }

运行结果为：

3、DFS与BFS的对比

可见对于同一个图，经过深度优先遍历和广度优先遍历所产生的的序列可能不同，当结点数和边数较多时，差异程度较明显