「java图论算法」算法 图论

今天给各位分享java图论算法的知识，其中也会对算法 图论进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、一个java算法问题,求高手解决!
• 2、判断有向图是否连通+dfs+java
• 3、在Java中，对象什么时候可以被垃圾回收？
• 4、求图论算法java实现
• 5、java中的算法，一共有多少种，哪几种，怎么分类。

一个java算法问题,求高手解决!

这是一个关于 图 的算法。

告诉你一个不太靠谱的方法，但是是最佳实践的方法：

根据当地的路况和交通规则随时变换派送规则。

比如：

在北京派送的话，要考虑下雨天路段积水问题，要考虑交通管制问题，要考虑上下班高峰期问题，要考虑派送路程上的交通事故问题，要考虑走换线还是走高速的问题，等等。

呵呵，开个玩笑。

你可以找一本 《数据结构》的书，重点看图论那一章，书里有详细讲解图中最短路径的算法。

就能解决你的问题了。

判断有向图是否连通+dfs+java

方法1：

如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度=2。

n算法：

第一步：删除所有度=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。

第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。

如果最后还有未删除顶点，则存在环，否则没有环。

n算法分析：

由于有m条边，n个顶点。

i)如果m=n，则根据图论知识可直接判断存在环路。（证明：如果没有环路，则该图必然是k棵树 k=1。根据树的性质，边的数目m = n-k。k=1，所以：mn）

ii)如果mn 则按照上面的算法每删除一个度为0的顶点操作一次（最多n次），或每删除一个度为1的顶点（同时删一条边）操作一次（最多m次）。这两种操作的总数不会超过m+n。由于mn，所以算法复杂度为O(n)。

在Java中，对象什么时候可以被垃圾回收？

1. 引用计数器算法

解释

系统给每个对象添加一个引用计数器,每当有一个地方引用这个对象的时候,计数器就加1,当引用失效的时候,计数器就减1,在任何一个时刻计数器为0的对象就是不可能被使用的对象,因为没有任何地方持有这个引用,这时这个对象就被视为内存垃圾,等待被虚拟机回收

优点

客观的说,引用计数器算法,他的实现很简单,判定的效率很高,在大部分情况下这都是相当不错的算法

其实,很多案例中都使用了这种算法,比如 IOS 的Object-C , 微软的COM技术(用于给window开发驱动,.net里面的技术几乎都是建立在COM上的),Python语言等.

缺陷

无法解决循环引用的问题.

这就好像是悬崖边的人采集草药的人, 想要活下去就必须要有一根绳子绑在悬崖上. 如果有两个人, 甲的手拉着悬崖, 乙的手拉着甲, 那么这两个人都能活, 但是, 如果甲的手拉着乙, 乙的手也拉着甲, 虽然这两个人都认为自己被别人拉着, 但是一样会掉下悬崖.

比如说 A对象的一个属性引用B,B对象的一个属性同时引用A A.b = B() B.a = A(); 这个A,B对象的计数器都是1,可是,如果没有其他任何地方引用A,B对象的时候,A,B对象其实在系统中是无法发挥任何作用的,既然无法发挥作用,那就应该被视作内存垃圾予以清理掉,可是因为此时A,B的计数器的值都是1,虚拟机就无法回收A,B对象,这样就会造成内存浪费,这在计算机系统中是不可容忍的.

解决办法

在语言层面处理, 例如Object-C 就使用强弱引用类型来解决问题.强引用计数器加1 ,弱引用不增加

Java中也有强弱引用

2. 可达性分析算法

解释

这种算法通过一系列成为 "GC Roots " 的对象作为起始点,从这些节点开始向下搜索所有走过的路径成为引用链(Reference Chain) , 当一个对象GC Roots没有任何引用链相连(用图论的话来说就是从GC Roots到这个对象不可达),则证明此对象是不可用的

优点

这个算法可以轻松的解决循环引用的问题

大部分的主流java虚拟机使用的都是这种算法

3. Java语言中的GC Roots

在虚拟机栈(其实是栈帧中的本地变量表)中引用的对象

