2020-05-02

图

图的概念：

https://www.cnblogs.com/songgj/p/9107797.html

图的展示方式

1. 邻接表
2. 邻接矩阵(相通为1，不通为0)

邻接矩阵实现

Graph类(和顶点数组有关)

//顶点数组
public class Graph {
    private Vertex[] vertex;  //存放顶点的矩阵
    private int currentSize;  //下标
    int[][] adjMat;   //二维矩阵存放顶点之间的关系


    public Graph(int size){
        vertex=new Vertex[size];  //设置顶点数组大小
        adjMat=new int[size][size]; //二维数组默认为0
    }

    //向图中添加顶点
    public  void  addVertex(Vertex v){
        vertex[currentSize++]=v;
    }

	//向图中添加边
    public void addEdge(String v1,String v2){
        int index1=0;
        int index2=0;
        for(int i=0;i<vertex.length;i++){
            if(vertex[i].getValue().equals(v1)){  //如果要添加的和v1是相等的 就把下标给index1
                index1=i;
                break;
            }
        }
        for(int i=0;i<vertex.length;i++){
            if (vertex[i].getValue().equals(v2)) {  //如果要添加的和v2是相等的 就把下表给index2
                index2=i;
                break;
            }
        }
        //相通给1
        adjMat[index1][index2]=1;  //把对应的位置变1
        adjMat[index2][index1]=1;

    }

}

Vertex类(顶点类)

//顶点类
public class Vertex {
     private String value;

    public Vertex(String value) {
        super();
        this.value = value;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value;
    }

}

TestGraph类(测试类)

public class TestGraph {
    public static void main(String[] args) {
     //创建五个顶点
        Vertex v1=new Vertex("A");
        Vertex v2=new Vertex("B");
        Vertex v3=new Vertex("C");
        Vertex v4=new Vertex("D");
        Vertex v5=new Vertex("E");
        Graph g=new Graph(5);
     //增加节点
        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);
        g.addVertex(v5);
     //增加边
        g.addEdge("A","C");
        g.addEdge("B","C");
        g.addEdge("A","B");
        g.addEdge("B","D");
        g.addEdge("B","E");
     //打印二维矩阵
        for(int[] a:g.adjMat){
            System.out.println(Arrays.toString(a));
        }

    }
}

结果分析

结果展示

图的遍历

1. 深度优先搜索算法(用栈的方式思考)
2. 广度优先搜索算法(用队列的方式思考)

两种遍历讲解

举例图：

深度优先搜索算法(DFS)

走迷宫一样，当前顶点走到死路就返回一步看能不能再走，把死路位置的顶点弹出去

1. 栈先放入A顶点 (栈内：A)
2. 搜索邻接矩阵中第一行A顶点可以到达哪个顶点
3. 栈再放入B顶点 (栈内：B A)
4. 搜索邻接矩阵中第二行B顶点可以到达哪个顶点
5. 栈再放入C顶点 (栈内：C B A)
6. 搜索邻接矩阵中第三行C顶点可以到达哪个顶点
7. 没有可以到达的顶点因此C顶点从栈弹出 (栈内：B A)  --已经搜索到的C弹出(C)
8. 返回到栈顶B顶点查看还可以到达哪个顶点
9. 栈再放入D顶点 (栈内: D B A)
10. 搜索邻接矩阵中第四行D顶点可以到达哪个顶点
11. 没有可以到达的顶点因此D顶点从栈弹出 (栈内：B A) --已经搜索到的D弹出(C D)
12. 返回到栈顶B顶点查看还可以到达哪个顶点
13. 栈再放入E顶点 (栈内：E B A)
14. 搜索邻接矩阵中第五行E顶点可以到达哪个顶点
15. 没有可以到达的顶点因此E顶点从栈弹出 (栈内：B A) --已经搜索到的E弹出(C D E)
16. 五个顶点都被遍历过后弹出栈内元素(先出B后出A)
17. 最终遍历顺序是： A B E D C

广度优先搜索算法(BFS)

从当前顶点一条路走到死，走死顶点就出队。让屁股后面的顶点继续走到死

1. 队列先放入A顶点 (队列内：A)
2. 搜索邻接矩阵中第一行A顶点可以到达哪个顶点
3. 队列再放入B顶点 (队列内：B A)
4. 搜索邻接矩阵中第一行A顶点还可以到达哪个顶点 
5. 队列再放入C顶点 (队列内：C B A)
6. 现在A没有可以到达的顶点因此A顶点出队(队列内：C B) --已经搜索到的A出队(A)
7. 现在搜索B还可以到达哪些顶点
8. 队列再放入D顶点 (队列内：D C B)
9. 在搜索B还可以到达哪些顶点
10. 队列再放入E顶点 (队列内：E D C B)
11. 五个顶点都被遍历过后弹出栈顶元素(先出B后出C然后D最后E)
12. 最终遍历顺序是： A B C D E