图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

图的基本概念

1、顶点（vertex）：图中的数据元素；
2、边（edge）：图中连接这些顶点的线；
3、路径（Path）：在无向图中，若从顶点Vi出发有一组边可到达顶点Vj，则称顶点Vi到顶点Vj的顶点序列为从顶点Vi到顶点Vj的路径；
4、无向图：如果图中任意两个顶点之间的边都是无向边，则称该图为无向图；
5、有向图：如果图中任意两个顶点之间的边都是有向边，则称该图为有向图；
6、有权图：这里的权可以理解成一个数值，就是说节点与节点之间这个边有一个数值与它对应，这个边的值就是代表着两个节点之间的关系，这种图被称为有权图；
7、顶点的度：连接顶点的边的数量称为该顶点的度。对于有向图一个顶点的度有入度和出度之分。

  • 入度是以该顶点为端点的入边数量， 记为ID(V)。
  • 出度是以该顶点为端点的出边数量， 记为OD(V)。

图 - 图1

图的存储结构

1、邻接矩阵（数组）：用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
图 - 图2
2、邻接表（链表）：由表头节点和表节点两部分组成，图中每个顶点均对应一个存储在数组中的表头节点。如果这个表头节点所对应的顶点存在邻接节点，则把邻接节点依次存放于表头节点所指向的单向链表中。
图 - 图3

图的遍历

从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。遍历过程中得到的顶点序列称为图遍历序列。

1、深度优先搜索遍历（DFS）
深度优先搜索思想：
（1）深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接结点作为初始结点，访问它的第一个邻接结点，可以这样理解：每次访问完当前节点后首先访问当前结点的第一个邻接结点。
（2）这样的访问策略是优先往纵向挖掘深入，而不是对一个结点的邻接结点进行横向访问。
（3）深度优先遍历是一个递归过程。

图 - 图4

2、广度优先搜索遍历（BFS）
广度优先搜索思想：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。

