java用栈表示图的广度遍历遍历代码

在 Java 中，我们可以使用栈（Stack）数据结构来实现图的广度优先搜索（Breadth-First Search，简称 BFS）。这是因为栈的特点就是先进先出（FIFO），非常适合处理需要逐层探索的问题。以下是使用邻接列表（Adjacency List）存储图的简单示例：

import java.util.*;

class Graph {
    private int vertices;
    private LinkedList<Integer>[] adjList;

    // 构造函数，初始化图
    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    // 添加边
    void addEdge(int src, int dest) {
        adjList[src].add(dest);
    }

    // 广度优先搜索
    public void bfs(int start) {
        boolean[] visited = new boolean[vertices]; // 标记节点是否已访问
        Queue<Integer> queue = new LinkedList<>(); // 存储待访问的节点

        // 将起始节点标记为已访问并加入队列
        visited[start] = true;
        queue.add(start);

        while (!queue.isEmpty()) { // 当队列不为空时继续遍历
            int node = queue.poll();
            System.out.print(node + " "); // 输出当前节点

            // 遍历邻居节点
            Iterator<Integer> neighborIterator = adjList[node].listIterator();
            while (neighborIterator.hasNext()) {
                int neighbor = neighborIterator.next();

                // 如果邻居未访问过，则标记并加入队列
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(4); // 假设我们有一个有4个顶点的图
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3); // 无向环，简化演示

        System.out.println("BFS starting from vertex 2:");
        graph.bfs(2);
    }
}

在这个例子中，我们首先创建一个图，并添加边。然后通过`bfs`方法开始从指定的起始节点（例如2）开始广度优先遍历。每次从队列中取出一个节点，打印它并将其未访问的邻居加入队列。这样就能完成整个图的广度优先遍历。