JAva図の遍歴方式(深さ遍歴、広さ遍歴)
2302 ワード
import java.util.*;
/**
*
* ,
* Created on 2013-11-18
* @version 0.1
*/
public class DeptSearch
{
public static void main(String args[]){
//
NodeT a=new NodeT("a");
NodeT b=new NodeT("b");
NodeT c=new NodeT("c");
NodeT d=new NodeT("d");
NodeT e=new NodeT("e");
NodeT f=new NodeT("f");
NodeT g=new NodeT("g");
NodeT h=new NodeT("h");
ArcT ab=new ArcT(a,b);
ArcT ac=new ArcT(a,c);
ArcT ad=new ArcT(a,d);
ArcT ah=new ArcT(a,h);
ArcT bc=new ArcT(b,c);
ArcT de=new ArcT(d,e);
ArcT ef=new ArcT(e,f);
ArcT eg=new ArcT(e,g);
ArcT hg=new ArcT(h,g);
//
a.outgoing.add(ab);
a.outgoing.add(ac);
a.outgoing.add(ad);
a.outgoing.add(ah);
b.outgoing.add(bc);
d.outgoing.add(de);
e.outgoing.add(ef);
e.outgoing.add(eg);
h.outgoing.add(hg);
//
DeptSearch search=new DeptSearch();
//
System.out.println(" :");
search.widthSearch(a);
//
System.out.println(" :");
List visited=new ArrayList();
search.deptFisrtSearch(a,visited);
}
/*
*
* : , ,
* cur
* visited
*/
void deptFisrtSearch(NodeT cur,List visited){
// , ,
if(visited.contains(cur)) return;
visited.add(cur);
System.out.println(" :"+cur.word);
for(int i=0;i visited=new HashSet();
//
Queue q=new LinkedList();
//
q.offer(start);
while(!q.isEmpty()){
NodeT cur=q.poll();
// , ,
if(!visited.contains(cur)){
visited.add(cur);
System.out.println(" :"+cur.word);
for(int i=0;i outgoing;
//
String word;
public NodeT(String word){
this.word=word;
outgoing=new ArrayList();
}
}
/**
*
*/
class ArcT
{
NodeT start,end;/* , */
public ArcT(NodeT start,NodeT end){
this.start=start;
this.end=end;
}
}