图论题目。

检测环(dfs+bfs)

课程表

题目
dfs:

class Solution {
    //dfs来
    //先创建有向图
    //在判断图有没有成环
    boolean isCircle=false;
    boolean[] onPath;//记录一次经过的节点
    boolean[] visit;//记录全过程访问过的节点 
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //建图--> 邻接表表示
        List<Integer>[] graph=new LinkedList[numCourses];
        //初始化graph
        for(int i=0;i<numCourses;i++){
            graph[i]=new LinkedList();
        }
        //创建onPath,visit
        onPath=new boolean[numCourses];
        visit=new boolean[numCourses];
        //graph的索引就是from
        for(int[] arr:prerequisites){
            int from=arr[1];
            int to=arr[0];
            graph[from].add(to);
        }
        //遍历图,由于图具有不连通性,每个节点都需要作为起点
        for(int i=0;i<numCourses;i++){
            trverse(graph,i);
        }
        return !isCircle;
    }
    //从start节点开始遍历
    void trverse(List<Integer>[] graph,int start){
        if(isCircle){
            //已经成环了
            return;
        }
        //在onPath路上重复出现start,说明成环了
        if(onPath[start]==true){
            isCircle=true;
            return;
        }
        //start节点曾经访问过,不需要重复访问
        if(visit[start]==true){
            return;
        }
        onPath[start]=true;
        visit[start]=true;
        for(int neibor:graph[start]){
            trverse(graph,neibor);
        }
        onPath[start]=false;
    }
}

bfs:

class Solution {
    //用bfs
    //思路：入度为0就进队列，同时把相邻的节点入度减1，
    //入队列就说明入度为0可以学，同样出队列的次数就是可以学习的个数
    //用到的：队列，存入度使得数组，图
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //创建图,和上面一样
        List<Integer>[]graph=new LinkedList[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i]=new LinkedList();
        }
        int[]indegree=new int[numCourses];//索引就是节点，数值就是入度数量
        for(int[] arr:prerequisites){
            int from=arr[1];
            int to=arr[0];
            indegree[to]++;
            graph[from].add(to);
        }
        //创建队列
        Queue<Integer> queue=new LinkedList();
        //把入度为0的节点入队列
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0){
                queue.add(i);
            }
        }
        int count=0;//统计入队列(可以学习)的个数
        //进队列就说明入度为1,可以学习
        while(!queue.isEmpty()){
            int node=queue.poll();
            count++;
            for(int neibor:graph[node]){
                indegree[neibor]--;
                if(indegree[neibor]==0){
                    queue.add(neibor);
                }
            }
        }
        if(count==numCourses){
            return true;
        }
        return false;
    }
}

拓扑排序（dfs+bfs）

课程表2

我的错误代码：
原因：我的res写在了前序遍历的位置，应该写在后序遍历的位置。

class Solution {
    //dfs
    ArrayList<Integer> res=new ArrayList();
    boolean[]visit;
    boolean[] onPath;
    boolean isCircle=false;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //创建图
        List<Integer>[] graph=new LinkedList[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i]=new LinkedList();
        }
        for(int[]arr:prerequisites){
            int from=arr[1];
            int to=arr[0];
            graph[from].add(to);
        }
        visit=new boolean[numCourses];
        onPath=new boolean[numCourses];
        for(int i=0;i<numCourses;i++){
            traverse(graph,i);
        }
        if(isCircle){
            return new int[]{};
        }
        int[]arr=new int[numCourses];
        for(int i=0;i<numCourses;i++){
            arr[i]=res.get(i);
        }
        return arr;
    }
    //以start为起点
    void traverse(List<Integer>[] graph ,int start){
        //已经有环了，直接返回
        if(isCircle){
            return;
        }
        //找到了环
        if(onPath[start]==true){
            isCircle=true;
            return;
        }
        //start曾经访问过,防止重复
        if(visit[start]==true){
            return;
        }
        onPath[start]=true;
        visit[start]=true;
        res.add(start);
        for(int neibor:graph[start]){
            traverse(graph,neibor);
        }
        onPath[start]=false;
    }
}

