概要

图是一种复杂的数据结构

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

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

图的组成

图有顶点和边组成。

图有顶点，边。

无向图

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

有向图

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

带权图

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

存储

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

邻接矩阵

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

邻接表

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

图的代码

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);}
}

小结

图这个数据结构

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