邻接表vs邻接矩阵：Java最短路径算法比较分析

.png)
# 1. 图论基础与最短路径问题

## 1.1 图论简介

图论是数学的一个分支，涉及图的性质和图的运算，是计算机科学中的一个重要领域，尤其在数据结构和算法设计上应用广泛。它由顶点（节点）和边（连接顶点的线）组成，可以用来表示实体之间的多种关系。

## 1.2 最短路径问题概述

最短路径问题是图论中的一个经典问题，目标是在一个带权图中找到两个顶点之间的最短路径。这一问题在计算机网络、交通规划、地图服务等领域中有着重要的实际应用。

## 1.3 解决最短路径的意义

通过理解并解决最短路径问题，不仅可以提高数据传输效率，缩短旅行时间，还可以在一定程度上优化资源配置，提升系统性能。因此，掌握最短路径算法对于IT从业者来说是必备的技能。

# 2. 图的表示方法

## 2.1 邻接表的定义和特性

### 2.1.1 邻接表的结构和实现

在图论中，邻接表是一种用来表示图的算法数据结构。它由图中每个顶点的邻接链表组成，用于存储各顶点相邻的其他顶点信息。在无向图中，每个顶点都拥有一个列表，其中包含了与它相连的其他所有顶点。

以下是邻接表的基本结构实现步骤：

1. 定义图数据结构。通常我们用一个字典或哈希表来存储每个顶点的邻接链表。
2. 遍历图中每个顶点，对于顶点i，将其所有邻接点j添加到邻接表中。
3. 对于有向图，直接将顶点i邻接到顶点j的边添加到顶点i的邻接链表中。
4. 对于无向图，需要在顶点i和顶点j的邻接链表中都添加对方，以表示边(i,j)存在。

class Graph {
    private int numVertices;  // 顶点的数量
    private LinkedList<Integer>[] adjacencyLists; // 邻接表

    public Graph(int vertices) {
        numVertices = vertices;
        adjacencyLists = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjacencyLists[i] = new LinkedList<>();
        }
    }

    public void addEdge(int source, int destination) {
        // 添加无向边
        adjacencyLists[source].add(destination);
        adjacencyLists[destination].add(source);
    }
}

### 2.1.2 邻接表的内存优化技术

为了节省内存，可以使用压缩邻接表。在压缩邻接表中，我们使用一个数组来记录顶点的邻接信息，对于每个顶点i，它的邻接信息被存储在从`start[i]`到`start[i+1] - 1`的位置。这种方法可以减少内存的使用，特别是在稀疏图中非常有效。

class CompressedAdjacencyList {
    private int numVertices;
    private int[] adjacencyList;
    private int[] start;

    public CompressedAdjacencyList(int vertices) {
        numVertices = vertices;
        adjacencyList = new int[vertices * (vertices - 1)]; // 假设为无向图
        start = new int[vertices + 1];
        Arrays.fill(start, -1); // 初始化为-1
    }

    public void addEdge(int source, int destination) {
        int edgeIndex = start[source] + 1;
        adjacencyList[edgeIndex] = destination;
        start[source] = edgeIndex;
        // 无向图需要双向添加
        edgeIndex = start[destination] + 1;
        adjacencyList[edgeIndex] = source;
        start[destination] = edgeIndex;
    }
}

## 2.2 邻接矩阵的定义和特性

### 2.2.1 邻接矩阵的结构和实现

邻接矩阵是一个二维数组，它用行列位置的值表示顶点之间的连接性。在无向图中，邻接矩阵是对称的，而在有向图中则不一定对称。如果顶点i和顶点j之间有边，那么在邻接矩阵中位置(i, j)和(j, i)的值通常是1（或边的权重），否则为0。

class AdjacencyMatrix {
    private int[][] matrix;
    private int numVertices;

    public AdjacencyMatrix(int vertices) {
        numVertices = vertices;
        matrix = new int[vertices][vertices];
    }

    public void addEdge(int source, int destination) {
        matrix[source][destination] = 1; // 有向图
        matrix[destination][source] = 1; // 无向图添加双边
    }
}

### 2.2.2 邻接矩阵的内存使用分析

邻接矩阵的一个主要缺点是它需要O(V^2)的空间复杂度，其中V是顶点的数量。这意味着即使是稀疏图，也需要存储大量的0元素，这造成了空间的浪费。尤其是对于大型图，邻接矩阵可能不是内存使用最优化的选择。