修正：这题用到拓扑排序，拓扑排序是对有向无环图（DAG）的顶点进行线性排序的一种算法，其实特别简单，把图结构后序遍历的结果进行反转，就是拓扑排序的结果。后序遍历的这一特点很重要，之所以拓扑排序的基础是后序遍历，是因为一个任务必须等到它依赖的所有任务都完成之后才能开始开始执行。
DFS:

class Solution {
    //dfs
    ArrayList<Integer> res=new ArrayList();
    boolean[]visit;
    boolean[] onPath;
    boolean isCircle=false;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //创建图
        List<Integer>[] graph=new LinkedList[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i]=new LinkedList();
        }
        for(int[]arr:prerequisites){
            int from=arr[1];
            int to=arr[0];
            graph[from].add(to);
        }
        visit=new boolean[numCourses];
        onPath=new boolean[numCourses];
        for(int i=0;i<numCourses;i++){
            traverse(graph,i);
        }
        if(isCircle){
            return new int[]{};
        }
        int[]arr=new int[numCourses];
        Collections.reverse(res);
        for(int i=0;i<numCourses;i++){
            arr[i]=res.get(i);
        }
        return arr;
    }
    //以start为起点
    void traverse(List<Integer>[] graph ,int start){
        //已经有环了，直接返回
        if(isCircle){
            return;
        }
        //找到了环
        if(onPath[start]==true){
            isCircle=true;
            return;
        }
        //start曾经访问过,防止重复
        if(visit[start]==true){
            return;
        }
        onPath[start]=true;
        visit[start]=true;
        
        for(int neibor:graph[start]){
            traverse(graph,neibor);
        }
        res.add(start);
        onPath[start]=false;
    }
}

BFS:

class Solution {
    //bfs:出队列的顺序就是拓扑排序
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //创建图,和上面一样
        List<Integer>[]graph=new LinkedList[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i]=new LinkedList();
        }
        int[]indegree=new int[numCourses];//索引就是节点，数值就是入度数量
        for(int[] arr:prerequisites){
            int from=arr[1];
            int to=arr[0];
            indegree[to]++;
            graph[from].add(to);
        }
        //创建res数组
        int[]res=new int[numCourses];
        //创建队列
        Queue<Integer> queue=new LinkedList();
        //把入度为0的节点入队列
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0){
                queue.add(i);
            }
        }
        int count=0;//统计入队列(可以学习)的个数
        int k=0;
        //进队列就说明入度为1,可以学习
        while(!queue.isEmpty()){
            int node=queue.poll();  
            count++;
            res[k++]=node;        
            for(int neibor:graph[node]){
                indegree[neibor]--;
                if(indegree[neibor]==0){
                    queue.add(neibor);
                }
            }
        }
        if(count==numCourses){
            return res;
        }
        return new int[]{};
    }
    
}

二分图（dfs,bfs）

判断二分图

class Solution {
    boolean ok=true;//是二分图
    //用dfs
    boolean[] visit;
    boolean[] color; 
    public boolean isBipartite(int[][] graph) {
        int sz=graph.length;
        color=new boolean[sz];
        visit=new boolean[sz];
        //遍历图
        for(int i=0;i<sz;i++){
            traverse(graph,i);
        }
        return ok;
    }
    //从start节点开始遍历图
    void traverse(int[][]graph,int start){
        //已经不是二分图了
        if(!ok){
            return;
        }
        int sz=graph.length;
        //start节点访问过了
        if(visit[start]){
            return;
        }
        visit[start]=true;
        for(int neibor:graph[start]){
            if(!visit[neibor]){
                //start的相邻节点没有访问
                //给相邻节点染色
                color[neibor]=!color[start];
                traverse(graph,neibor);
            }else{
                if(color[start]==color[neibor]){
                    ok=false;
                    return;
                }
            }
        }
    }
}

