如何遍历java邻接表

Java

小樊

2024-09-15 02:08:16

栏目: 编程语言

在Java中，邻接表通常用来表示图（Graph）的数据结构

首先，创建一个邻接表来表示图。这里我们使用HashMap和ArrayList来实现邻接表：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Graph {
    private Map<Integer, List<Integer>> adjacencyList = new HashMap<>();

    public void addVertex(int vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }

    public void addEdge(int source, int destination) {
        adjacencyList.get(source).add(destination);
        adjacencyList.get(destination).add(source);
    }
}

然后，编写一个方法来遍历邻接表。这里我们使用深度优先搜索（DFS）算法来遍历邻接表：

import java.util.Stack;

public class GraphTraversal {
    public void depthFirstTraversal(Graph graph, int startVertex) {
        Stack<Integer> stack = new Stack<>();
        boolean[] visited = new boolean[graph.adjacencyList.size()];

        stack.push(startVertex);

        while (!stack.isEmpty()) {
            int currentVertex = stack.pop();

            if (!visited[currentVertex]) {
                System.out.println("Visited vertex: " + currentVertex);
                visited[currentVertex] = true;

                for (int neighbor : graph.adjacencyList.get(currentVertex)) {
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }
}

最后，在主函数中创建一个图并遍历它的邻接表：

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addVertex(0);
        graph.addVertex(1);
        graph.addVertex(2);
        graph.addVertex(3);
        graph.addVertex(4);

        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);

        GraphTraversal traversal = new GraphTraversal();
        traversal.depthFirstTraversal(graph, 0);
    }
}

运行上述代码，将会输出以下结果：

Visited vertex: 0
Visited vertex: 1
Visited vertex: 3
Visited vertex: 2
Visited vertex: 4

这个例子展示了如何在Java中使用邻接表表示图，并使用深度优先搜索算法遍历邻接表。你可以根据需要修改这些代码以适应不同类型的图和遍历算法。

如何遍历java邻接表

最新问答

相关标签