[数据结构与算法]LeetCode 图相关知识

图论知识点众多，LeetCode最常涉及的便是有向图与无向图的遍历算法。

例如下有向图，使用 邻接矩阵 与 邻接表 存储。

????????

邻接矩阵

使用N*N的二维数组存储，a[i][j] = 1意思着 i -> j存在连接，也可以用来存权。

邻接表

使用N个元素的一维数组分别存储一个列表，列表中存储与第i个元素相连的所有元素。

构造邻接矩阵与邻接表?

? ? ? ? ?构造邻接矩阵

    public int[][] assemMap(){
        // 构造图的临界矩阵
        int nodeCount = 5;
        int[][] result = new int[nodeCount][nodeCount];

        result[0][2]=1;
        result[0][4]=1;

        result[1][0]=1;
        result[1][2]=1;

        result[2][3]=1;

        result[3][4]=1;

        result[4][3]=1;

        return result;
    }

? ? ? ? 构造邻接表

? ? ? ? ? ? ? ADT

    public static class Link{
        public int value;
        public List<Link> neighbors = new ArrayList<>();

        public Link(int value) {
            this.value = value;
        }
    }

? ? ? ? ? ? ?组装邻接表?

public Link[] assemMap2() {
        // 构造图的临界表
        Link link0 = new Link(0);
        Link link1 = new Link(1);
        Link link2 = new Link(2);
        Link link3 = new Link(3);
        Link link4 = new Link(4);

        link0.neighbors.add(link2);
        link0.neighbors.add(link4);

        link1.neighbors.add(link0);
        link1.neighbors.add(link2);

        link2.neighbors.add(link3);

        link3.neighbors.add(link4);

        link4.neighbors.add(link3);

        Link[] linkMap = new Link[5];

        linkMap[0] = link0;
        linkMap[1] = link1;
        linkMap[2] = link2;
        linkMap[3] = link3;
        linkMap[4] = link4;

        return linkMap;
    }

深度优先搜索算法

以下列有向图为例，遍历后顺序为0 -> 4 -> 3 -> 2 -> 1

? ? ? ? ?DFS算法思想：新建visited[]数组存储第i个节点是否被访问过（由于图存在环的情况，从某一个节点访问回到出发节点）DFS使用递归算法，从某一节点开始一直访问到没有后续节点为止。? ? ? ??

邻接表实现DFS算法?

??????    public void search1(Link[] map){
        int[] visited = new int[map.length];
        for(int i = 0; i<map.length; i++){
            if(visited[i] == 0){
                System.out.print("Start to search: "+map[i].value);
                dfs_search1(map[i], visited);
                System.out.println(" ");
            }
        }
    }

    public void dfs_search1(Link root, int[] visited){
        // 基于临界表深度搜索图
        visited[root.value] =1 ;
        for(Link node : root.neighbors){
            if(visited[node.value] == 0){
                System.out.print(" ->" + node.value);
                dfs_search1(node, visited);
            }
        }
    }

邻接矩阵实现DFS算法

    public void dfs_search2(int[][] map, int[] visited, int j){
        // 基于临界矩阵深度搜索图
        visited[j] =1 ;

        for(int x = 0; x < map.length; x++){
            if(map[x][j] != 0 && visited[x] == 0){
                System.out.print(" ->" + x);
                dfs_search2(map, visited, x);
            }
        }
    }

广度优先搜索算法

广度优先搜索算法BFS：同样使用visited[]数组存储节点是否被访问过，并使用队列存储待访问的节点。

邻接表实现广度优先搜索算法?

    public void bfs_search1(Link root, int[] visited){
        Queue<Link> queue = new ArrayDeque<>();
        queue.add(root);
        while(queue.size() != 0){
            Link node = queue.poll();
            if(visited[node.value] == 0){
                // 未被访问过
                System.out.print("->"+node.value);
                for(Link link : node.neighbors){
                    queue.add(link);
                }
                visited[node.value] =1;
            }
        }
    }