图是由定点的有穷非空集合和顶点之间的边的集合组成，通常表示为：G(V,E)，其中G表示一个图，V是图G中顶点的边集，E是图中边的集合。
图按照有无方向分为有向图和无向图。无向图由顶点和边构成，有向图由顶点和弧构成。开始点为弧尾，结束点为弧头。
图按照边的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫做有向完全图。若无重复的边或顶点到自身的边叫做简单图。
图的边或弧相关的数叫做权，这种带权的图通称为网。
图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称为强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。

———————————————————图的存储结构—————————————————
1.邻接矩阵

用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组存储图中边或弧的信息

/**
   * 一维数组，存储顶点
   */
  private Object[] elementData;

  /**
   * 二维数组存储边
   */
  private int[][] edges;

  /**
   * 顶点数量
   */
  private int size;
  public AdjacencyMatrixGraph(int initSize) {

      size = 0;
      elementData = new Object[initSize];
      edges = new int[initSize][initSize];
      visited = new Boolean[initSize];
  }

 //插入顶点
  public void insertV(Object o) {
      visited[size] = false;
      elementData[size] = o;
      size++;
  }
  //删除顶点
  public void deleteV(Object o) {
      int index = indexOf(o);
      if (index == -1) {
          throw new RuntimeException("顶点数据不存在");
      }

      /**
       * 查找存在包含该顶点的边
       */
      for (int i = 0; i < size; i++) {
          deleteEdge(i, index);
          deleteEdge(index, i);
      }

      visited[index] = false;
      size--;

  }

  public int indexOf(Object o) {
      for (int i = 0; i < size; i++) {
          if (o.equals(elementData[i])) {
              return i;
          }
      }
      return -1;
  }
  //删除边
  public void deleteEdge(int v1, int v2) {
      judge(v1, v2);
      edges[v1][v2] = 0;
      edges[v2][v2] = 0;
  }

  private void judge(int v1, int v2) {
      if (v1 < 0 || v2 < 0 || v1 >= size || v2 >= size) {
          throw new RuntimeException("顶点索引不正确");
      }
  }
  //插入边
  public void insertEdge(int v1, int v2) {
      judge(v1, v2);
      edges[v1][v2] = 1;
      edges[v2][v1] = 1;

  }

  public int getEdge(int v1, int v2) {
      judge(v1, v2);
      return edges[v1][v2];
  }

2.邻接表

（1）图中顶点用一个一维数组存储
（2）图中每个顶点vi的所有邻接点构成一个线性表。

    private static class EdgeNode {

        /**
         * 该节点的下标位置
         */
        private int adjvex;

        /**
         * 权值
         */
        private int weight;

        /**
         * 下一个边节点的指针
         */
        private EdgeNode edgeNode;

        public EdgeNode(int adjvex, int weight, EdgeNode edgeNode) {
            this.adjvex = adjvex;
            this.weight = weight;
            this.edgeNode = edgeNode;
        }

        public EdgeNode(int adjvex, int weight) {
            this.adjvex = adjvex;
            this.weight = weight;
        }

        public EdgeNode(int adjvex) {
            this.adjvex = adjvex;
        }

        public EdgeNode() {
        }
    }

    private static class VertexNode {
        private Object data;

        private EdgeNode edgeNode;

        public VertexNode() {
        }

        public VertexNode(Object data) {
            this.data = data;
        }

        public VertexNode(Object data, EdgeNode edgeNode) {
            this.data = data;
            this.edgeNode = edgeNode;
        }
    }

    private VertexNode[] nodes;

    /**
     * 实际顶点数量
     */
    private int size;
    public AdjListGraph(int initSize) {
        nodes = new VertexNode[initSize];
        size = 0;
        visited = new Boolean[initSize];
    }
    //插入顶点
    public void insertV(Object o) {
        VertexNode vertexNode = new VertexNode(o);
        nodes[size] = vertexNode;
        visited[size] = false;
        size++;
    }
    //删除顶点
    public void removeV(int v) {
        if (v < 0 || v >= size) {
            throw new RuntimeException("顶点索引不正确");
        }

        for (int i = 0; i < size; i++) {
            deleteE(i, v);
            deleteE(v, i);
        }

    }
     //插入边
    public void insertE(int v1, int v2, int weight) {
        judge(v1, v2);

        handleVertexNode(v1, v2, weight);

        handleVertexNode(v2, v1, weight);

    }

    private void handleVertexNode(int v1, int v2, int weight) {
        VertexNode v1VertexNode = nodes[v1];

        if (v1VertexNode.edgeNode == null) {
            v1VertexNode.edgeNode = new EdgeNode(v2, weight);
        } else {
            v1VertexNode.edgeNode = new EdgeNode(v2, weight, v1VertexNode.edgeNode);
        }
    }
    //删除边
    public void deleteE(int v1, int v2) {
        judge(v1, v2);

        fastRemoveE(v1, v2);

        fastRemoveE(v2, v1);

    }

    private void fastRemoveE(int v1, int v2) {

        //如果是顶点连接的第一个邻接节点，需将顶点的邻接重置
        EdgeNode edgeNode = nodes[v1].edgeNode;
        if (edgeNode != null && edgeNode.adjvex == v2) {
            nodes[v1].edgeNode = edgeNode.edgeNode;
        } else {

            //判断是不是链表上非第一个
            EdgeNode previous = null;
            edgeNode = edgeNode.edgeNode;
            while (edgeNode != null && edgeNode.adjvex != v2) {

                previous = edgeNode;
                edgeNode = edgeNode.edgeNode;
            }

            if (edgeNode != null) {
                previous.edgeNode = edgeNode.edgeNode;

            }
        }

    }

    private void judge(int v1, int v2) {
        if (v1 < 0 || v2 < 0 || v1 >= size || v2 >= size) {
            throw new RuntimeException("顶点索引不正确");
        }
    }