class Solution {
    //用bfs
    boolean[]color;
    boolean[]visit;
    boolean ok=true;
    public boolean isBipartite(int[][] graph) {
        int sz=graph.length;
        color=new boolean[sz];
        visit=new boolean[sz];
        Queue<Integer> queue=new LinkedList();
        //图具有不连通性
        for(int i=0;i<sz;i++){     
            if(visit[i]==true){
                continue;
            }
            queue.add(i);
            visit[i]=true;
            while(!queue.isEmpty()){
                int cur=queue.poll();
                //把cur的邻居节点染色，入队列
                for(int neibor:graph[cur]){
                    if(!visit[neibor]){
                        color[neibor]=!color[cur];
                        visit[neibor]=true;
                        queue.add(neibor);
                    }else{
                        if(color[neibor]==color[cur]){
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }
}

可能的二分法

题目
DFS:

class Solution {
    //dislike相当于给了你边的关系
    //1.创建图 无向图
    //2.判断这个图是不是二分图
    //dfs
    boolean[]color;
    boolean[]visit;
    boolean ok=true;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer>[]graph=buildGraph(n,dislikes);
        color=new boolean[n+1];
        visit=new boolean[n+1];
        for(int i=1;i<=n;i++){
            traverse(graph,i);
        }
        return ok;
    }
    //以start为起点，开始遍历
    void traverse( List<Integer>[] graph,int start){
        //不是二分图
        if(!ok){
            return;
        }
        //start已经访问了
        if(visit[start]){
            return;
        }
        visit[start]=true;
        for(int neibor:graph[start]){
            if(!visit[neibor]){
                color[neibor]=!color[start];
                traverse(graph,neibor);
            }else{
                if(color[start]==color[neibor]){
                    ok=false;
                    return;
                }
            }
        }
    }
    List<Integer>[] buildGraph(int n,int[][]dislikes){
        List<Integer>[] graph=new LinkedList[n+1];
        for(int i=0;i<=n;i++){
            graph[i]=new LinkedList();
        }
        for(int[] relation:dislikes){
            int a=relation[0];
            int b=relation[1];
            graph[a].add(b);
            graph[b].add(a);
        }
        return graph;
    }
}

BFS:

class Solution {
    //dislike相当于给了你边的关系
    //1.创建图 无向图
    //2.判断这个图是不是二分图
    //bfs
    boolean[]color;
    boolean[]visit;
    boolean ok=true;
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<Integer>[]graph=buildGraph(n,dislikes);
        color=new boolean[n+1];
        visit=new boolean[n+1];
        for(int i=1;i<=n;i++){
            bfs(graph,i);
        }
        return ok;
    }
    //以start为起点，开始bfs
    void bfs( List<Integer>[] graph,int start){
        //不是二分图
        if(!ok){
            return;
        }
        //start已经访问了
        if(visit[start]){
            return;
        }
        visit[start]=true;
        Queue<Integer> queue=new LinkedList();
        queue.add(start);
       while(!queue.isEmpty()){
        int cur=queue.poll();
        for(int neibor:graph[cur]){
            if(!visit[neibor]){
                color[neibor]=!color[cur];
                visit[neibor]=true;
                queue.add(neibor);
            }else{
                if(color[cur]==color[neibor]){
                    ok=false;
                    return;
                }
            }
        }
       }
    }
    List<Integer>[] buildGraph(int n,int[][]dislikes){
        List<Integer>[] graph=new LinkedList[n+1];
        for(int i=0;i<=n;i++){
            graph[i]=new LinkedList();
        }
        for(int[] relation:dislikes){
            int a=relation[0];
            int b=relation[1];
            graph[a].add(b);
            graph[b].add(a);
        }
        return graph;
    }
}

Kruskal算法和Prim算法

Kruskal: 将所有边按照权重从小到大排序，从权重最小的边开始遍历，如果这条边和 mst 中的其它边不会形成环，则这条边是最小生成树的一部分，将它加入 mst 集合；否则，这条边不是最小生成树的一部分，不要把它加入 mst 集合。

Prim: Prim 算法的逻辑就是这样，每次切分都能找到最小生成树的一条边，然后又可以进行新一轮切分，直到找到最小生成树的所有边为止。

连接所有点的最小费用

题目

class Solution {
    //用kruscal算法 时间复杂度是:O(M*logM) M为边的数量 这里变得数量是n(n-1)/2,n是点的数量
    public int minCostConnectPoints(int[][] points) {
        List<int[]> graph=new LinkedList();
        int sz=points.length;
        for(int i=0;i<sz;i++){
            for(int j=i+1;j<sz;j++){
                int x0=points[i][0];
                int y0=points[i][1];
                int x1=points[j][0];
                int y1=points[j][1];
                int weight=Math.abs(x0-x1)+Math.abs(y1-y0);
                graph.add(new int[]{i,j,weight});
            }
        }
       //排序 权重从小到大
       Collections.sort(graph,new Comparator<int[]>() {
    	   @Override
    	public int compare(int[] o1, int[] o2) {
    		// TODO Auto-generated method stub
    		return o1[2]-o2[2];
    	}
	    });
        //
        UF uf=new UF(sz);
        int total=0;
        for(int[]arr:graph){
            int city1=arr[0];
            int city2=arr[1];
            int distance=arr[2];
            if(uf.isConnected(city1,city2)){
                continue;
            }
            uf.union(city1,city2);
            total+=distance;
        }

        return total;
    }
    class UF{
        int count;//连通数量
        int[]parent;//父节点
        UF(int n){
            parent=new int[n];
            for(int i=0;i<n;i++){
                parent[i]=i;//自环
            }
            count=n;
        }
        boolean isConnected(int a,int b){
            //找到a的父节点
            int parentA=find(a);
            int parentB=find(b);
            if(parentA==parentB){
                return true;
            }
            return false;
        }
        //找到x的父节点
        int find(int x){
            if(parent[x]!=x){
                parent[x]=find(parent[x]);
            }
            return parent[x];
        }
        void union(int a,int b){
            int rootA=find(a);
            int rootB=find(b);
            if(rootA==rootB){
                return;
            }

            parent[rootA]=rootB;
            count--;
        }
        int count(){
            return count;
        }
    }
}

class Solution {
    //用prim算法
    boolean[] isMST;//记录那些节点是最小生成树的一部分
    PriorityQueue<int[]> pq;//存储横切边[from,to,weiht]
    int weightSum=0;//记录最小生成树的权重和
    List<int[]>[] graph;//记录三元组{from,to,weight}表示一条边 下标就是from
    public int minCostConnectPoints(int[][] points) {
        int sz=points.length;
        isMST=new boolean[sz];
        //按照权重从小到大的顺序
        pq=new PriorityQueue<int[]>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[2]-o2[2];
            }
        });
        graph=buildGraph(points);
        cut(0);//先从第一个城市开始切
        isMST[0]=true;
        while(!pq.isEmpty()){
            int[]cur=pq.poll();
            if(!isMST[cur[1]]){
                isMST[cur[1]]=true;
                weightSum+=cur[2];
                cut(cur[1]);
            }
        }
        return weightSum;
    }
    //围绕x节点切一刀
    void cut(int x){
        //遍历x的邻居节点，
        for(int[]neibor:graph[x]){
            //邻居节点已经是生成树的一部分，不用重复入队列
            if(isMST[neibor[1]]){
                continue;
            }
            pq.add(neibor);
        }
    }
    List<int[]>[] buildGraph(int[][]points){
        int sz=points.length;//城市的数量
        List<int[]>[] graph=new ArrayList[sz];
        for(int i=0;i<sz;i++){
            graph[i]=new ArrayList();
        }
        for(int i=0;i<sz;i++){
            for(int j=0;j<sz;j++){
                int x0=points[i][0];
                int y0=points[i][1];
                int x1=points[j][0];
                int y1=points[j][1];
                int weight=Math.abs(x0-x1)+Math.abs(y0-y1);
                graph[i].add(new int[]{i,j,weight});
            }
        }
        return graph;
    }
}

