Java实现图论的基本使用

news/2024/7/15 17:07:22 标签: java, 图论, 算法, 数据结构

我这里主要写代码，定义等参考图论基础和表示 | 菜鸟教程

一、邻接矩阵代码实现
java">public class AdjacencyMatrix {
    private int n;//节点数
    private int m;//边数
    private boolean directed;//是否为有向图
    private int[][] data;//图数据

    // 构造一个没有边的邻接矩阵
    public AdjacencyMatrix(int n, boolean directed) {
        // g初始化为n*n的布尔矩阵, 每一个data[i][j]均为0, 表示没有任何边，权值为0
        // 为非零正整数时表示有边且边的权值为该值
        assert n>=0;
        this.n = n;
        this.directed = directed;
        this.m=0;
        data=new int[n][n];
    }

    //判断v到w是否有边
    private boolean hasEdge(int v,int w){
        assert v>=0 && v<n;
        assert w>=0 && w<n;
        // 为非零正整数时表示有边且边的权值为该值
        return data[v][w]>0;
    }

    //给v到w添加边和权值
    private void addEdge(int v,int w,int weight){
        assert v>=0 && v<n;
        assert w>=0 && w<n;
        if (hasEdge(v,w)){
            return;
        }
        data[v][w]=weight;
        if (v!=w &&!directed){
            data[w][v]=weight;
        };
        m++;
    }
    //遍历邻边，通过一个顶点遍历相关的邻边
    public Vector<Integer> adjacentEdge(int v) {
        assert v >= 0 && v < n;
        Vector<Integer> ae = new Vector<>();
        for (int i=0;i<n;i++) {
            if (data[v][i] > 0) {
                ae.add(i);
            }
        }
        return ae;
    }

    // 返回节点个数
    public int nodeNum(){ return n;}
    // 返回边的个数
    public int edgeNum(){ return m;}
}
二、邻接表代码实现
java">public class AdjacencyList {
    private int n;//节点数
    private int m;//边数
    private boolean directed;//是否为有向图
    //Vector是线程安全的可变数组
    private Vector<Integer>[] data;

    public AdjacencyList(int n, boolean directed) {
        this.n = n;
        this.directed = directed;
        data =  new Vector[n];
        for (int i=0;i<n;i++){
            data[i]=new Vector<Integer>();
        }
    }

    //判断v到w是否有边
    private boolean hasEdge(int v,int w){
        assert v>=0 && v<n;
        assert w>=0 && w<n;
        // 为非零正整数时表示有边且边的权值为该值
        /*for (int i=0;i<data[v].size();i++ ) {
            if (data[v].elementAt(i)==w){
                return true;
            }
        }*/
        if (data[v].contains(w)){
            return true;
        }
        return false;
    }
    //给v到w添加边和权值
    private void addEdge(int v,int w,int weight){
        assert v>=0 && v<n;
        assert w>=0 && w<n;
        if (data[v].contains(w)){
            return;
        }
        data[v].add(w);
        if (v!=w && !directed){
            data[w].add(v);
        }
        m++;
    }
    //遍历邻边，通过一个顶点遍历相关的邻边
    public Vector<Integer> adjacentEdge(int v) {
        assert v>=0 && v<n;
        return data[v];
    }

    // 返回节点个数
    public int nodeNum(){ return n;}
    // 返回边的个数
    public int edgeNum(){ return m;}
}
三、深度优先遍历（搜索）DBF

DFS（Depth-First-Search，深度优先遍历）算法的具体做法是：
从某个点一直往深处走，走到不能往下走之后，就回退到上一步，直到找到解或把所有点走完

java">public class DFS{
    public AdjacencyMatrix matrix;
    private int count;//连通分量数
    private int[] id;//每个节点分量标记id
    private boolean[] visited;//记录节点是否被遍历过

    private int nodeNum;
    //构造函数：算法初始化
    public DFS(AdjacencyMatrix matrix) {
        this.nodeNum=matrix.nodeNum();
        this.matrix = matrix;
        this.count=0;
        this.id=new int[nodeNum];
        this.visited=new boolean[nodeNum];
        for (int i=0;i<nodeNum;i++){
            visited[i]=false;
            id[i]=-1;
        }
        //使用doDFS方法获取连通分量数
        for (int i=0;i< nodeNum;i++){
            if (!visited[i]){
                count++;
                this.doDFS(i);
            }
        }
    }
    private void doDFS(int node){
        visited[node]=true;
        id[node]=count;
        //使用递归遍历节点的边
        for (Integer i: matrix.adjacentEdge(node)){
            if(!visited[i]){
                doDFS(i);
            }
        }
    }

    public int getCount() {
        return count;
    }
    // 查询点v和点w是否联通
    //两个节点拥有相同的 id 值代表属于同一联通分量。
    private boolean isConnected( int v , int w ){
        assert v >= 0 && v < nodeNum;
        assert w >= 0 && w < nodeNum;
        return id[v] == id[w];
    }
}