## 2.3 邻接表与邻接矩阵的对比

### 2.3.1 时间复杂度对比

- **邻接表**：添加边的时间复杂度是O(1)，但是如果要检查两个顶点是否相连，时间复杂度是O(min(n,m))，其中n是顶点数，m是边数。
- **邻接矩阵**：添加边的时间复杂度是O(1)，但是检查两个顶点是否相连的时间复杂度是O(1)，这是因为直接通过索引位置就可以确认。

### 2.3.2 空间复杂度对比

- **邻接表**：对于稀疏图来说，空间复杂度可以接近O(E)，其中E是边的数量。
- **邻接矩阵**：对于稠密图，空间复杂度是O(V^2)，对于稀疏图，这种空间浪费更为明显。

接下来的章节将详细介绍Java中图的表示实现，其中包括邻接表和邻接矩阵的Java数据结构设计，以及图的遍历算法实现。

# 3. Java中的图表示实现

## 3.1 利用邻接表实现图

### 3.1.1 邻接表的数据结构设计

在计算机科学中，图是由节点（vertices）和连接节点的边（edges）组成的抽象数据结构。邻接表是一种用于表示图的数据结构，它利用一个节点对应多个边的链表，有效地表示图的各个顶点之间的邻接关系。

在Java中实现邻接表，通常可以使用`HashMap`或`ArrayList`来存储邻接链表。每个顶点对应一个列表，列表中包含了与该顶点相邻的所有顶点。下面是一个简单的邻接表实现：

import java.util.*;

class Graph {
    private int V;   // 顶点数
    private LinkedList<Integer> adj[]; // 邻接表

    // 构造函数
    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    // 添加边到图中
    void addEdge(int v, int w) {
        adj[v].add(w); // 将 w 添加到 v 的链表中
    }

    // 打印图的邻接表表示
    void printGraph() {
        for (int v = 0; v < V; ++v)
        {
            System.out.print("\n Adjacency list of vertex " + v);
            System.out.print(" \n head");
            for (Integer i : adj[v])
                System.out.print(" -> " + i);
            System.out.println();
        }
    }
}

在上述代码中，`addEdge`方法用于添加边，`printGraph`方法用于打印图的邻接表表示。这可以帮助我们直观地理解图的结构。

### 3.1.2 图的遍历算法实现

图的遍历指的是从某个顶点出发，按照某种规则，系统地访问图中的每一个顶点，且仅访问一次。深度优先搜索（DFS）和广度优先搜索（BFS）是两种常用的图遍历算法。

下面是使用DFS算法遍历图的Java实现：

import java.util.*;

class Graph {
    // ... 上述的数据结构定义 ...

    // DFS的辅助函数
    void DFSUtil(int v, boolean visited[]) {
        // 标记当前节点为已访问
        visited[v] = true;
        System.out.print(v + " ");

        // 递归访问所有未访问的邻接顶点
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext()) {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // DFS算法的实现
    void DFS(int v) {
        // 默认全部顶点未访问
        boolean visited[] = new boolean[V];

        // 调用递归辅助函数，遍历所有顶点
        DFSUtil(v, visited);
    }
}

public class Main {
    public static void main(String args[]) {
        Graph g = new Graph(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("深度优先遍历（从顶点2开始）:");
        g.DFS(2);
    }
}

在上述代码中，`DFSUtil`是一个递归函数，用于深度优先遍历图。`DFS`方法则是调用`DFSUtil`并传入一个未访问的顶点。

## 3.2 利用邻接矩阵实现图

### 3.2.1 邻接矩阵的数据结构设计

另一种表示图的方式是使用邻接矩阵，它是一个二维数组。如果顶点i和顶点j之间有边相连，则矩阵中的第i行第j列的元素为1（或边的权重），否则为0。

以下是使用邻接矩阵表示图的Java实现：

class Graph {
    private int V; // 顶点的数量
    private int[][] graph; // 邻接矩阵

    // 构造函数
    Graph(int v) {
        V = v;
        graph = new int[v][v];
    }

    // 添加边
    void addEdge(int v, int w) {
        graph[v][w] = 1; // 设置v-w边
        graph[w][v] = 1; // 由于无向图，设置w-v边
    }

    // 打印邻接矩阵
    void printGraph() {
        System.out.println("图的邻接矩阵：");
        for (int i = 0; i < V; i++) {
            fo