本文共 1861 字，大约阅读时间需要 6 分钟。

1. 什么是图？

前面说完了树这种数据结构，接下来在看看一种更加复杂的非线性数据结构——图。

先看看下面图这种数据结构的图片演示吧：

像上图这样的数据结构就叫做图了，图中的每个节点叫做 顶点 ，各个顶点之间的连接关系叫做 边 ，每个顶点有多少条边，叫做这个顶点的 度 。其实图这种数据结构比较适合用来存储我们常用的微信、微博好友关系。例如存储微信好友，例如两个人互加了微信，就相当于在两个顶点之间加上一条边，而顶点的度则表示一个人有多少微信好友。

而微博这样的存储关系，要稍微复杂一些，因为微博允许当方面关注，例如 A 关注了 B ，而 B 可以不关注 A，这样的关系，我们可以在图中引入方向的概念，先看下图：

例如 A 关注了 B，那么直接将 A 的边指向 B 即可。这样有方向关系的图，叫做 有向图 ，显然，没有方向关系的图，就叫做 无向图 。

无向图中有度的概念，表示一个顶点有多少条边，而有向图中的度，则还有 入度 和 出度 的区分，例如 A 指向 B，叫做 A 顶点的出度，E 指向了 A，叫做 A 的入度。不难理解，对应到微博的关系中，一个顶点的出度，就表示他关注了多少人，入度，则表示他有多少粉丝。

2. 图是如何存储的？

图有两种存储的方式，第一种叫做邻接矩阵，其底层是利用二维数组来存储的。对于无向图，如果顶点 i 和 j 之间有边，则在二维数组中 A[i] [j] 和 A[j] [i] 位置处标记为 1 ，对于有向图，如果 i 指向了 j，则将二维数组中 A[i] [j] 位置标记为 1，类似，如果 j 指向了 i，则将二维数组中 A[j] [i] 位置标记为 1。看下图的说明就很容易明白了：

这种存储方式虽然支持较为高效的查找操作，因为可以直接根据数组下标取出数据，但是存在的问题便是比较浪费存储空间，特别是对于数据量较大的情况。

另一种更加常用的图存储方式是邻接表，每个顶点对应一个链表，就像下图这样：

上面是使用的有向图，每个顶点对应的链表存储的是该顶点所指向的顶点，如果是无向图的话，那就更简单了，每个顶点链表存储的是与该顶点有边关系的顶点。

3. 简单实现一个图

接下来我是用代码简单使用了一个图，你可以看看，顺便理解一下：

public class Graph {    private int vertex;//图中的顶点个数    private LinkedList
   
    [] list;    public Graph(int vertex) {        this.vertex = vertex;        list = new LinkedList[vertex];        for (int i = 0; i < vertex; i++) {            list[i] = new LinkedList();        }    }    //两个顶点之间建立边关系    public void addSide(int v1, int v2){        if (v1 >= vertex || v2 >= vertex || v1 == v2) return;        if (!list[v1].contains(v2))            list[v1].add(v2);        if (!list[v2].contains(v1))            list[v2].add(v1);    }    //删除顶点之间的边    public void removeSide(int v1, int v2){        if (v1 >= vertex || v2 >= vertex || v1 == v2) return;        if (list[v1].contains(v2))            list[v1].remove(v2);        if (list[v2].contains(v1))            list[v2].remove(v1);    }    //列出与某顶点有边关系的所有顶点    public void listVertexes(int v){        if (v >= vertex) return;        System.out.println(list[v].toString());    }}
   

转载地址：https://blog.csdn.net/Rose_DuanM/article/details/88672531 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！