图的遍历

发表于 2022-12-27 分类于 algrithom 阅读次数：
代码实现

/**
 * 无向图
 */
public class NoDirectionGraph {
 
private int mMaxSize; //图中包含的最大顶点数
private GraphVertex[] vertexList; //顶点数组
private int[][] indicatorMat; //指示顶点之间的连通关系的邻接矩阵
private int nVertex; //当前实际保存的顶点数目


public NoDirectionGraph(int maxSize) {
    mMaxSize = maxSize;
    vertexList = new GraphVertex[mMaxSize];
    indicatorMat = new int[mMaxSize][mMaxSize];
    nVertex = 0;
    //初始化邻接矩阵元素为0
    for(int j=0;j&lt;mMaxSize;j++) {
        for(int k=0;k&lt;mMaxSize;k++) {
            indicatorMat[j][k] = 0;
        }
    }
}


public void addVertex(GraphVertex v) {
    if(nVertex &lt; mMaxSize) {
        vertexList[nVertex++] = v;
        
    } else {
        System.out.println("---插入失败，顶点数量已达上限!");
    }
}

/**
 * 修改邻接矩阵，添加新的边
 * @param start
 * @param end
 */
public void addEdge(int start,int end) {
    indicatorMat[start][end] = 1;
    indicatorMat[end][start] = 1;
}

/**
 * 打印邻接矩阵
 */
public void printIndicatorMat() {
    
    for(int[] line:indicatorMat) {
        for(int i:line) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}

/**
 * 深度优先遍历
 * @param vertexIndex 表示要遍历的起点,即图的邻接矩阵中的行数
 */
public void DFS(int vertexIndex) {
    ArrayStack stack = new ArrayStack();
    //1.添加检索元素到栈中
    vertexList[vertexIndex].setVisited(true);
    stack.push(vertexIndex);
    int nextVertexIndex = getNextVertexIndex(vertexIndex);
    while(!stack.isEmpty()) { //不断地压栈、出栈，直到栈为空(检索元素也没弹出了栈)为止
        if(nextVertexIndex != -1) {
            vertexList[nextVertexIndex].setVisited(true);
            stack.push(nextVertexIndex);
            stack.printElems();
        } else {
            stack.pop();
        }
        //检索当前栈顶元素是否包含其他未遍历过的节点
        if(!stack.isEmpty()) {
            nextVertexIndex = getNextVertexIndex(stack.peek()); 
        }
    }
}

/**
 * 得到当前顶点的下一个顶点所在行
 * @param column
 * @return
 */
public int getNextVertexIndex(int column) {
    for(int i=0;i&lt;indicatorMat[column].length;i++) {
        if(indicatorMat[column][i] == 1 &amp;&amp; !vertexList[i].isVisited()) {
            return i;
        }
    }
    return -1;
}

/**
 * 广度优先遍历
 * @param vertexIndex 表示要遍历的起点,即图的邻接矩阵中的行数
 */
public void BFS(int vertexIndex) {
    ChainQueue queue = new ChainQueue();
    vertexList[vertexIndex].setVisited(true);
    queue.insert(new QueueNode(vertexIndex));
    int nextVertexIndex = getNextVertexIndex(vertexIndex);
    while(!queue.isEmpty()) {
        if(nextVertexIndex != -1) {
            vertexList[nextVertexIndex].setVisited(true);
            queue.insert(new QueueNode(nextVertexIndex));
        } else {
            queue.remove();
        }
        if(!queue.isEmpty()) {
            nextVertexIndex = getNextVertexIndex(queue.peek().data);
            queue.printElems();
        }
    }
}

}
/**

使用数组实现栈结构
 */
public class ArrayStack {
 private int[] tArray;
 private int topIndex = -1; //表示当前栈顶元素的索引位置
 private int CAPACITY_STEP = 12; //数组容量扩展步长
 public ArrayStack() {
 /创建泛型数组的一种方法/
 tArray = new int[CAPACITY_STEP];
 }
 /**

弹出栈顶元素方法
@return
  */
 public int pop() {
 if(isEmpty()) {
 System.out.println(“错误，栈中元素为空，不能pop”);
 return -1;
 } else {
 int i = tArray[topIndex];
 tArray[topIndex–] = -1; //擦除pop元素
 return i;
 }
 }

 /**

向栈中插入一个元素
@param t
  */
 public void push(int t) {
 //检查栈是否已满
 if(topIndex == (tArray.length-1)) {
 //扩展容量
 int[] tempArray = new int[tArray.length + CAPACITY_STEP];
 for(int i=0;i<tArray.length;i++) {
     tempArray[i] = tArray[i];
 }
 tArray = tempArray;
 tempArray = null;
 } else {
 topIndex ++;
 tArray[topIndex] = t;
 }
 }

 /**

得到栈顶元素，但不弹出
@return
  */
 public int peek() {
 if(isEmpty()) {
 System.out.println(“错误，栈中元素为空，不能peek”);
 return -1;
 } else {
 return tArray[topIndex];
 }
 }

 /**

判断当前栈是否为空
@return
  */
 public boolean isEmpty() {
 return (topIndex < 0);
 }

 /**

打印栈中元素
  */
 public void printElems() {
 for(int i=0;i<=topIndex;i++) {
 System.out.print(tArray[i] + “ “);
 }
 System.out.println();
 }



}
/**

使用链表实现队列
 */
public class ChainQueue {
 private QueueNode head; // 指向队列头节点
 private QueueNode tail; // 指向队列尾节点
 private int size = 0; // 队列尺寸
 public ChainQueue() {
 }
 /**

插入新节点到队列尾
  */
 public void insert(QueueNode node) {
 // 当然也可以这么写,添加tail.prev = node
 if (head == null) {
 head = node;
 tail = head;
 } else {
 node.next = tail;
 tail.prev = node; // 双向连接，确保head.prev不为空
 tail = node;
 }
 size++;


 }
 /**

移除队列首节点
  */
 public QueueNode remove() {
 if (!isEmpty()) {
 QueueNode temp = head;
 head = head.prev;
 size–;
 return temp;
 } else {
 System.out.println(“异常操作，当前队列为空!”);
 return null;
 }
 }

 /**

队列是否为空

@return
  */
 public boolean isEmpty() {
 if (size > 0) {
 return false;
 } else {
 return true;
 }
 }

 /**

返回队列首节点，但不移除
  */
 public QueueNode peek() {
 if (!isEmpty()) {
 return head;
 } else {
 System.out.println();
 System.out.println(“异常操作，当前队列为空!”);
 return null;
 }
 }

 /**

返回队列大小

@return
  */
 public int size() {
 return size;
 }

 /**

打印队列中的元素
  */
 public void printElems() {
 QueueNode tempNode = head;
 while(tempNode != null) {
 System.out.print(tempNode.data + “ “);
 tempNode = tempNode.prev;
 }
 System.out.println();
 }



}
/**

节点类

@author wly


 */
class QueueNode {
    QueueNode prev;
    QueueNode next;
int data;

public QueueNode(int data) {
    this.data = data;
}
public int getData() {
    return data;
}
public void setData(int data) {
    this.data = data;
}
@Override
public String toString() {
    // TODO Auto-generated method stub
    super.toString();
    return data + “”;
}

}