package com.data.struct;
import java.util.Random;
public class Graphic {
private Node[] list;
private NodeArrayQueue queue;
private int time=0;
public Graphic(int v,int e){
list=new Node[v];
for(int i=0;i<v;i++){
Node node=new Node();
node.id=i;
list[i]=node;
}
for(int i=0;i<e;i++){
int v1=new Random().nextInt(v);
int v2=new Random().nextInt(v);
if(v1==v2){
continue;
}
while(true){
Node node=list[v1];
boolean already=false;
while(node.next!=null){
if(node.next.id==v2){
already=true;
break;
}
node=node.next;
}
if(already==true){
break;
}
Node ex=new Node();
ex.id=v2;
node.next=ex;
break;
}
}
queue=new NodeArrayQueue((v*(v-1)/2)+5);
}
public void depthFirstSearch(){
for(int i=0;i<list.length;i++){
if(list[i].color==Node.WHITE){
dfsVisit(list[i]);
}
}
}
private void dfsVisit(Node node){
time++;
node.d=time;
node.color=Node.GRAY;
Node w=list[node.id];
while(w.next!=null){
if(list[w.next.id].color==Node.WHITE){
list[w.next.id].color=Node.GRAY;
list[w.next.id].parent=w;
dfsVisit(list[w.next.id]);
}
w=w.next;
}
node.color=Node.BLACK;
time++;
node.f=time;
}
public void printDepth(Node v){
Node s=list[0];
if(v==s){
System.out.print(s.id+"=>");
}else if(v.parent==null){
System.out.print(v.id+"=>");
}else {
printDepth(v.parent);
System.out.print(v.id+"=>");
}
}
public void print(){
for(int i=0;i<list.length;i++){
Node node=list[i];
System.out.print(node.id+"=>");
while(node.next!=null){
System.out.print(node.next.id+"=>");
node=node.next;
}
System.out.println();
}
}
public void printAllDepth(){
System.out.println("path");
for(int i=0;i<list.length;i++){
printDepth(list[i]);
System.out.println();
}
}
public static class Node{
public static final int WHITE=1;
public static final int BLACK=2;
public static final int GRAY=3;
private int id;
private Node next;
private int color=WHITE;
private int d=Integer.MAX_VALUE;
private Node parent;
private int f;
}
public static void main(String[] args)throws Exception {
Graphic g=new Graphic(5,30);
g.print();
g.depthFirstSearch();
g.printAllDepth();
}
}上面程序有个bug，修改后如下：
package com.data.struct;
import java.util.Random;
public class GraphicDepthFirst {
private Node[] list;
private int time=0;
public GraphicDepthFirst(int v,int e){
list=new Node[v];
for(int i=0;i<v;i++){
Node node=new Node();
node.id=i;
list[i]=node;
}
for(int i=0;i<e;i++){
int v1=new Random().nextInt(v);
int v2=new Random().nextInt(v);
if(v1==v2){
continue;
}
while(true){
Node node=list[v1];
boolean already=false;
while(node.next!=null){
if(node.next.id==v2){
already=true;
break;
}
node=node.next;
}
if(already==true){
break;
}
Node ex=new Node();
ex.id=v2;
node.next=ex;
break;
}
}
}
public void depthFirstSearch(){
for(int i=0;i<list.length;i++){
if(list[i].color==Node.WHITE){
dfsVisit(list[i]);
}
}
}
private void dfsVisit(Node node){
time++;
node.d=time;
node.color=Node.GRAY;
Node w=list[node.id];
Node u=w;
while(w.next!=null){
if(list[w.next.id].color==Node.WHITE){
list[w.next.id].color=Node.GRAY;
list[w.next.id].parent=u;
dfsVisit(list[w.next.id]);
}
w=w.next;
}
node.color=Node.BLACK;
time++;
node.f=time;
}
public void printDepth(Node v){
Node s=list[0];
if(v==s){
System.out.print(s.id+"=>");
}else if(v.parent==null){
System.out.print(v.id+"=>");
}else {
printDepth(v.parent);
System.out.print(v.id+"=>");
}
}
public void print(){
for(int i=0;i<list.length;i++){
Node node=list[i];
System.out.print(node.id+"=>");
while(node.next!=null){
System.out.print(node.next.id+"=>");
node=node.next;
}
System.out.println();
}
}
public void printAllDepth(){
System.out.println("path");
for(int i=0;i<list.length;i++){
printDepth(list[i]);
System.out.println();
}
}
public static class Node{
public static final int WHITE=1;
public static final int BLACK=2;
public static final int GRAY=3;
private int id;
private Node next;
private int color=WHITE;
private int d=Integer.MAX_VALUE;
private Node parent;
private int f;
}
public static void main(String[] args)throws Exception {
GraphicDepthFirst g=new GraphicDepthFirst(5,30);
g.print();
g.depthFirstSearch();
g.printAllDepth();
}
}