图 - 图5

  1. /**
  2.  * 图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
  3.  */
  4. public interface Graph<V, E> {
  6.     /**
  7.      * 新增顶点
  8.      */
  9.     void addVertex(V v);
  11.     /**
  12.      * 新增边
  13.      * @param v1 顶点1
  14.      * @param v2 顶点2
  15.      * @param e 权值
  16.      */
  17.     void addEdge(V v1, V v2, E e);
  19.     /**
  20.      * 获取边
  21.      * @param v1 顶点1
  22.      * @param v2 顶点2
  23.      */
  24.     E getEdge(V v1, V v2);
  26.     /**
  27.      * 获取顶点数量
  28.      */
  29.     int size();
  31.     /**
  32.      * 获取边数量
  33.      */
  34.     int edgeSize();
  36.     /**
  37.      * 获取顶点的索引
  38.      */
  39.     int indexOfVertex(V v);
  40. }
  1. /**
  2.  * 《图》
  3.  *   邻接矩阵（数组）：用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
  4.  *
  5.  *                          顶点数组：   A B C D E
  6.  *       A                              0 1 2 3 4
  7.  *     /   \
  8.  *    B     C     --->      边数组：    A  B  C  D  E
  9.  *   / \                            A  0  1  1  0  0
  10.  * D -- E                           B  1  0  0  1  1
  11.  *                                  C  1  0  0  0  0
  12.  *                                  D  0  1  0  0  1
  13.  *                                  E  0  1  0  1  0
  14.  */
  15. public class ArrayGraph<V, E> implements Graph<V, E> {
  17.     /**
  18.      * 存放顶点的一维数组
  19.      */
  20.     private Object[] vertexArray;
  22.     /**
  23.      * 存放边的二维数组
  24.      */
  25.     private Object[][] edgeArray;
  27.     /**
  28.      * 边的实际数量
  29.      */
  30.     private int edgeSize;
  32.     /**
  33.      * 顶点的实际数量
  34.      */
  35.     private int vertexSize;
  37.     /**
  38.      * 顶点的最大数量
  39.      */
  40.     private int vertexMaxSize;
  42.     public ArrayGraph(int vertexMaxSize) {
  43.         this.vertexSize = 0;
  44.         this.vertexMaxSize = vertexMaxSize;
  45.         this.vertexArray = new Object[vertexMaxSize];
  46.         this.edgeArray = new Object[vertexMaxSize][vertexMaxSize];
  47.     }
  49.     /**
  50.      * 根据索引获取顶点
  51.      */
  52.     public Object getVertexOfIndex(int index) {
  53.         return vertexArray[index];
  54.     }
  56.     /**
  57.      * 获取顶点的索引
  58.      */
  59.     @Override
  60.     public int indexOfVertex(V v) {
  61.         for (int i = 0; i < vertexSize; i++) {
  62.             if (vertexArray[i] != null && Objects.equals(vertexArray[i], v)) {
  63.                 return i;
  64.             }
  65.         }
  66.         return -1;
  67.     }
  69.     /**
  70.      * 新增顶点
  71.      */
  72.     @Override
  73.     public void addVertex(V v) {
  74.         if (vertexSize >= vertexMaxSize) {
  75.             System.out.println("新增失败，图顶点已满！");
  76.             return;
  77.         }
  78.         vertexArray[vertexSize++] = v;
  79.         // 同一顶点组成的边权值为0
  80.         edgeArray[indexOfVertex(v)][indexOfVertex(v)] = 0;
  81.     }
  83.     /**
  84.      * 新增边
  85.      */
  86.     @Override
  87.     public void addEdge(V v1, V v2, E e) {
  88.         int index1 = indexOfVertex(v1);
  89.         if (index1 == -1) {
  90.             System.out.println("新增失败，顶点不存在" + v1.toString());
  91.             return;
  92.         }
  93.         int index2 = indexOfVertex(v2);
  94.         if (index2 == -1) {
  95.             System.out.println("新增失败，顶点不存在" + v2.toString());
  96.             return;
  97.         }
  98.         edgeArray[index1][index2] = e;
  99.         edgeArray[index2][index1] = e;
  100.         edgeSize++;
  101.     }
  103.     /**
  104.      * 获取边
  105.      * @return
  106.      */
  107.     @Override
  108.     public E getEdge(V v1, V v2) {
  109.         int index1 = indexOfVertex(v1);
  110.         if (index1 == -1) {
  111.             System.out.println("获取失败，顶点不存在" + v1.toString());
  112.             return null;
  113.         }
  114.         int index2 = indexOfVertex(v2);
  115.         if (index2 == -1) {
  116.             System.out.println("获取失败，顶点不存在" + v2.toString());
  117.             return null;
  118.         }
  119.         return (E) edgeArray[index1][index2];
  120.     }
  122.     /**
  123.      * 获取顶点数量
  124.      */
  125.     @Override
  126.     public int size() {
  127.         return this.vertexSize;
  128.     }
  130.     /**
  131.      * 获取边数量
  132.      */
  133.     @Override
  134.     public int edgeSize() {
  135.         return this.edgeSize;
  136.     }
  138.     /**
  139.      * 存放边的二维数组
  140.      */
  141.     public Object[][] getEdgeArray() {
  142.         return this.edgeArray;
  143.     }
  145.     /**
  146.      * 获取指定顶点的第一个邻接顶点
  147.      * @return
  148.      */
  149.     private int getFirstNeighbor(int index) {
  150.         for (int i = 0; i < vertexArray.length; i++) {
  151.             if (edgeArray[index][i] != null) {
  152.                 return i;
  153.             }
  154.         }
  155.         return -1;
  156.     }
  158.     /**
  159.      * 根据指定顶点的前一个邻接顶点获取下一个邻接顶点
  160.      * @return
  161.      */
  162.     private int getNextNeighbor(int index, int w) {
  163.         for (int i = w + 1; i < vertexArray.length; i++) {
  164.             if (edgeArray[index][i] != null) {
  165.                 return i;
  166.             }
  167.         }
  168.         return -1;
  169.     }
  171.     /**
  172.      * 深度优先搜索遍历（DFS）
  173.      */
  174.     public void dfs() {
  175.         if (vertexSize == 0) {
  176.             System.out.println("图为空");
  177.             return;
  178.         }
  179.         boolean[] isVisted = new boolean[vertexSize];
  180.         dfs(0, isVisted);
  181.     }
  183.     /**
  184.      * 深度优先搜索遍历算法步骤
  185.      * 1）访问初始节点v，并标记节点v以访问
  186.      * 2）查找节点v的第一个邻接节点w
  187.      * 3）若w存在，执行4，若w不存在，回到第一步，从v的下一个节点继续
  188.      * 4）若w未被访问，对w进行深度优先遍历递归
  189.      * 5）若w被访问，以下一个邻接节点作为初始节点进行递归
  190.      */
  191.     private void dfs(int v, boolean[] isVisted) {
  192.         System.out.printf("%s\t", vertexArray[v]);
  193.         // 设置为访问过
  194.         isVisted[v] = true;
  195.         // 获取指定顶点的第一个邻接顶点
  196.         int w = getFirstNeighbor(v);
  197.         while (w != -1) {
  198.             // 当前顶点没有访问过
  199.             if (!isVisted[w]) {
  200.                 dfs(w, isVisted);
  201.             }
  202.             // 访问下一个邻接顶点
  203.             w = getNextNeighbor(v, w);
  204.         }
  205.     }
  207.     /**
  208.      * 广度优先搜索遍历（BFS）
  209.      */
  210.     public void bfs() {
  211.         if (vertexSize == 0) {
  212.             System.out.println("图为空");
  213.             return;
  214.         }
  215.         boolean[] isVisted = new boolean[vertexSize];
  216.         bfs(0, isVisted);
  217.     }
  219.     /**
  220.      * 广度优先搜索遍历算法步骤
  221.      * 1）访问初始节点v并标记v为已访问
  222.      * 2）节点v入队列
  223.      * 3）当队列非空时，继续执行，否则算法结束
  224.      * 4）出队列，取得队头节点u
  225.      * 5）查找节点u的第一个邻接节点w
  226.      * 6）若节点u的邻接节点w不存在，进行步骤3，否则循环执行以下三个步骤
  227.      *  6.1若w未被访问，则访问节点w并记为已访问
  228.      *  6.2节点w入队列
  229.      *  6.3查找节点u的继ww邻接节点的下一个邻接节点w，转到步骤6
  230.      */
  231.     private void bfs(int v, boolean[] isVisted) {
  232.         // 输出初始结点v
  233.         System.out.printf("%s\t", vertexArray[v]);
  234.         // 设置为访问过
  235.         isVisted[v] = true;
  236.         // 将访问的结点v加入队列中
  237.         List<Integer> list = new ArrayList();
  238.         list.add(v);
  239.         // 队列不为空时循环执行
  240.         while (!list.isEmpty()) {
  241.             // 获取队列头结点
  242.             int u = list.remove(0);
  243.             // 获取第一个邻接顶点
  244.             int w = getFirstNeighbor(u);
  245.             while (w != -1) {
  246.                 if (!isVisted[w]) {
  247.                     // 输出初始结点w
  248.                     System.out.printf("%s\t", vertexArray[w]);
  249.                     // 设置为访问过
  250.                     isVisted[w] = true;
  251.                     // 加入队列
  252.                     list.add(w);
  253.                 }
  254.                 // 访问下一个邻接顶点
  255.                 w = getNextNeighbor(u, w);
  256.             }
  257.         }
  258.     }
  260.     /**
  261.      * 打印数组
  262.      */
  263.     public void print() {
  264.         for (int i = 0; i < vertexSize; i++) {
  265.             for (int j=0; j < vertexSize; j++) {
  266.                 System.out.printf("%s\t", edgeArray[i][j] == null ? "-" : edgeArray[i][j]);
  267.             }
  268.             System.out.println();
  269.         }
  270.     }
  272.     public static void main(String[] args) {
  273.         ArrayGraph<String, Integer> arrayGraph = new ArrayGraph<>(5);
  274.         // 添加顶点
  275.         arrayGraph.addVertex("A");
  276.         arrayGraph.addVertex("B");
  277.         arrayGraph.addVertex("C");
  278.         arrayGraph.addVertex("D");
  279.         arrayGraph.addVertex("E");
  280.         // 添加边
  281.         arrayGraph.addEdge("A", "B", 1);
  282.         arrayGraph.addEdge("A", "C", 1);
  283.         arrayGraph.addEdge("B", "D", 1);
  284.         arrayGraph.addEdge("B", "E", 1);
  285.         arrayGraph.addEdge("D", "E", 1);
  286.         System.out.println("打印邻接矩阵:");
  287.         arrayGraph.print();
  289.         System.out.println("获取顶点数量:" + arrayGraph.size());
  290.         System.out.println("获取边数量:" + arrayGraph.edgeSize());
  291.         System.out.println("获取边:" + arrayGraph.getEdge("A", "B"));
  292.         System.out.println("深度优先搜索遍历（DFS）：");
  293.         arrayGraph.dfs();
  294.         System.out.println();
  295.         System.out.println("广度优先搜索遍历（BFS）：");
  296.         arrayGraph.bfs();
  297.     }
  298. }