Dijkstra算法

概率最大的路径

题目

class Solution {
    public double maxProbability(int n, int[][] edges, double[] succProb, int start_node, int end_node) {
        //创建图
        List<double[]>[]graph=buildGarph(n,edges,succProb);//三元组{from,to,weight}
        //创建优先级队列 {当前节点，到起点的权重} 降序
        PriorityQueue<double[]> pq=new PriorityQueue<double[]>(new Comparator<double[]>() {
            @Override
            public int compare(double[] o1, double[] o2) {
                // TODO Auto-generated method stub
                return Double.compare(o2[1],o1[1]);
            }
        });
        //创建备忘录,记录到期点的可能性
        double[]memo=new double[n];
        //起点先入队列
        pq.add(new double[]{start_node,1});
        memo[start_node]=1;
        while(!pq.isEmpty()){
            //取出节点
            double[] curArr=pq.poll();
            int curVal=(int)curArr[0];
            double curProb=curArr[1];
            //已经找到了更大的可能性（权重）
            if(curVal==end_node){
                return curProb;
            }
            if(curProb<memo[curVal]){
                continue;
            }
            //去当前节点的周边看看
            for(double[]neibor:graph[curVal]){
                //如果找到了更大可能性，就更新memo，并进队列
                if(neibor[2]*curProb>memo[(int)neibor[1]]){
                    memo[(int)neibor[1]]=neibor[2]*curProb;
                    pq.add(new double[]{neibor[1],memo[(int)neibor[1]]});
                }
            }
        }
        return memo[end_node];
    }
    List<double[]>[] buildGarph(int n,int[][]edges,double[]succProb){
        List<double[]>[] graph=new ArrayList[n];
        for(int i=0;i<n;i++){
            graph[i]=new ArrayList();
        }
        for(int i=0;i<edges.length;i++){
            int node1=edges[i][0];
            int node2=edges[i][1];
            double weight=succProb[i];
            graph[node1].add(new double[]{node1,node2,weight});
            graph[node2].add(new double[]{node2,node1,weight});
        }
        return graph;
    }
}