在方法区中的类静态属性引用对象

在方法区中的常量引用的对象

在本地方法栈中JNI(即一般说的Native方法)的引用对象

求图论算法java实现

求图论算法java实现

package test;

import java.io.BufferedReader;

import java.io.FileReader;

import java.io.IOException;

import java.util.ArrayList;

import java.util.Comparator;

import java.util.HashMap;

import java.util.Map;

import java.util.PriorityQueue;

import java.util.Queue;

public class MinSpanningTree {

    class Edge {//内部类定义边的数据结果

        int u, v, weight;

    }

    ArrayListedge Edges = new ArrayListedge();

    Mapinteger, integer="" nodeFather = new HashMapinteger, integer=""();

    int cnt = 0, nodeCnt = 0;

    public MinSpanningTree(String path) {

        try {

            BufferedReader br = new BufferedReader(new FileReader(path));

            String str;

            String[] strArray;

            while ((str = br.readLine()) != null) {

                strArray = str.split("\\s");

                Edges.add(cnt, new Edge());

                Edges.get(cnt).u = Integer.parseInt(strArray[0]);

                Edges.get(cnt).v = Integer.parseInt(strArray[1]);

                Edges.get(cnt).weight = Integer.parseInt(strArray[2]);

                if (!nodeFather.containsKey(Edges.get(cnt).u)) {

                    nodeFather.put(Edges.get(cnt).u, Edges.get(cnt).u);//初始化，father[i]=i;

                    ++nodeCnt;

                }

                if (!nodeFather.containsKey(Edges.get(cnt).v)) {

                    nodeFather.put(Edges.get(cnt).v, Edges.get(cnt).v);

                    ++nodeCnt;

                }

                ++cnt;

            }

            br.close();

        } catch (IOException e) {

            e.printStackTrace();

        }

    }

    public boolean union(int u, int v) {//并操作

        int a = find(u);

        int b = find(v);

        if (a != b) {

            nodeFather.put(a, b);

            return true;

        }

        return false;

    }

    public int find(int x) {//查操作

        if (x != nodeFather.get(x)) {

            nodeFather.put(x, find(nodeFather.get(x)));

        }

        return nodeFather.get(x);

    }

    public ArrayListedge getMinSpanningTree() {

        ArrayListedge result = new ArrayListedge();

        Queueedge FsQueue = new PriorityQueueedge(1000,//设置优先队列，使按边权值从小到大排序

                new Comparatoredge() {

                    public int compare(Edge EdgeOne, Edge EdgeTwo) {

                        if (EdgeOne.weight  EdgeTwo.weight)

                            return 1;

                        else if (EdgeOne.weight  EdgeTwo.weight)

                            return -1;

                        else

                            return 0;

                    }

                });

        for (int i = 0; i  cnt; ++i) {

            FsQueue.add(Edges.get(i));

        }

        while (!FsQueue.isEmpty()) {//遍历每一条边

            Edge Edge = FsQueue.poll();

            if (union(Edge.u, Edge.v)) {

                result.add(Edge);

            } else {

                continue;

            }

        }

        return result;

    }

    public static void main(String[] args) {

        MinSpanningTree mstree = new MinSpanningTree("c:/treedata.txt");

        ArrayListedge result = mstree.getMinSpanningTree();

        for (int i = 0; i  result.size(); ++i) {

            System.out.println(result.get(i).u + " " + result.get(i).v + " "+ result.get(i).weight);

        }

    }

}

java中的算法，一共有多少种，哪几种，怎么分类。

就好比问，汉语中常用写作方法有多少种，怎么分类。

算法按用途分,体现设计目的、有什么特点

算法按实现方式分，有递归、迭代、平行、序列、过程、确定、不确定等等

算法按设计范型分，有分治、动态、贪心、线性、图论、简化等等

作为图灵完备的语言，理论上”Java语言“可以实现所有算法。

“Java的标准库'中用了一些常用数据结构和相关算法.

像apache common这样的java库中又提供了一些通用的算法

java图论算法的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于算法 图论、java图论算法的信息别忘了在本站进行查找喔。