图

为什么要有图？
线性表局限于一个直接前驱和一个直接后继的关系，树也只能有一个直接前驱也就是父节点
当我们需要表示一种多对多的关系就需要用到图。
图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。结点也可以称为顶点。如图：
在这里插入图片描述
图的常用概念：

图的表示方式

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

邻接矩阵
邻接表

创建图

采用邻接矩阵的方法
思路：用邻接矩阵创建图时，需要以下属性，一个list，用来存放图的所有顶点，顶点用字符串表示；一个二维数组int[][]，用来表示图的关系，0表示顶点之间不连通，1表示连通；一个数int，用来存放图的边的总数。
创建图时，需分别创建顶点和创建每一条边。

java">	package graph;



import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 无相图
 */
public class graph {
    public List<String> vertexList;//存放顶点
    public int[][] edges;//存放图
    public int numOfEdges;//存放图的边的数量
    public boolean[] visit;//存放是否被访问过

    public static void main(String[] args) {
        String[] vertexs={"1","2","3","4","5","6","7","8"};
        graph graph=new graph(8);
        for(String n:vertexs){
            graph.insertVertex(n);
        }
        graph.insertEdges(0,1,1);
        graph.insertEdges(0,2,1);
        graph.insertEdges(1,3,1);
        graph.insertEdges(1,4,1);
        graph.insertEdges(3,7,1);
        graph.insertEdges(4,7,1);
        graph.insertEdges(2,5,1);
        graph.insertEdges(2,6,1);
        graph.insertEdges(5,6,1);
        graph.showGraph();
        graph.dfs();
        System.out.println("广度优先");
        graph.bfs();

    }
    public graph(int n){
        vertexList=new ArrayList<>(n);
        edges=new int[n][n];
    }
    /**
     * 增加顶点
     * @param vertex
     */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    /**
     * 增加边
     * @param v1 第一个顶点的下标
     * @param v2 第二个顶点的下标
     * @param weight 边的权值，0表示不连通
     */
    public void insertEdges(int v1,int v2, int weight){
        edges[v1][v2]=weight;
        edges[v2][v1]=weight;
        numOfEdges++;
    }

    /**
     * 显示图
     */
    public void showGraph(){
        for (int i = 0; i <edges.length ; i++) {
            System.out.println(Arrays.toString(edges[i]));
        }
    }
}

深度优先遍历

在这里插入图片描述

深度优先遍历大意是，在遍历图的时候，从第一个顶点出发，输出它，然后找到它的第一个相邻顶点，如果该顶点没被访问过，就对它进行深度优先访问，如果访问过了，就找到第一个顶点的下一个相邻结点，并对它重新判断。
也就是说，进行深度优先遍历时，会从第一个顶点，一直顺着连接访问顶点的第一个相邻顶点，等到所有的第一个相邻顶点输出了，在回溯到前一层访问对应顶点的第二个相邻顶点。
具体思路：里面运用了递归的思想，需要一个boolean数组存放每一个顶点是否访问过

输出该顶点，并把它设为已访问。最开始就是第一个顶点
获得它的所有相邻顶点下标，保存为一个数组，这个数组保存的是该顶点所有未被访问的相邻顶点，最初获得时，肯定是都没有被访问的，随着循环，应该把已经访问过的顶点移除
如果数组长度大于0，进行循环，每次获得数组第一个数，它代表顶点的第一个相邻顶点（之后就表示第二个、第三个。。。相邻顶点），判断这个顶点是否访问过。
如果没有访问，对他进行深度优先访问，也就是递归，之后，由于访问过它，把它从数组中移除
如果访问过，直接移除它。
循环结束后，已经访问了每一个有连接的顶点，但有可能会出现没有和任何顶点相连的顶点，这时候重载算法，对每一个顶点执行该算法，保证能够访问到每一个顶点。

