图

图

图的简介

图（graph）是继表，树，之后一个更加混乱的数据结构，表是线性的，树好歹具有层次性，而图，再怎么看也啥性质也没有。下面就是一张图，用混乱来形容真的毫不为过(记住这个图，以后还会用到)


image

十分通俗地，字母A-G叫做图的顶点(Vertices ),用V来表示，连接这些顶点的黑灰色的边就叫做边(Edge),用E来表示，图就是这些点和边的集合：(V,E).具体可以参见wiki–图

注：有向图，无向图，连通图等这里不过多介绍，默认是无向图

图的存储

既然我们要写图的数据结构就得想办法用代码把图表示出来，总不能让计算机去图像识别吧 :neutral_face: 。下面来看一看图的存储。

仔细想想一个图可以有两种方式来确定它的特征：

  • 顶点以及顶点之间是否相连（是否有边）
  • 边以及边与边是否有交点（0，1，2）个

不用多说第一种表示方法更加简单明了吧。。。。 :no_mouth: 这样一来就清晰好多了，我们需要用一个数据集合描述点及点与点之间的关系，下面来看两种表示法。

邻接矩阵

设有V个点，用一个v*v的矩阵$A = a_{ij}$来表示点与点是否连接，如果点1和点2之间有边，那么$a_{12}=a_{21} = 1$，如果点3和4之间没有边相连，那么$a_{34}=a_{43} = 0$,这样一个用一个v*v的矩阵就能唯一表示一个含v个顶点的图了。如下图是一个例子:

1
2
3
4
5
6
7
8
mermaid

graph LR
A[1]---D[4]
A[1]---B[2]
A[1]---C[3]
D[4]---B[2]
C[3]---D[4]

如上一个含有四个顶点的图有（1，3），（1，4），（1，2），（2，4），（3，4）五条边，用矩阵表示为：

$$ \begin{bmatrix} 0 & 1 & 1&1 \ 1 & 0 & 0&1 \ 1 & 0& 0&1 \ 1&1&1&0 \ \end{bmatrix} $$

聪明的你一定不难发现方阵用数组来存储是最方便的吧,下面我给出java代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//MyGraph.java
public class MyGraph {
    private int V;//顶点
    private int array[][];//数组
    MyGraph(int v){//构造器
        this.V = v;
        this.array = new int[V][V];//初始化
    }
    
    void addEdge(int a,int b){//添加边的过程就是让矩阵上两个对称的点的距离等于1的过程
        this.array[a-1][b-1] = 1;
        this.array[b-1][a-1] = 1;
    }
}

邻接表

实际上用矩阵存储图是十分耗内存的，有n个点的图就要nn的矩阵，所需的存储空间以平方倍增长，这样明显极为不划算，下面提供一种更好也更常用的图的存储方法：*邻接表

邻接表的思维和邻接矩阵差不多，都是用一个数据集合来表示点以及点点之间是否有边，邻接表的思路是这样的：

  • 对于有V个顶点的图，用V个链表来存储点和点之间是否有边(也就是一个链表数组)

  • 每个顶点对应一个链表，如果在顶点A与另一顶点B之间添加了一条边，那么让A对应的链表插入B,当然B对应的链表也要插入A

    下面有一张示意图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
mermaid

graph LR
subgraph headerPointer LinkList array
A---B
B---C
C---D
D---E
end
A-->F[B]
F[B]-->G[C]
B-->H[A]
C-->I[A]
I-->J[E]
E-->K[C]

简单解释一下，这个图有ABCDE五个顶点，A->B->C表示A与B和A与C之间有一条边（切记不是A与B,B与C）,C->A->E表示C与A,C与E之间有一条边。

这里每个顶点对应的链表里面节点与节点之间没有前驱和后继的关系,这一点十分重要，最后给出java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Graph {
    private int V;//节点个数
    //每个节点对应的linkList
    private LinkedList<Integer> adj[];

    public Graph(int v){
        this.V = v;
        this.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);
        adj[w].add(v);
    }
}

总结

这一篇主要说明了（无向）图是啥，并介绍了两种图的存储结构：邻接矩阵和邻接表。在这里说明一下，以后的有关图的博客都以邻接表作为存储方法。

当然科学家的脑洞是无限的，图肯定不止这两种存储方法，其他方法不作介绍，如想了解请自行百度/谷歌。