美文网首页
图的深度优先算法和广度优先算法

图的深度优先算法和广度优先算法

作者: 左上偏右 | 来源:发表于2016-12-27 22:57 被阅读55次
Paste_Image.png
Paste_Image.png
package com.dn.graph.matrix;

import java.util.LinkedList;

public class Graph {
    private int vertexSize;//顶点数量
    private int [] vertexs;//顶点数组
    private int[][]  matrix;
    private static final int MAX_WEIGHT = 1000;
    private boolean [] isVisited;
    public Graph(int vertextSize){
        this.vertexSize = vertextSize;
        matrix = new int[vertextSize][vertextSize];
        vertexs = new int[vertextSize];
        for(int i = 0;i<vertextSize;i++){
            vertexs[i] = i;
        }
        isVisited = new boolean[vertextSize];
    }
    
    
    /**
     * 获取某个顶点的出度
     * @return
     */
    public int getOutDegree(int index){
        int degree = 0;
        for(int j = 0;j<matrix[index].length;j++){
            int weight = matrix[index][j];
            if(weight!=0&&weight!=MAX_WEIGHT){
                degree++;
            }
        }
        return degree;
    }
    
    
    
    /**
     * 入度
     * @return
     */
    
    /**
     * 获取某个顶点的第一个邻接点
     * 其实就是遍历当前index行的列数据,从第1列开始当遇到大于0且小于最大权值时,就找到了此顶点的第一个邻接点
     */
    public int getFirstNeighbor(int index){
        for(int j = 0;j<vertexSize;j++){//行数据
            if(matrix[index][j]>0&&matrix[index][j]<MAX_WEIGHT){ //列数据
                return j;
            }
        }
        return -1;
    }
    
    /**
     * 根据前一个邻接点的下标来取得下一个邻接点
     * @param v1表示要找的顶点
     * @param v2 表示该顶点相对于哪个邻接点去获取下一个邻接点
     */
    public int getNextNeighbor(int v,int index){
        for(int j = index+1;j<vertexSize;j++){
            if(matrix[v][j]>0&&matrix[v][j]<MAX_WEIGHT){
                return j;
            }
        }
        return -1;
    }
    
    /**
     * 图的深度优先遍历算法
     */
    private void depthFirstSearch(int i){
        isVisited[i] = true;
        int w = getFirstNeighbor(i);//
        while(w!=-1){
            if(!isVisited[w]){
                //需要遍历该顶点
                System.out.println("访问到了:"+w+"顶点");
                depthFirstSearch(w);//不断深层次迭代,不满足条件时往回退
            }
            //访问未被访问的邻接点
            w = getNextNeighbor(i, w);//第一个相对于w的邻接点
        }
    }
    
    /**
     * 对外公开的深度优先遍历
     */
    
    public void depthFirstSearch(){
        isVisited = new boolean[vertexSize];
        for(int i = 0;i<vertexSize;i++){
            if(!isVisited[i]){
                System.out.println("访问到了:"+i+"顶点");
                depthFirstSearch(i);
            }
        }
        isVisited = new boolean[vertexSize];
    }
    
    public void broadFirstSearch(){
        isVisited = new boolean[vertexSize];
        for(int i =0;i<vertexSize;i++){
            if(!isVisited[i]){
                broadFirstSearch(i);
            }
        }
    }
    
    /**
     * 实现广度优先遍历
     * @param i
     */
    private void broadFirstSearch(int i) {
        int u,w;
        LinkedList<Integer> queue = new LinkedList<Integer>();
        System.out.println("访问到:"+i+"顶点");
        isVisited[i] = true;
        queue.add(i);//第一次把v0加到队列
        while(!queue.isEmpty()){
            u = (Integer)(queue.removeFirst()).intValue();
            w = getFirstNeighbor(u);
            while(w!=-1){ //这个循环将u结点的孩子全部访问完
                if(!isVisited[w]){
                    System.out.println("访问到了:"+w+"顶点");
                    isVisited[w] = true;
                    queue.add(w);
                }
                w = getNextNeighbor(u, w);//获取后续邻接结点
            }
        }
    }

/**
 * prim 普里姆算法
 */
    public void prim(){
        int [] lowcost = new int[vertexSize];//最小代价顶点权值的数组,为0表示已经获取最小权值
        int [] adjvex = new int[vertexSize];//放顶点权值
        int min,minId,sum = 0;
        for(int i = 1;i<vertexSize;i++){
            lowcost[i] = matrix[0][i];
        }
        for(int i = 1;i<vertexSize;i++){
            min = MAX_WEIGHT;
            minId = 0;
            for(int j = 1;j<vertexSize;j++){
                if(lowcost[j]<min&&lowcost[j]>0){
                    min = lowcost[j];
                    minId = j;
                }
            }
            System.out.println("顶点:"+adjvex[minId]+"权值:"+min);
            sum+=min;
            lowcost[minId] = 0;
            for(int j = 1;j<vertexSize;j++){
                if(lowcost[j]!=0&&matrix[minId][j]<lowcost[j]){
                    lowcost[j] = matrix[minId][j];
                    adjvex[j] = minId;
                }
            }
        }
        System.out.println("最小生成树权值和:"+sum);
    }
    
    /**
     * 图的广度优先搜索算法
     */
    
    /**
     * 获取两个顶点之间的权值
     * @return
     */
    public int getWeight(int v1,int v2){
        int weight = matrix[v1][v2];
        return weight == 0?0:(weight == MAX_WEIGHT?-1:weight);
    }
    
    
    public int[] getVertexs() {
        return vertexs;
    }

    public void setVertexs(int[] vertexs) {
        this.vertexs = vertexs;
    }

    public static void main(String [] args){
        Graph graph = new Graph(9);
        
        int [] a1 = new int[]{0,10,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,11,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
        int [] a2 = new int[]{10,0,18,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,16,MAX_WEIGHT,12};
        int [] a3 = new int[]{MAX_WEIGHT,MAX_WEIGHT,0,22,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,8};
        int [] a4 = new int[]{MAX_WEIGHT,MAX_WEIGHT,22,0,20,MAX_WEIGHT,MAX_WEIGHT,16,21};
        int [] a5 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,20,0,26,MAX_WEIGHT,7,MAX_WEIGHT};
        int [] a6 = new int[]{11,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,26,0,17,MAX_WEIGHT,MAX_WEIGHT};
        int [] a7 = new int[]{MAX_WEIGHT,16,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,17,0,19,MAX_WEIGHT};
        int [] a8 = new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,16,7,MAX_WEIGHT,19,0,MAX_WEIGHT};
        int [] a9 = new int[]{MAX_WEIGHT,12,8,21,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,0};
        
        graph.matrix[0] = a1;
        graph.matrix[1] = a2;
        graph.matrix[2] = a3;
        graph.matrix[3] = a4;
        graph.matrix[4] = a5;
        graph.matrix[5] = a6;
        graph.matrix[6] = a7;
        graph.matrix[7] = a8;
        graph.matrix[8] = a9;
        
//      int degree = graph.getOutDegree(4);
//      System.out.println("vo的出度:"+degree);
//      System.out.println("权值:"+graph.getWeight(2,3));
//      graph.depthFirstSearch();
//      graph.broadFirstSearch();
        graph.prim();
    }
}



相关文章

网友评论

      本文标题:图的深度优先算法和广度优先算法

      本文链接:https://www.haomeiwen.com/subject/wcgevttx.html