网络延时时间

题目

class Solution {
    //以k为起点
    public int networkDelayTime(int[][] times, int n, int k) {
    	//{from,to,weight}
    	ArrayList<int[]>[] graph=new ArrayList[n+1];
        for(int i=0;i<=n;i++){
            graph[i]=new ArrayList();
        }
    	//建图
    	for(int[] e:times) {
    		int from=e[0];
    		int to=e[1];
    		int weight=e[2];
    		graph[from].add(new int[] {from,to,weight});
    	
    	}
    	
        int[]memo=new int[n+1];//memo[i]:i距离起点的长度
        Arrays.fill(memo, Integer.MAX_VALUE);
        memo[k]=0;
        //pq存的是{当前节点，距离起点的长度}
        PriorityQueue<int[]>pq=new PriorityQueue<int[]>(new Comparator<int[]>() {
        	@Override
        	public int compare(int[] o1, int[] o2) {
        		// TODO Auto-generated method stub
        		return o1[1]-o2[1];
        	}
		});
        pq.add(new int[] {k,0});
        memo[k]=0;
        while(!pq.isEmpty()) {
        	int[]cur=pq.poll();
        	int curVal=cur[0];
        	int curDis=cur[1];
        	//如果当前的节点距离起点的距离较大，就不在继续往下
        	if(curDis>memo[curVal]) {
        		continue;
        	}
        	
        	for(int[]neibor:graph[curVal]) {
        		int neiborVal=neibor[1];
        		int neiborDis=curDis+neibor[2];
        		//当前的权重更小就更新
        		if(neiborDis<memo[neiborVal]) {
        			//更新memo
        			memo[neiborVal]=neiborDis;
        			//把小化的数据入队列
        			pq.add(new int[] {neiborVal,neiborDis});
        		}
        	}
        }
        //在memo中找最大值返回
        int res=memo[1];
        for(int i=2;i<=n;i++) {
        	res=Math.max(res, memo[i]);
        }
        
        return (res==Integer.MAX_VALUE)?-1:res;
    }
}