3.十字链表

4.邻接多重表

5.边集数组

由两个一维数组构成。一个存储顶点的信息，另一个存储边的信息，这边数组每个数据元素由一条边的起点下标、终点下标和权值组成。

———————————————————图的遍历———————————————————
1.深度优先遍历

从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。

邻接矩阵深度优先遍历：递归

    /**
     * 节点是否被遍历
     */
    private Boolean[] visited;
  /**
     * 邻接矩阵的深度优先算法
     * 选定一个顶点进行遍历，判断是否被遍历到
     * 如果为遍历到，则遍历这个节点相关联的边节点
     */
    public void dfs() {

        for (int i = 0; i < size; i++) {

            if (!visited[i]) {
                dfs(i);
            }
        }

    }

    /**
     * 从第i个节点进行深度遍历
     *
     * @param i
     */
    private void dfs(int i) {
        visited[i] = true;
        System.out.println(elementData[i] + "   ");

        for (int j = 0; j < size; j++) {
            if (edges[i][j] == 1 && !visited[j]) {
                dfs(j);
            }
        }

    }

邻接矩阵深度优先遍历：非递归（使用栈）

private Boolean[] visited;
 private Stack<Object> stack = new Stack<>();
 public void stackDfs() {

        visited[0] = true;
        System.out.println(elementData[0]);

        stack.push(elementData[0]);

        int index = 0;
        while (!stack.isEmpty()) {
            int v = getNextIndex(index);
            if (v == -1) {
                stack.pop();
            } else {
                visited[v] = true;

                System.out.println(elementData[v]);

                stack.push(elementData[v]);

                index = v;

            }
        }

    }

    public int getNextIndex(int index) {

        for (int i = 0; i < size; i++) {
            if (edges[index][i] == 1 && !visited[i]) {
                return i;
            }
        }

        return -1;
    }

邻接表深度优先遍历：递归

    private Boolean[] visited;

   /**
     * 邻接链表的深度优先算法
     *
     * 判断相邻的边的下标是否被遍历到，如果未遍历，则从这个节点开始遍历
     *
     *
     * 递归算法实现
     */
    public void dfs() {

        for (int i = 0; i < size; i++) {
            if (!visited[i]) {
                dfs(i);
            }
        }

    }

    public void dfs(int i) {

        visited[i] = true;
        System.out.println(nodes[i].data);

        EdgeNode edgeNode = nodes[i].edgeNode;
        while (edgeNode != null) {
            if (!visited[edgeNode.adjvex]) {
                dfs(edgeNode.adjvex);
            }
            edgeNode = edgeNode.edgeNode;
        }
    }

邻接表深度优先遍历：栈

    private Boolean[] visited;

    private Stack<VertexNode> vertexNodeStack = new Stack<>();

    /**
     * 使用栈对链表进行遍历
     */
    public void stackDfs() {

        visited[0] = true;

        System.out.println(nodes[0].data);
        vertexNodeStack.push(nodes[0]);

        //栈不空，则判断栈顶元素的向邻接节点
        while (!vertexNodeStack.isEmpty()) {
            int adjListIndex = getIndex(vertexNodeStack.peek());
            if(adjListIndex == -1){
                vertexNodeStack.pop();
            }else {
                visited[adjListIndex] = true;
                System.out.println(nodes[adjListIndex].data);

                vertexNodeStack.push(nodes[adjListIndex]);
            }

        }

    }

    public int getIndex(VertexNode v) {
        EdgeNode edgeNode = v.edgeNode;
        while (edgeNode != null) {
            if (!visited[edgeNode.adjvex]) {
               return edgeNode.adjvex;
            }
            edgeNode = edgeNode.edgeNode;
        }

        return  -1;
    }

2.广度优先遍历

一层一层的顶点访问

邻接矩阵广度优先遍历：

  private Queue<Object> objectQueue = new ArrayDeque<>();

    /**
     * 队列实现广度优先遍历算法
     *
     * 类似层序遍历
     *
     * 先入队列，则先出队列
     */
    public void bfs() {
        visited[0] = true;

        objectQueue.add(elementData[0]);
        System.out.println(elementData[0]);

        int index = 0;
        while (!objectQueue.isEmpty()) {

            objectQueue.remove();

            for (int i = 0; i < size; i++) {
                if (edges[index][i] == 1 && !visited[i]) {

                    visited[i] = true;

                    objectQueue.add(elementData[i]);

                    System.out.println(elementData[i]);
                }
            }

        }

    }

邻接表广度优先遍历：

   private Queue<VertexNode> vertexNodeQueue = new ArrayDeque<>();

    /**
     * 队列实现广度优先遍历算法
     *
     * 类似层序遍历
     *
     * 先入队列，则先出队列
     */
    public void bfs() {
        visited[0] = true;

        vertexNodeQueue.add(nodes[0]);
        System.out.println(nodes[0].data);

        int index = 0;
        while (!vertexNodeQueue.isEmpty()) {

            vertexNodeQueue.remove();

            EdgeNode edgeNode = nodes[index].edgeNode;
            while (edgeNode !=null){
                if(!visited[edgeNode.adjvex]){
                    vertexNodeQueue.add(nodes[edgeNode.adjvex]);

                    visited[edgeNode.adjvex] = true;
                    System.out.println(nodes[edgeNode.adjvex].data);
                }

                edgeNode = edgeNode.edgeNode;

            }

        }

    }