欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

#例程学习# | java刷题 | 图_经典结构+图宽度优先遍历+图广/深度优先遍历_1 | 左神第七章_自定义图结构

程序员文章站 2022-03-03 12:31:42
...

背景

刷题+总结+进步!
看B站左神的算法,总结一个自己的关于图的万能结构,之后遇到新的题目,只用写接口即可与自己的万能结构结合起来,加快做题速度

实现

分析

图_经典结构+图宽度优先遍历+图广度优先遍历。

步骤

1、图_经典结构:图、节点、边

1、定义图;
2、定义图节点;
3、定义图中两点连线的边;

2、图宽度优先遍历:队列

1、利用队列实现;
2、从源节点开始依次按照宽度入队,后弹出
3、每弹出一个节点,将该节点的邻接点中未进入队列的点放入队列;
4、直到队列变空。

3、图广度优先遍历:栈

1、利用栈实现;
2、从源节点开始,将节点按照深度放入栈,后弹出;
3、每弹出一个点,将该点的邻接点中 未进入过栈的点 入栈;
4、直到栈变空。

题解

注意代码中类和方法的位置:

  • 以下代码中,需要定义三个类:Graph、Node、Edge、Solution。
  • 前三个类不加public,是简单的结构定义。
  • Solution类中实现主要的功能函数:也可以加入主函数main实现输入输出,在该类的其他方法中直接调用dfs、bfs功能函数或在其他类中通过类名来调用bfs、dfs。

1、图_经典结构

//图结构
class Graph(){
    public HashMap<Integer,Node> nodes;     //城市的编号、对应的具体节点,构成map点集。可以通过点集查某个城市是否出现过
    //如果数据比较大的话,自己可用数组结构替代hash表,城市的数值不会很大,数组的查改速度会更快一点。
    public HashSet<Edge> edges;             //边集是一个hashset保存

    public Graph(int ){
        nodes = new HashMap<>(); 
        edges = new HashMap<>(); 
    }
}

//点结构
class Node{
    public int value;                   //自己的数据项,0 这个城市就是0
    public int in;                      //一个点的入度
    public int out;                     //该点的出度
    public ArrayList<Node> nexts;       //从当前点出发,发散出去的边直接相连的连接点。
    public ArrayList<Node> edges;       //当前点出发,出度的边集

    public Node(int value){
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}


//边结构
class Edge{
    public int weight;      //有向边,可以拼成无向边
    public Node from;
    public Node to;

    public Edge(int weight, Node from, Node to){
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}

2、图宽度优先遍历

public class Solution{
	//从node出发,图宽度优先遍历:队列
    public void bfs(Node node){
        if(node == null)    return null;

        //1.利用队列实现
        Queue<Node> queue = new LinkedList<>();     //用来进行遍历的临时保存
        HashSet<Node> set = new HashSet<>();        //为队列服务,set保证队列中的点集不重复

        queue.add(node);                            //将出发点放到queue、set中
        set.add(node);

        //4.直到队列变空
        while(!queue.isEmpty()){
            
            //2.从源节点开始依次按照宽度进入队列,然后弹出
            Node cur = queue.poll();            
            
            System.out.println(cur.value);          //出节点的时候,进行自己的处理

            //3、每弹出一个点,把该节点没有进过队列的邻接点放入队列
            for(Node next : cur.nexts){
                if(!set.contains(next)){
                    set.add(next);
                    queue.add(next);
                }
            }
        }
    }
}

3、图广度优先遍历

public class Solution{
	//图深度优先遍历:栈
    public void dfs(Node node){
        if(node == null){
            return;
        }

        Stack<Node> stack = new Stack<>();          //临时存放遍历到的节点,最深路径
        HahsSet<Node> set = new HashSet<>();        //存放所有遍历过的节点 
        stack.add(node);
        set.add(node);

        while(!stack.isEmpty()){
            Node cur = stack.pop();
            for(Node next : cur.nexts){             //遍历当前节点的出度对应的节点集合
                if(!set.contains(next)){
                    set.add(cur);
                    stack.push(cur);
                    stack.push(next);
                    System.out.println(next.value);
                    break;                          //跳出当前for,遍历cur的下一个出度的节点
                }
            }
        }                                           //直到遍历完所有的节点,依次出栈即可
    } 
}

4、对于问题编写接口

//接口函数,用户给出一些值,需要将这些值转换为图结构
// matrix 所有的边
// N*3矩阵
// [from节点上的值, to节点上的值, weight]public class Solution{
public class Solution(){

    //创建图,接口函数。不要哪些,不填即可。
    public Graph createGraph(int[][] matrix){
        Graph graph = new Graph();

        //将输入的矩阵转换为自己构建的图结构
        for(int i = 0; i < matrix.length; i++){     //matrix[0][0],matrix[0][1],matrix[0][2]
            Integer from = matrix[i][0];
            Integer to = matrix[i][1];
            Integer weight = matrix[i][2];

            //保证点集里面一定有from 、 to
            if(!graph.nodes.containsKey(from)){             //如果from这个城市没有出现过
                graph.nodes.put(from, new Node(from));
            }
            if(!graph.nodes.containsKey(to)){             //如果to这个城市没有出现过
                graph.nodes.put(to, new Node(to));
            }

            //拿出实际的两个点,构建边,赋予权值
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge newEdge = new Edge(weight, fromNode, toNode);

            fromNode.nexts.add(num);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }
}

总结

搁置了好久的博客开始恢复吧

参考

链接: link.
[1]: http://先保留一个格式