java 数据结构---图---持续补充

1. 线性表和树，线性表局限于一个直接前驱和一个直接后继，树只有一个直接前驱（父结点）
2. 当我们需要多对多的关系时，就需要图这种数据结构

1. 边是两个结点之间的连接
2. 顶点就是结点
3. 无向图，顶点之间的连接没有方向，A-B，既可以从A到B，又可以从B到A，而有向图，只能一个方向
4. 路径，一个顶点到另一个顶点的路径，比如D->C的路径有D-B-C和D-A-B-C
   
5. 有向图，顶点之间连接有方向
6. 带权图，顶点直接的连接带有权值，这种图又名网

1. 邻接矩阵（二维数组表示）
   

1. 通过1和0表示两个顶点，是否存在直接连接，比如arr[0][1]=1,那么表示0这个顶点和1这个顶点相互连接

2. 邻接表（链表）
   

1. 思路

1. 通过一个List保存顶点，
2. 通过二维数组，也就是用邻接矩阵的方式表示顶点间的连接关系

2. 运行效果
   
   3.代码

import java.util.ArrayList;
import java.util.Arrays;

public class Test {

    public static void main(String[] args) {
        String[] arr = {"0","1","2","3","4","5"};
        Graph graph = new Graph(arr.length);
        graph.insertVertexs(arr);
        graph.insetEdge(0,1);
        graph.insetEdge(0,4);
        graph.insetEdge(0,3);
        graph.insetEdge(0,2);
        graph.insetEdge(1,4);
        graph.insetEdge(2,4);
        graph.insetEdge(2,5);
        graph.insetEdge(3,5);
        graph.insetEdge(4,5);
        graph.showGraph();

    }

}


class Graph{
    private ArrayList vertexList;//存储顶点的集合
    private int[][] edges;//存储图各顶点连接关系的邻接矩阵
    private int numOfEdges;//表示边的数目

    
    public Graph(int n){
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;
    }

    
    public int getNumOfVertex(){
        return vertexList.size();
    }

    
    public int getNumOfEdges(){
        return numOfEdges;
    }

    
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

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

    
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    
    public void insertVertexs(String[] vertexs){
        for (String s : vertexs){
            vertexList.add(s);
        }
    }

    
    public void insertEdge(int v1,int v2,int flag){
        //因为是无向图，所以边既可以从v1到v2，也可以从v2到v1
        edges[v1][v2]=flag;//A-B可以连接
        edges[v2][v1]=flag;//B-A可以连接
        numOfEdges++;//边数++
    }
    //重载，如果不传入flag，就默认用1表示两个顶点相互连接，两个顶点的边权值为1
    public void insetEdge(int v1,int v2){
        insertEdge(v1,v2,1);
    }


    public void showGraph(){
        System.out.println("图的领接矩阵为：");
        for (int[] row : edges){
            System.out.println(Arrays.toString(row));
        }
    }
}

1. 图有两种遍历方式，深度优先（DFS）遍历和广度优先（BFS）遍历

1. 深度优先搜索（Depth First Search）
   

1. 深度优先遍历，从初始结点出发，访问邻接的第一个结点，然后以被访问的结点，访问邻接它的下一个结点，每次访问完当前结点后，标记此结点已经访问过，然后访问当前结点的第一个邻接结点
2. 此种访问策略，是优先向下挖掘深入，不是对一个结点的所有邻接结点横向访问，显然，深度优先搜索是一个递归的过程

2. 运行结果
   
3. 代码
   

private boolean[] vertexVisited;//用来标识结点是否被访问过，true标识被访问过

    
    public Graph(int n){
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;
        vertexVisited = new boolean[n];
    }

    
    public int getFirstNeighbor(int index){
        for(int j = 0;j0){
                return j;
            }
        }
        return -1;
    }

    
    public int getNextNeighbor(int v1,int v2){
        for(int j = v2+1;j0){
                return j;
            }
        }
        return -1;
    }

    
    public void dfs(){
        for (int i = 0;i 
2. 广度优先遍历 
 
 
广度优先搜索(Broad First Search):类似分层搜索，需要使用队列以保证访问过结点的顺序，以便按顺序访问这些结点的邻接结点
 
 
 
 
  
访问初始结点，标记为已访问，入队列。
然后出队列，直到队列为空，算法结束
当一个结点出队列后，找到第一个邻接结点，不存在继续出队列，存在，就访问这个邻接结点，然后标记为已访问，入队列
然后继续查找刚刚出队列的内个结点的下一个邻接结点，如果没有了就继续出队列
 
 
 
 
运行结果
 
代码(用到的数组和一些方法，在深度优先遍历的代码块中)
 
 
	
    public void bfs(){
        for (int i = 0;i();//队列

        System.out.print(getValueByIndex(i)+"=>");//先访问当前结点输出
        isVisited[i] = 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)+"=>");//访问这个结点，输出
                    isVisited[w] = true;//然后标记为已访问
                    queue.addLast(w);//入队列
                }
                w = getNextNeighbor(u,w);//然后广度遍历，获取下一个邻居
            }
        }
    }
 
大家可以用这个例子试一试，深度和广度的区别