package com.tech.cglibx; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.Map; import java.util.Set; public class MyGraph { public static void main(String[] args) { Graph graph = new Graph(); Set<Vertex> vertexSet = graph.getVertexSet(); Map<Vertex, Vertex[]> edgeMap = graph.getAdjacencys(); Vertex twoVertex = new Vertex("2"); Vertex threeVertex = new Vertex("3"); Vertex fiveVertex = new Vertex("5"); Vertex sevenVertex = new Vertex("7"); Vertex eightVertex = new Vertex("8"); Vertex nineVertex = new Vertex("9"); Vertex tenVertex = new Vertex("10"); Vertex elevenVertex = new Vertex("11"); vertexSet.add(twoVertex); vertexSet.add(threeVertex); vertexSet.add(fiveVertex); vertexSet.add(sevenVertex); vertexSet.add(eightVertex); vertexSet.add(nineVertex); vertexSet.add(tenVertex); vertexSet.add(elevenVertex); edgeMap.put(twoVertex, new Vertex[] { elevenVertex }); edgeMap.put(nineVertex, new Vertex[] { elevenVertex, eightVertex }); edgeMap.put(tenVertex, new Vertex[] { elevenVertex, threeVertex }); edgeMap.put(elevenVertex, new Vertex[] { sevenVertex, fiveVertex }); edgeMap.put(eightVertex, new Vertex[] { sevenVertex, threeVertex }); topologicalSort2(graph,twoVertex); //Vertex[] sortedVertexs = topologicalSort(graph); //printVertex(sortedVertexs); } public static void printVertex(Vertex[] Vertexs) { for (Vertex vertex : Vertexs) { System.out.println(vertex.getName() + " discover time:" + vertex.getDiscover() + " finish time:" + vertex.getFinish()); } } static class TimeRecorder { private int time = 0; public int getTime() { return time; } public void setTime(int time) { this.time = time; } } public static Vertex[] topologicalSort(Graph graph) { Set<Vertex> vertexSet = graph.getVertexSet(); if (vertexSet.size() < 2) { return vertexSet.toArray(new Vertex[0]); } LinkedList<Vertex> sortedList = new LinkedList<Vertex>(); TimeRecorder recorder = new TimeRecorder(); for (Vertex vertex : vertexSet) { if (vertex.color == Color.WHITE) { visitVertex(graph, vertex, recorder, sortedList); } } return sortedList.toArray(new Vertex[0]); } public static void topologicalSort2(Graph graph,Vertex vertex) { LinkedList<Vertex> sortedList = new LinkedList<Vertex>(); TimeRecorder recorder = new TimeRecorder(); visitVertex(graph, vertex, recorder, sortedList); System.out.println(sortedList); } /** * 深度优先搜索(Depth First Search) */ public static void visitVertex(Graph graph, Vertex vertex, TimeRecorder recorder, LinkedList<Vertex> sortedList) { recorder.time += 1; vertex.color = Color.GRAY; vertex.discover = recorder.time; Map<Vertex, Vertex[]> edgeMap = graph.getAdjacencys(); Vertex[] adjacencys = edgeMap.get(vertex); if (adjacencys != null && adjacencys.length > 0) { for (Vertex adjacency : adjacencys) { if (adjacency.color == Color.WHITE) { adjacency.parent = vertex; visitVertex(graph, adjacency, recorder, sortedList); } } } recorder.time += 1; vertex.color = Color.BLACK; vertex.finish = recorder.time; sortedList.addLast(vertex); } enum Color { WHITE, GRAY, BLACK } static class Vertex { private String name; private Color color; private Vertex parent; private int discover; private int finish; @Override public String toString() { return String.format("Vertex [name=%s, color=%s, parent=%s]", name, color, parent); } public Vertex(String name) { this.name = name; this.color = Color.WHITE; } public String getName() { return name; } public void setName(String name) { this.name = name; } public Color getColor() { return color; } public void setColor(Color color) { this.color = color; } public Vertex getParent() { return parent; } public void setParent(Vertex parent) { this.parent = parent; } public int getDiscover() { return discover; } public void setDiscover(int discover) { this.discover = discover; } public int getFinish() { return finish; } public void setFinish(int finish) { this.finish = finish; } @Override public int hashCode() { final int prime = 31; int result = 1; result = prime * result + ((name == null) ? 0 : name.hashCode()); return result; } @Override public boolean equals(Object obj) { if (this == obj) return true; if (obj == null) return false; if (getClass() != obj.getClass()) return false; Vertex other = (Vertex) obj; if (name == null) { if (other.name != null) return false; } else if (!name.equals(other.name)) return false; return true; } } static class Graph { private Set<Vertex> vertexSet = new HashSet<Vertex>(); // 相邻的节点 private Map<Vertex, Vertex[]> adjacencys = new HashMap<Vertex, Vertex[]>(); public Set<Vertex> getVertexSet() { return vertexSet; } public void setVertexSet(Set<Vertex> vertexSet) { this.vertexSet = vertexSet; } public Map<Vertex, Vertex[]> getAdjacencys() { return adjacencys; } public void setAdjacencys(Map<Vertex, Vertex[]> adjacencys) { this.adjacencys = adjacencys; } } }
相关推荐
some websites for graph coloring and joe cuberson's graph coloring and graph generator in gnu c++ in unix and a very smart c++ source code for vertex coloring in vc++.
to develop the code for image processing in segmentation using graph cut
Graph-Based Visual Saliency (MATLAB source code)
这个是graphcut程序的流程图,为了便于理解,应该会有帮助的
这是一个用C++写的graph cut代码,对分割图像有很好的效果。希望有帮助
graph cut segmentation method.
characterizing transport in DFNs, by combining graph theoretical and ma- chine learning methods. We consider a graph representation where nodes sig- nify fractures and edges denote their intersections...
Graph Databases is written by Ian Robinson, Jim Webber, and Emil Eifrém, graph experts and enthusiasts at Neo Technology, creators of Neo4j, the world’s leading graph database. Table of Contents 1...
All charts are completly customizable and can be set up quickly either from code or from the unity editor. Graph And Chart can be used with any platform including VR/AR, mobile ,web and desktop. All ...
Every algorithm and example is accompanied with R code. This allows readers to see how the algorithmic techniques correspond to the process of graph data analysis and to use the graph mining ...
这里有比较全的Tutorial Graph Based Image Segmentation,大家喜欢可以来看看
Completely customizable from the editor and does not require even one line of code. Can be used within any platform including VR/AR. Bar Chart , Pie Chart , Torus Chart , Graph Chart , Bubble Chart ...
graph_algo_pesudo_code.txt.bak
g2o实践GraphSLAM_tutorials_code代码编译报错问题修改后编译通过版本
Code2Graph:将源代码转换为图形。 通过对嵌套层次结构,控制和数据流的轻量级静态分析。 对于软件和语言工程中的各种下游任务: 软件架构分析 语义代码差异 语义代码合并 对代码更改的影响分析 不同粒度下的协同...
openopen114-Random_Graph_Component_Matlab_Code
若要创建此对象 请使用这些标识符之一 Application Access.Application CurrentData Access.CodeData CurrentProject Access.CodeProject DefaultWebOptions Access.DefaultWebOptions Microsoft Excel 若要创建下...
vs2015 c++ opencv3.3.1 实现 Interactive graph cuts for optimal boundary & region segmentation of objects in N-D images code
ClassGraph won a Duke's Choice Award (a recognition of the most useful and/or innovative software in the Java ecosystem) at Oracle Code One 2018. Thanks to all the users who have reported bugs, ...