import java.util.*
public class GectorGraph {
private Point root
private List<List<String>> circlePath
public GectorGraph(String pointName) {
root=new Point(pointName)
}
public GectorGraph(Point point) {
root=point
}
public boolean hasCirclePath(){
findCirclePath()
return circlePath.size()>0
}
public void findCirclePath(){
List<Point> CirclePoints=findCirclePoint()
if(circlePath==null){circlePath=new ArrayList<List<String>>()}
for(Point tempPoint:CirclePoints){
List<String> pointPath=new ArrayList<String>()
findPointPath(tempPoint,root,pointPath)
pointPath.add(root.pointName)
circlePath.add(pointPath)
}
}
public boolean findPointPath(Point target,Point currentPoint,List<String> pointPath){
if(currentPoint.equals(target)){return true}
if(!currentPoint.hasNext()){return false}
List<Point> pointList= currentPoint.getNextPointList()
for(Point tempPoint:pointList){
if(tempPoint.equals(root)){continue}
if(findPointPath(target,tempPoint,pointPath)){
pointPath.add(tempPoint.pointName)
return true
}
}
return false
}
private List<Point> findCirclePoint(){
if(!root.hasNext()){return null}
List<Point> circlePoints=new ArrayList<Point>()
findCirclePoint(root,root,circlePoints)
return circlePoints
}
private void findCirclePoint(Point root,Point currentPoint,List<Point> circlePoints){
if(!currentPoint.hasNext()){return}
List<Point> pointList= currentPoint.getNextPointList()
for(Point tempPoint:pointList){
if(tempPoint.equals(root)){circlePoints.add(currentPoint)}
else{findCirclePoint(root,tempPoint,circlePoints)}
}
}
public void showPath(){
if(circlePath==null){System.out.println("Error")}
for(List<String> tempList:circlePath){
StringBuffer pathString=new StringBuffer()
int tempListIndex=tempList.size()-1
for(tempListIndex>-1tempListIndex--){
pathString.append(tempList.get(tempListIndex))
if(tempListIndex!=0){pathString.append("->")}
}
System.out.println(pathString.toString())
}
}
public static void main(String[] args) {
Point root=new Point("root")
List<Point> p3=new ArrayList<Point>()
for(int i=0i<3i++){
p3.add(new Point("3/1/"+i))
}
List<Point> p4=new ArrayList<Point>()
for(int i=0i<3i++){
p4.add(new Point("3/2/"+i))
}
List<Point> p2=new ArrayList<Point>()
for(int i=0i<2i++){
p2.add(new Point("2/"+i))
}
p3.add(0,root)
p3.get(2).addNextPoint(root)
p4.get(0).addNextPoint(root)
p2.get(0).addNextPointList(p3)
p2.get(1).addNextPointList(p4)
root.addNextPointList(p2)
GectorGraph gg=new GectorGraph(root)
if(gg.hasCirclePath()){
gg.showPath()
}
}
}
class Point{
public String pointName
private List<Point> nextPointList
public Point(String pointName) {
this.pointName=pointName
}
public void addNextPoint(Point p){
if(nextPointList==null){nextPointList=new ArrayList<Point>()}
nextPointList.add(p)
}
public void addNextPointList(List<Point> pList){
if(nextPointList==null){nextPointList=new ArrayList<Point>()}
nextPointList.addAll(pList)
}
public boolean hasNext(){
return nextPointList!=null&&!nextPointList.isEmpty()
}
public List<Point> getNextPointList() {
return nextPointList
}
public void setNextPointList(List<Point> nextPointList) {
this.nextPointList = nextPointList
}
}
1、Java的内存管理就是对象的分配和释放问题。
在Java中，程序员需要通过关键字new为每个对象申请内存空间 (基本类型除外)，所有的对象都在堆 (Heap)中分配空间。
对象的释放是由GC决定和执行的。
在Java中，内存的分配是由程序完成的，而内存的释放是有GC完成的，这种收支两条线的方法简化了程序员的工作。但也加重了JVM的工作。这也是Java程序运行速度较慢的原因之一。 GC释放空间方法：
监控每一个对象的运行状态，包括对象的申请、引用、被引用、赋值等。当该对象不再被引用时，释放对象。
2、内存管理结构
Java使用有向图的方式进行内存管理，对于程序的每一个时刻，我们都有一个有向图表示JVM的内存分配情况。 将对象考虑为有向图的顶点，将引用关系考虑为图的有向边，有向边从引用者指向被引对象。另外，每个线程对象可以作为一个图的起始顶点，例如大多程序从main进程开始执行，那么该图就是以main进程顶点开始的一棵根树。在这个有向图中，根顶点可达的对象都是有效对象，GC将不回收这些对象。如果某个对象 (连通子图)与这个根顶点不可达(注意，该图为有向图)，那么我们认为这个(这些)对象不再被引用，可以被GC回收。 3、使用有向图方式管理内存的优缺点
Java使用有向图的方式进行内存管理，可以消除引用循环的问题，例如有三个对象，相互引用，只要它们和根进程不可达的，那么GC也是可以回收它们的。
Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式
用OPEN,CLOSE表的方式，其采用的是贪心法的算法策略，大概过程如下：
1.声明两个集合，open和close，open用于存储未遍历的节点，close用来存储已遍历的节点
2.初始阶段，将初始节点放入close，其他所有节点放入open
3.以初始节点为中心向外一层层遍历，获取离指定节点最近的子节点放入close并从新计算路径，直至close包含所有子节点
代码实例如下：
Node对象用于封装节点信息，包括名字和子节点
[java] view plain copy
public class Node {
private String name
private Map<Node,Integer>child=new HashMap<Node,Integer>()
public Node(String name){
this.name=name
}
public String getName() {
return name
}
public void setName(String name) {
this.name = name
}
public Map<Node, Integer>getChild() {
return child
}
public void setChild(Map<Node, Integer>child) {
this.child = child
}
}
MapBuilder用于初始化数据源，返回图的起始节点
[java] view plain copy
public class MapBuilder {
public Node build(Set<Node>open, Set<Node>close){
Node nodeA=new Node("A")
Node nodeB=new Node("B")
Node nodeC=new Node("C")
Node nodeD=new Node("D")
Node nodeE=new Node("E")
Node nodeF=new Node("F")
Node nodeG=new Node("G")
Node nodeH=new Node("H")
nodeA.getChild().put(nodeB, 1)
nodeA.getChild().put(nodeC, 1)
nodeA.getChild().put(nodeD, 4)
nodeA.getChild().put(nodeG, 5)
nodeA.getChild().put(nodeF, 2)
nodeB.getChild().put(nodeA, 1)
nodeB.getChild().put(nodeF, 2)
nodeB.getChild().put(nodeH, 4)
nodeC.getChild().put(nodeA, 1)
nodeC.getChild().put(nodeG, 3)
nodeD.getChild().put(nodeA, 4)
nodeD.getChild().put(nodeE, 1)
nodeE.getChild().put(nodeD, 1)
nodeE.getChild().put(nodeF, 1)
nodeF.getChild().put(nodeE, 1)
nodeF.getChild().put(nodeB, 2)
nodeF.getChild().put(nodeA, 2)
nodeG.getChild().put(nodeC, 3)
nodeG.getChild().put(nodeA, 5)
nodeG.getChild().put(nodeH, 1)
nodeH.getChild().put(nodeB, 4)
nodeH.getChild().put(nodeG, 1)
open.add(nodeB)
open.add(nodeC)
open.add(nodeD)
open.add(nodeE)
open.add(nodeF)
open.add(nodeG)
open.add(nodeH)
close.add(nodeA)
return nodeA
}
}
图的结构如下图所示：
Dijkstra对象用于计算起始节点到所有其他节点的最短路径
[java] view plain copy
public class Dijkstra {
Set<Node>open=new HashSet<Node>()
Set<Node>close=new HashSet<Node>()
Map<String,Integer>path=new HashMap<String,Integer>()//封装路径距离
Map<String,String>pathInfo=new HashMap<String,String>()//封装路径信息
public Node init(){
//初始路径,因没有A->E这条路径,所以path(E)设置为Integer.MAX_VALUE
path.put("B", 1)
pathInfo.put("B", "A->B")
path.put("C", 1)
pathInfo.put("C", "A->C")
path.put("D", 4)
pathInfo.put("D", "A->D")
path.put("E", Integer.MAX_VALUE)
pathInfo.put("E", "A")
path.put("F", 2)
pathInfo.put("F", "A->F")
path.put("G", 5)
pathInfo.put("G", "A->G")
path.put("H", Integer.MAX_VALUE)
pathInfo.put("H", "A")
//将初始节点放入close,其他节点放入open
Node start=new MapBuilder().build(open,close)
return start
}
public void computePath(Node start){
Node nearest=getShortestPath(start)//取距离start节点最近的子节点,放入close
if(nearest==null){
return
}
close.add(nearest)
open.remove(nearest)
Map<Node,Integer>childs=nearest.getChild()
for(Node child:childs.keySet()){
if(open.contains(child)){//如果子节点在open中
Integer newCompute=path.get(nearest.getName())+childs.get(child)
if(path.get(child.getName())>newCompute){//之前设置的距离大于新计算出来的距离
path.put(child.getName(), newCompute)
pathInfo.put(child.getName(), pathInfo.get(nearest.getName())+"->"+child.getName())
}
}
}
computePath(start)//重复执行自己,确保所有子节点被遍历
computePath(nearest)//向外一层层递归,直至所有顶点被遍历
}
public void printPathInfo(){
Set<Map.Entry<String, String>>pathInfos=pathInfo.entrySet()
for(Map.Entry<String, String>pathInfo:pathInfos){
System.out.println(pathInfo.getKey()+":"+pathInfo.getValue())
}
}
/**
* 获取与node最近的子节点
*/
private Node getShortestPath(Node node){
Node res=null
int minDis=Integer.MAX_VALUE
Map<Node,Integer>childs=node.getChild()
for(Node child:childs.keySet()){
if(open.contains(child)){
int distance=childs.get(child)
if(distance<minDis){
minDis=distance
res=child
}
}
}
return res
}
}
Main用于测试Dijkstra对象
[java] view plain copy
public class Main {
public static void main(String[] args) {
Dijkstra test=new Dijkstra()
Node start=test.init()
test.computePath(start)
test.printPathInfo()
}
}
