// 深搜
private void dfs(int v) {
visited[v] = true;
System.out.print(v+" ");
for (int i = 0; i que = new LinkedList();
que.offer(v);
while (!que.isEmpty()) {
v = que.poll();
System.out.print(v+" ");
visited[v] = true;
//将被访问节点的分支节点(邻接点)加入到队列中
for (int i = 0; i <G.get(v).size(); i++) {
int k=G.get(v).get(i);
if (!visited[k]){
que.add(k);
visited[k] = true;
}
}

public class ALGraph implements IGraph{
　　//图的邻接表类的描述
private GraphKind kind;
private int vexNum,arcNum;
private VNode[] vexs;

    public void createGraph() {  
    // TODO Auto-generated method stub  
    Scanner sc = new Scanner(System.in);  
    System.out.println("请输入图的类型");  
    GraphKind kind =GraphKind.valueOf(sc.next());  
    switch(kind)  
    {  
    case UDG:  
        createUDG();  
        break;  
    case DG:  
        createDG();  
        break;  
    case UDN:  
        createUDN();  
        break;  
    case DN:  
        createDN();  
        break;  
    }  
}

private void createDN() {  
    // TODO Auto-generated method stub  
    //创建有向网  
    Scanner sc=new Scanner(System.in);  
    System.out.println("下面要创建带权的有向图（有向网）。请分别输入图的顶点数、图的边数");  
    vexNum=sc.nextInt();  
    arcNum=sc.nextInt();  
    vexs=new VNode\[vexNum\];  
    System.out.println("请分别输入图的各顶点");  
    for(int v=0;v<vexNum;v++)  
        vexs\[v\]=new VNode(sc.next());  
    System.out.println("请输入各边的顶点及其权值：");  
    for(int k=0;k<arcNum;k++)  
    {  
        int v=locateVex(sc.next());//弧尾  
        int u=locateVex(sc.next());//弧头  
        int value=sc.nextInt();  
        addArc(v,u,value);  
    }  
    for(VNode v:vexs)  
    System.out.print(v.getData()+" ");

}

    //在图中插入边（或弧）节点，图右顶点集合边集组成，因此创建图必须先建立图的顶点集合边集  
private void addArc(int v, int u, int value) {  
    // TODO Auto-generated method stub  
    ArcNode arc = new ArcNode(u,value);  
    arc.setNextArc(vexs\[v\].getFirstArc());  
    vexs\[v\].setFirstArc(arc);

}

//图的邻接表表示中的顶点节点类
public class VNode {

private Object data;// 顶点信息  
private ArcNode firstArc; //指向第一条依附于该顶点的弧  

}

//图的邻接表表示中 边结点 类
public class ArcNode {
private int adjVex;//该弧所指向的顶点位置
private int value;//边或弧的权值
private ArcNode nextArc;//指向下一条弧
}