深度优先搜索与广度优先搜索

// 用于实现深度优先搜索的栈类
class  StackX ... {
    private final int SIZE=20;
    private int[] st;
    private int top;
    public StackX()...{
        st=new int[SIZE];
        top=-1;
    }
    public void push(int j)...{
        st[++top]=j;
    }
    public int pop()...{
        return st[top--];
    }
    public int peek()...{
        return st[top];
    }
    public boolean isEmpty()...{
        return top==-1;
    }
}
// 用于实现广度优先搜索的队列类
class  Queue ... {
    private final int SIZE=20;
    private int[] queArray;
    private int front;
    private int rear;
    public Queue()...{
        queArray=new int[SIZE];
        front=0;
        rear=-1;
    }
    public void insert(int j)...{
        if(rear==SIZE-1)
            rear=-1;
        queArray[++rear]=j;
    }
    public int remove()...{
        int temp=queArray[front++];
        if(front==SIZE)
            front=0;
        return temp;
    }
    public boolean isEmpty()...{
        return ((rear+1==front)||(front+SIZE-1==rear));
    }
}
// 顶点类
class  Vertex ... {
    public char label;
    public boolean wasVisited;
    public Vertex(char lab)...{
        label=lab;
        wasVisited=false;
    }
}
// 图类
public   class  Graph  ... {
    
    private final int MAX_VERTS=20;
    private Vertex vertexList[];
    private int adjMat[][];
    private int nVerts;
    private StackX theStack;
    private Queue theQueue;
    
    /** *//** Creates a new instance of Graph */
    public Graph() ...{
        vertexList=new Vertex[MAX_VERTS];
        adjMat=new int[MAX_VERTS][MAX_VERTS];
        nVerts=0;
        for (int j = 0; j < MAX_VERTS; j++) ...{
            for (int k = 0; k < MAX_VERTS; k++) ...{
                adjMat[j][k]=0;
            }
        }
        theStack=new StackX();
        theQueue=new Queue();
    }
    //增加一个顶点
    public void addVertex(char lab)...{
        vertexList[nVerts++]=new Vertex(lab);
    }
    //增加一条边
    public void addEdge(int start,int end)...{
        adjMat[start][end]=1;
        adjMat[end][start]=1;
    }
    public void displayVertex(int v)...{
        (vertexList[v].label);
    }
    //深度优先搜索
    public void dfs()...{
        vertexList[0].wasVisited=true;
        displayVertex(0);
        (0);
        while(!())...{
            int v=getAdjUnvisitedVertex(());
            if(v==-1)
                ();
            else...{
                vertexList[v].wasVisited=true;
                displayVertex(v);
                (v);
            }
        }
        for(int j=0;j<nVerts;j++)
            vertexList[j].wasVisited=false;
    }
    //得到与v顶点邻接且未访问过的顶点标号
    public int getAdjUnvisitedVertex(int v)...{
        for (int j = 0; j < nVerts; j++) ...{
            if(adjMat[v][j]==1&&vertexList[j].wasVisited==false)
                return j;
        }
        return -1;
    }
    //广度优先搜索
    public void bfs()...{
        vertexList[0].wasVisited=true;
        displayVertex(0);
        (0);
        int v2;
        while(!())...{
            int v1=();
            while((v2=getAdjUnvisitedVertex(v1))!=-1)...{
                vertexList[v2].wasVisited=true;
                displayVertex(v2);
                (v2);
            }
        }
        for (int j = 0; j < nVerts; j++) ...{
            vertexList[j].wasVisited=false;
        }
    }
    
}