四、寻路算法
java">public class LookPath {
    AdjacencyMatrix matrix;
    private int nodeNum;
    private int start;//起点
    private boolean[] visited;//记录dfs的过程中节点是否被访问
    private int[] last;// 记录路径, last[i]表示查找的路径上i的上一个节点

    public LookPath(AdjacencyMatrix matrix, int start) {
        this.matrix = matrix;
        this.start = start;
        this.nodeNum= matrix.nodeNum();
        assert start >= 0 && start < nodeNum;
        visited=new boolean[nodeNum];
        last=new int[nodeNum];
        for (int i=0;i<nodeNum;i++){
            visited[i]=false;
            last[i]=-1;
        }
        doDFS(start);
    }
    // 图的深度优先遍历
    private void doDFS(int v){
        assert v >= 0 && v < nodeNum;
        visited[v]=true;
        for (Integer i: matrix.adjacentEdge(v)){
            last[i]=v;
            doDFS(i);
        }
    }

    //判断start节点到end节点是否有路径，只要查询 visited 对应数组值即可。
    private boolean hasPath(int end){
        assert end >= 0 && end < nodeNum;
        return visited[end];
    }
    private Vector<Integer> lookPath(int current){
        assert hasPath(current);
        Stack<Integer> stack=new Stack<>();// 通过from数组查找到从current到start的路径, 存放到栈中
        while (current!=-1){
            stack.push(current);
            current=last[current];
        }
        // 从栈中依次取出元素, 获得顺序的从start到current的路径
        Vector<Integer> ve = new Vector<>();
        while (!stack.empty()){
            ve.addElement(stack.pop());
        }
        return ve;
    }
    // 打印出从s点到w点的路径
    public void showPath(int w){
        assert hasPath(w) ;
        Vector<Integer> vec = lookPath(w);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            System.out.print(vec.elementAt(i));
            if( i == vec.size() - 1 )
                System.out.println();
            else
                System.out.print(" -> ");
        }
    }
}
五、广度优先遍历与最短路径

（Breadth First Search，广度优先搜索，又名宽度优先搜索），与深度优先算法在一个结点“死磕到底“的思维不同，广度优先算法关注的重点在于每一层的结点进行的下一层的访问。类似于二叉树或堆的层序遍历，BFS的核心就是要把当前在哪作为一个状态存储，并将这个状态交给队列进行入队操作

java">public class BFS {
    AdjacencyMatrix matrix;
    private int nodeNum;
    private int start;//起点
    private boolean[] visited;//记录dfs的过程中节点是否被访问
    private int[] last;// 记录路径, last[i]表示查找的路径上i的上一个节点
    private int[] order;// 记录路径中节点的次序。order[i]表示i节点在路径中的次序。

    public BFS(AdjacencyMatrix matrix, int start) {
        this.matrix = matrix;
        this.start = start;
        this.nodeNum = matrix.nodeNum();
        assert start >= 0 && start < nodeNum;
        visited=new boolean[nodeNum];
        last=new int[nodeNum];
        order=new int[nodeNum];
        for (int i=0;i<nodeNum;i++){
            visited[i]=false;
            last[i]=-1;
            order[i]=-1;
        }
        doBFS(start);
    }
    // 图的深度优先遍历
    private void doBFS(int v){
        visited[v]=true;
        order[v]=0;
        LinkedList<Integer> queue=new LinkedList<>();
        //add向链表末尾后添加，push向第一个位置前添加，pop返回并删除第一个,当队列或栈使用时要得当
        queue.addFirst(v);
        while (!queue.isEmpty()){
            Integer rf = queue.removeFirst();
            for (Integer i : matrix.adjacentEdge(rf)) {
                last[i]=rf;
                queue.addLast(i);
                visited[i]=true;
                order[i]=order[rf]+1;
            }
        }
    }

    //判断start节点到end节点是否有路径，只要查询 visited 对应数组值即可。
    private boolean hasPath(int end){
        assert end >= 0 && end < nodeNum;
        return visited[end];
    }
    private Vector<Integer> lookPath(int current){
        assert hasPath(current);
        Stack<Integer> stack=new Stack<>();// 通过from数组查找到从current到start的路径, 存放到栈中
        while (current!=-1){
            stack.push(current);
            current=last[current];
        }
        // 从栈中依次取出元素, 获得顺序的从start到current的路径
        Vector<Integer> ve = new Vector<>();
        while (!stack.empty()){
            ve.addElement(stack.pop());
        }
        return ve;
    }
    // 打印出从s点到w点的路径
    public void showPath(int w){
        assert hasPath(w) ;
        Vector<Integer> vec = lookPath(w);
        for( int i = 0 ; i < vec.size() ; i ++ ){
            System.out.print(vec.elementAt(i));
            if( i == vec.size() - 1 )
                System.out.println();
            else
                System.out.print(" -> ");
        }
    }
    // 查看从s点到w点的最短路径长度
    // 若从s到w不可达，返回-1
    public int length(int w){
        assert w >= 0 && w < nodeNum;
        return order[w];
    }
}


