图的存储方式（Leetcode743为例）

女爷i 2022-09-08 03:41 112阅读 0赞

对于n个节点、m条边的图，一般有三种存储方式：邻接矩阵、邻接表和类。

# 1. 邻接矩阵 #

定义n×n的二维矩阵，graph\[i\]\[j\]=w，表示从节点i到节点j有一条权重为w的边。

无向图的邻接矩阵是对角阵，无权图的邻接矩阵数值为0或1，表示是否连通。

邻接矩阵适用于**边数较多的稠密图**，边数接近点数的平方，m≈n^2。

int[][] graph = new int[n][n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            graph[i][j] = i == j ? 0 : Integer.MAX_VALUE;
        }
    }
    
    // 存储
    for (int[] time : times) {
        graph[time[0]][time[1]] = time[2];
    }
    
    // 遍历以k为起点的所有边
    for (int i = 0; i < n; i++) {
        System.out.println(graph[k][i])
    }
    
    // 遍历以k为终点的所有边
    for (int i = 0; i < n; i++) {
        System.out.println(graph[i][k])
    }

# 2. 邻接表 #

又称链式前向星存图，定义n个链表存储各节点对应的边集合、长度为n的数组存储链表的头节点，通常使用数组模拟单链表（头插法）。

邻接矩阵适用于**边数较少的稀疏图**，边数接近点数，m≈n。

int[] graph = new int[n];    // 节点对应边集合的头结点
    int[] edges = new int[m];    // 边的链表关系，用于找到下一条边
    int[] tails = new int[m];    // 边的终点
    int[] weights = new int[m];  // 边的权重
    Arrays.fill(graph, -1);
    Arrays.fill(edges, -1);
    
    // 存储
    for (int i = 0; i < m; i++) {
        int a = times[i][0];
        int b = times[i][1];
        int w = times[i][2];
        edges[i] = graph[a];       // 边i指向起点链表的当前头结点
        graph[a] = i;              // 起点链表的头结点更新为i
        tails[i] = times[i][1];    // 终点
        weights[i] = times[i][2];  // 权重
    }
    
    // 遍历以k为起点的所有边
    for (int i = graph[k]; i!=-1; i = edges[i]) {
        System.out.println(tails[i]);
        System.out.println(weights[i]);
    }

# 3. 类 #

创建Edge类记录边信息（起点、终点和权重），等同于使用二维数组edges\[m\]\[3\]存储边信息，是最简单的存储方式。

通常只有需要确保某种操作复杂度严格O(m)时，才会考虑使用。

class Edge {
        int a;
        int b;
        int w;
        
        public Edge(int a, int b, int w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }
    
    List<Edge> edges = new ArrayList<>();

**参考文献**：

*  [Leetcode743题解 by 宫水三叶][Leetcode743_ by]

**修订记录**：

<table> 
 <thead> 
  <tr> 
   <th align="center">日期</th> 
   <th align="center">版本号</th> 
   <th align="center">作者</th> 
   <th align="center">修订内容</th> 
   <th align="center">备注</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">2020-08-25</td> 
   <td align="center">1.0</td> 
   <td align="center">moonspiritacm</td> 
   <td align="center">创建文档</td> 
   <td align="center"></td> 
  </tr> 
 </tbody> 
</table>

[Leetcode743_ by]: https://leetcode-cn.com/problems/network-delay-time/solution/gong-shui-san-xie-yi-ti-wu-jie-wu-chong-oghpz/