java实现图的邻接表存储结构的两种方式及实例应用详解

下面就给您详细讲解“java实现图的邻接表存储结构的两种方式及实例应用详解”的完整攻略。

一、什么是图的邻接表存储结构？

图是一种重要的数据结构，主要由顶点和边组成。邻接表存储结构是一种常见的存储图的方式，它采用链表来表示图中的每个顶点及其相邻的顶点。其中，每个顶点对应一个单链表，存储该顶点与其他顶点相邻的边。

邻接表存储结构通常使用数组加链表的方式实现。数组中的每个元素表示一个顶点，每个元素对应一个链表，链表中存储该顶点的所有相邻顶点。该结构可以表示图中的各种关系，例如有向图和无向图等。

二、两种实现方式及示例

1. 使用单链表

使用单链表实现邻接表存储结构，每个节点表示一个相邻的顶点。示例如下：

class GraphNode {
    int index; // 顶点编号
    GraphNode next; // 指向下一个相邻顶点的节点
    public GraphNode(int index, GraphNode next) {
        this.index = index;
        this.next = next;
    }
}

class Graph {
    int n; // 顶点个数
    GraphNode[] nodes; // 存储各个顶点的链表头节点
    public Graph(int n) {
        this.n = n;
        nodes = new GraphNode[n];
    }
    public void addEdge(int u, int v) {
        nodes[u] = new GraphNode(v, nodes[u]); // 将v加入u的链表中
        nodes[v] = new GraphNode(u, nodes[v]); // 将u加入v的链表中，因为是无向图
    }
}

2. 使用双向链表

使用双向链表实现邻接表存储结构，每个节点表示一条边。示例如下：

class EdgeNode {
    int start, end; // 边的起点和终点
    EdgeNode next, prev; // 指向下一条和上一条相邻边的节点
    public EdgeNode(int start, int end, EdgeNode next, EdgeNode prev) {
        this.start = start;
        this.end = end;
        this.next = next;
        this.prev = prev;
    }
}

class Graph {
    int n; // 顶点个数
    EdgeNode[] nodes; // 存储各个顶点的相邻边链表头节点
    public Graph(int n) {
        this.n = n;
        nodes = new EdgeNode[n];
    }
    public void addEdge(int u, int v) {
        nodes[u] = new EdgeNode(u, v, nodes[u], null); // 将(u,v)加入u的相邻边链表中
        nodes[v] = new EdgeNode(v, u, nodes[v], null); // 将(v,u)加入v的相邻边链表中，因为是无向图
        nodes[u].next.prev = nodes[u]; // 修改u的相邻边链表头节点前一个节点的指针
        nodes[v].next.prev = nodes[v]; // 修改v的相邻边链表头节点前一个节点的指针
    }
}

三、应用

图的邻接表存储结构可以应用于很多图论算法中，例如最短路径算法、最小生成树算法等。下面以最短路径算法为例，简要介绍其应用过程。

最短路径算法通常采用广度优先搜索(BFS)来实现。通过邻接表存储结构，可以方便地获取某个顶点的相邻顶点列表，并避免了使用邻接矩阵存储时需要搜索整个矩阵的麻烦。使用邻接表存储结构的最短路径算法示例如下：

public void bfs(int s) {
    boolean[] visited = new boolean[n];
    int[] distance = new int[n];
    Queue<Integer> queue = new LinkedList<>();
    visited[s] = true;
    distance[s] = 0;
    queue.offer(s);
    while (!queue.isEmpty()) {
        int u = queue.poll();
        GraphNode p = nodes[u];
        while (p != null) {
            int v = p.index;
            if (!visited[v]) {
                visited[v] = true;
                distance[v] = distance[u] + 1;
                queue.offer(v);
            }
            p = p.next;
        }
    }
}

上面的代码中，visited数组表示每个顶点是否被访问过，distance数组表示从起点到每个顶点的最短距离。BFS搜索每个顶点的相邻顶点，并将其加入队列中，直到遍历完所有的顶点为止。

四、总结

上述是java实现图的邻接表存储结构的两种方式及实例应用的详解。在应用邻接表存储结构时，需要注意实现细节，并且根据具体问题选择最优的存储方式。