图的宽度遍历java实现

一.什么是宽度遍历？

我们可通过下图理解：


下面我们用代码重现上面的情况：

二.代码实现：

//辅助队列
class ArrayQueue{
    private int front;
    private int rear;
    private int capacity;
    private int [] array;
    //有参构造方法
    public ArrayQueue(int size)
    {
        capacity=size;
        front=-1;
        rear=-1;
        array = new int[size];
    }


    //判断队列是否为空
    public boolean isEmpty()
    {   return (front == -1);}
    //判断队列是否满了
    public boolean isFull()
    {  return ((rear+1)%capacity==front); }

    //得到队列的大小
    public int getQueueSize()
    { return ((capacity-front+rear+1)%capacity); }

    //向队列添加值
    public void enQueue(int data)
    {
        if(isFull())
        {
            System.out.println("Queue Overflow");
        }
        else{
            rear = (rear+1)%capacity;
            array[rear]=data;
            if(front==-1)
                front=rear;
        }
    }
    //弹出当前队列最先进入的值
    public int deQueue()
    {
        int data=0;
        if(isEmpty()){
            System.out.println("Queue Empty");
        }
        else {
            data=array[front];
            if(front==rear)
            {
                front = rear-1;

            }else {
                front = (front+1)%capacity;
            }
        }
        return data;
    }
}


public class Graph2 {

    private final int maxVertices=20;//定义最大节点数
    private Vertex vertexList[];//节点数组
    private int adjMatrix[][];//存储两点关系的数组
    private ArrayQueue theQueue;//辅助队列
    private int vertexCount;//记录当前的节点数

    public Graph2()//图构造方法
    {
        vertexList = new Vertex[maxVertices];//分配空间
        adjMatrix = new int[maxVertices][maxVertices];//分配空间
        vertexCount=0;//初始值
        for(int y=0;y<maxVertices;y++)
        {
            for(int x=0;x<maxVertices;x++)
            {
                adjMatrix[x][y]=0;//给所有点关系赋为0
            }
            theQueue=new ArrayQueue(10);
        }
    }

    public void addVertex(char lab)//添加节点信息
    {
        vertexList[vertexCount++]=new Vertex(lab);
    }

    public void addEdge(int start,int end)//添加节点关系
    {
        adjMatrix[start][end]=1;
        adjMatrix[end][start]=1;
    }

    public void displayVertex(int v)//展示节点信息
    {
        System.out.println(vertexList[v].label);
    }


    public void bfs()//宽度度遍历方法
    {
        vertexList[0].visited=true;
        displayVertex(0);
        theQueue.enQueue(0);
        int v2;
        while(!theQueue.isEmpty())
        {
            int v1=theQueue.deQueue();
            while((v2=getAdjUnvisitedVertex(v1))!=-1)
            {
                vertexList[v2].visited=true;
                displayVertex(v2);
                theQueue.enQueue(v2);
            }
        }
        for(int j=0;j<vertexCount;j++)
            vertexList[j].visited=false;
    }


    public int getAdjUnvisitedVertex(int v)//得到未被访问的节点位置
    {
        for(int j=0;j<vertexCount;j++)
        {
            if(adjMatrix[v][j]==1&&vertexList[j].visited==false)
                return j;
        }
        return -1;
    }

}

测试方法：

public class text {
    public static void main(String[] args) {

        Graph2 test=new Graph2();
        test.addVertex('A');
        test.addVertex('B');
        test.addVertex('C');
        test.addVertex('D');
        test.addVertex('E');
        test.addVertex('F');
        test.addVertex('G');
        test.addVertex('H');//7
        test.addEdge(0,1);
        test.addEdge(1,2);
        test.addEdge(1,7);
        test.addEdge(2,3);
        test.addEdge(2,4);
        test.addEdge(4,7);
        test.addEdge(4,6);
        test.addEdge(4,5);
        test.bfs();
    }
}

结果：