java">/**
     * 深度优先遍历
     * @param i 顶点的下标
     */
    public void dfs(int i){
        //访问i结点
        visit[i]=true;
        System.out.print(vertexList.get(i)+"->");
        //获得i的所有邻接结点
        List<Integer> neighbors = getNeighbors(i);
        //当i有未访问的邻接结点时
        while (neighbors.size()>0){
            //获得i的第一个邻接结点
            int j=neighbors.get(0);
            //如果没有访问过它
            if(!visit[j]){
                //访问，并将它删除
                dfs(j);
                neighbors.remove(0);
            }else {
                //说明访问过了，把它删除
                neighbors.remove(0);
            }
        }
    }

    /**
     * 重载深度优先遍历,如果有结点没有跟其他结点联通，就会访问不到
     */
    public void dfs(){
        visit=new boolean[vertexList.size()];
        for (int i = 0; i <vertexList.size() ; i++) {
            if(!visit[i]){
                dfs(i);
            }
        }
    }
    /**
     * 获取i的邻接结点
     * @param i
     * @return
     */
    public List<Integer> getNeighbors(int i){
        List<Integer> res=new ArrayList<>();
        for (int j = 0; j <vertexList.size() ; j++) {
            if(edges[i][j]!=0){
                res.add(j);
            }
        }
        return res;
    }

广度优先遍历

在这里插入图片描述
广度优先遍历简单来说就是，输出一个顶点，然后输出这个顶点的所有相邻顶点，然后按顺序从第二个顶点开始，输出第二个顶点没被输出过的所有相邻节点，然后按顺序从第三个顶点开始，输出第三个顶点没被输出过的所有相邻节点，一直到所有顶点被输出。按照上图，简单来说就是一层一层输出，先输出1，再输出1的所有相邻顶点23，然后。。。
具体思路：为了知道顶点输出的顺序，用一个队列保存输出后的顶点

输出顶点，设为已访问，把顶点加入队列，这时也就是图的第一个顶点，队列的作用是保存已输出的顶点和输出顺序。
如果队列不为空，进入循环
接收并弹出队列的头，最开始的时候就是第一个顶点，获得它的相邻顶点集合。
如果集合长度大于0，进入循环。此循环的目的是输出队列头的所有相邻顶点，集合中存放的是未访问的相邻顶点，每次访问一个顶点，就把它从集合中删除，直到全部访问，集合就空了
弹出并保存集合的第一个数据，也就是顶点的第一个相邻顶点，判断它是否被访问，如果没有，输出它并把它加入队列，如果没有，不用操作，因为弹出用的是remove，此时进入下一次循环，弹出下一个数，访问过的顶点就已经被删除了
直到循环退出，已经输出了第一个顶点的所有相邻顶点，此时会弹出队列的头，也就是第二个输出的顶点，接着进入循环输出它的所有相邻顶点，直到队列为空，也就是检查过每一个顶点的全部相邻顶点，程序结束
同理，考虑到无连接的顶点，通过for循环对每一个顶点进行广度优先遍历

java"> /**
     * 广度优先算法
     * @param i
     */
    public void bfs(int i){
        int u;
        int w;
        //一个队列，
        LinkedList<Integer> queue=new LinkedList<>();
        //访问i，并把它加入队列
        System.out.print(vertexList.get(i)+"=>");
        visit[i]=true;
        queue.addLast(i);
        //队列不为空时
        while (!queue.isEmpty()){
            //获得队列头
            u=queue.removeFirst();
            //查找它的所有未访问的邻接结点
            List<Integer> neighbors = getNeighbors(u);
            //获得每一个未访问的邻接结点，访问并删除它，并把它加入队列
            while (neighbors.size()>0){
                w=neighbors.remove(0);
                if(!visit[w]){
                    System.out.print(vertexList.get(w)+"=>");
                    visit[w]=true;
                    queue.addLast(w);
                }
            }
        }
    }

    /**
     * 重载，保证不相连的结点也被访问到
     */
    public void bfs(){
        visit=new boolean[vertexList.size()];
        for (int i = 0; i <vertexList.size() ; i++) {
            if(!visit[i]){
                bfs(i);
            }
        }
    }