图的表示法——边列表#

一、引言#

之前我们讨论了图的特性，但是我们还没真正表示出图这样一个逻辑结构。

G=（V,E)

为了在内存中表示图，我们可以创建两个列表，一个用来存储所有的顶点，另外一个用来存储所有的边。

二、演示#

列表的实现可以用动态数组。

下图第一个列表包含顶点的名字，所以它将会是一个简单的名字列表或者字符串列表。

而边是由它的两个端点来标识的，因此我们可以做的是把边当作一个对象，它由两个域组成，我们可以把边定义为一个结构体或者类。

1
struct Edge{
2
  const char *startvsrtex;
3
  const char *endvertex;
4
}
5
或者
6
class Edge{
7
  string *startvsrtex;
8
  string *endvertex;
9
}

我们来将图中的边填进去吧，由于是无向图，所以随便哪个都可以作为起点。

由于是无向边，所有有(F,H)同样也会有（H,F)，但是我们不需要那么做，那样会浪费内存。

现在我们再来赋予一些权重，那么该如何存储呢？

我们可以再增加一个域用来存储，你知道的，画那么多很麻烦😎

1
struct Edge{
2
  const char *startvsrtex;
3
  const char *endvertex;
4
    int weight;
5
}
6
或者
7
class Edge{
8
  string *startvsrtex;
9
  string *endvertex;
10
    int weight;
11
}
12
string vertex_list[MAX_SIZE];
13
Edge edge_list[Max_size];

这就是我们实现图的一种方式，两个列表一个存储边一个存储顶点。

但是这样并不奈斯，我们实现存储会看开销。

三、空间复杂度#

开销一般就是时间与内存。

首先我们来看看空间复杂度。

对于第一个顶点列表，最小的内存使用量就是顶点数量。

因为我们这里对字符串的使用都是片面的，只是用了一个字符，如果我们使用不同的命名来存储顶点，那么内存开销会更大！

但是一般情况下，我们会认为内存正比于顶点的数量，空间复杂度也就是O|v|。

对于边列表，存储字符串同样是一个很大的开销。

所以我们可以存储顶点的引用或者指针。

或者一个更好的方式就是直接使用顶点在列表的索引位置。

这样起始和终止将会是整型。

1
struct Edge{
2
  int startvsrtex;
3
  int endvertex;
4
    int weight;
5
}
6
或者
7
class Edge{
8
  int startvsrtex;
9
  int endvertex;
10
    int weight;
11
}
12
string vertex_list[MAX_SIZE];
13
Edge edge_list[Max_size];

这样存储的话，边列表的空间复杂度就是O（|E|）。E为边的数量。

总的空间复杂度就为O（|v|+|E|)

四、时间复杂度#

在操作一个图的时候，最频繁的操作是找到一个给定节点所有的直连节点。

对于有向图来说，我们要扫描边列表来查看起始节点是否为给定节点的相邻节点。

对于无向图来说，我们要同时看起始和终止的节点。

运行时间将会正比于边的数量。也就是O（|E|）。

另外一个操作是判断两个给定的节点是否相连。

我们需要在边列表进行线性查找，最坏的情况下我们需要查看边列表中所有条目，空间复杂度是O(|E|)

如果顶点的数量是n，那么在无向图里边数量的范围是0——n（n-1），有向图是n(n-1)/2。

所以可以看成边的数量是顶点数的平方。

总的来说，采用边列表的方式来实现图并不高效。