数据结构===图

概要

图是一种复杂的数据结构

图包括顶点，边。图的分类有无向图，有向图，带权图。

按照存储有邻接矩阵，邻接表。

图的组成

图有顶点和边组成。

图有顶点，边。

无向图

对于无向图来说，还有个概念，叫做度。就是边的条数。有顶点，有边，就构成了一个图。

有向图

对于有向图来说，度有方向，分为入度和出度。顶点，边，入度，出度，构成了一个有向图。

带权图

对于带权图来说，有个概念，每条边有个权重。

存储

怎么来存储图这种数据结构呢？这就有邻接矩阵和邻接表。

邻接矩阵

邻接矩阵是一种使用二维数组来表示图的方法，其中的元素表示两个顶点之间是否有边。在加权图中，矩阵中的元素可以表示边的权重。

邻接表

在这种表示方法中，每个顶点都关联一个列表，这个列表存储了所有与该顶点直接相连的其他顶点。在加权图中，这个列表中的元素可以是顶点对，或者包含顶点和权重的元组。

图的代码

public class Graph { // 无向图
  private int v; // 顶点的个数
  private LinkedList<Integer> adj[]; // 邻接表

  public Graph(int v) {
    this.v = v;
    adj = new LinkedList[v];
    for (int i=0; i<v; ++i) {
      adj[i] = new LinkedList<>();
    }
  }

  public void addEdge(int s, int t) { // 无向图一条边存两次
    adj[s].add(t);
    adj[t].add(s);
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

小结

图这个数据结构

本篇主要记录了跟图有关的概念，比如，顶点，边。无向图，有向图，带权图；邻接矩阵，邻接表。基本上就这么多吧。跟图相关的概念。接下来可以聊聊跟图相关的算法了。像深度优先，广度优先；当然还有些其他的应用，最短路径，生成最小树，朋友圈好友等等。