http://www.niftyadmin.cn/n/5401904.html

相关文章

论文阅读之Reasoning Implicit Sentiment with Chain-of-Thought Prompting

论文阅读之Reasoning Implicit Sentiment with Chain-of-Thought Prompting

简介 本文主要对2023ACL论文《Reasoning Implicit Sentiment with Chain-of-Thought Prompting》主要内容进行介绍。 摘要 虽然情绪分析任务中通常根据输入文本中的关键意见表达来确定给定目标的情绪极性&#xff0c;但在隐式情绪分析&#xff08;ISA&#xff09;中&#xf…
阅读更多...
C语言：编译与链接

C语言：编译与链接

C语言&#xff1a;编译 & 链接 环境翻译环境 编译预处理编译汇编 链接 环境 对C语言而言&#xff0c;生成程序的过程中存在两种环境&#xff1a;翻译环境与运行环境。 翻译环境 在翻译环境中&#xff0c;源代码会被转化为可执行的机器指令。这个过程会分为编译与链接两大…
阅读更多...
Kubernetes（k8s第二部分）

Kubernetes（k8s第二部分）

资源清单相当于剧本 什么是资源&#xff1a; k8s中所有的内容都抽象为资源&#xff0c;资源实例化后&#xff0c;叫做对象。 1.K8S中的资源 集群资源分类 名称空间级别&#xff1a; kubeadm k8s kube-system kubectl get pod -n default 工作负载型资源&#xff0c;&a…
阅读更多...
Leetcode刷题（十八）

Leetcode刷题（十八）

一、203. 移除链表元素 代码&#xff1a; class Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:while head and head.val val:head head.nextpre, cur head, headwhile cur:if cur.val val:pre.next cur.nextelse:p…
阅读更多...
java之反射Reflection

java之反射Reflection

反射就是&#xff1a;加载类&#xff0c;并准许以编程的方式&#xff0c;解刨类中的各种成分 (成员变量、方法、构造器等) 步骤 1. 反射第一步&#xff1a;加载类&#xff0c;获取类的字节码&#xff1a;class对象 2. 获取类的构造器&#xff1a;constructor 3. 获取类的成员…
阅读更多...
2024有哪些免费的mac苹果电脑深度清理工具？CleanMyMac X

2024有哪些免费的mac苹果电脑深度清理工具？CleanMyMac X

苹果电脑用户们&#xff0c;你们是否经常感到你们的Mac变得不再像刚拆封时那样迅速、流畅&#xff1f;可能是时候对你的苹果电脑进行一次深度清理了。在这个时刻&#xff0c;拥有一些高效的深度清理工具就显得尤为重要。今天&#xff0c;我将介绍几款优秀的苹果电脑深度清理工具…
阅读更多...
Verilog参数、Verilog参数和属性冲突、整数处理

Verilog参数、Verilog参数和属性冲突、整数处理

Verilog参数 Verilog参数执行以下操作&#xff1a; •允许您创建易于重用和扩展的参数化代码。 •使代码更可读、更紧凑、更易于维护。 •将此类功能描述为&#xff1a; ○ 总线尺寸 ○ 建模设计单元中某些重复元素的数量 •是常数。对于参数化模块的每个实例化&#xf…
阅读更多...
Netty NIO 非阻塞模式2(完善)

Netty NIO 非阻塞模式2(完善)

1.概要 1.1 说明 Netty NIO 非阻塞模式-CSDN博客 真对上面的问题&#xff0c;做些修正。主要解决如下问题。当客户端关闭或者强制关闭的时候&#xff0c;服务端关闭对应的SelectionKey。这样可以避免因异常退出&#xff0c;和不断的重复读取数据。 1.1.1客户端强制退出&…
阅读更多...
最新文章

Copyright @ 2022~2023