图(Graph)的表示

图(Graph)

图，是一种记录节点和节点之间关连的表示法。对於图，表示是由集合和集合共同构成的集合，集合中的元素为图中的节点，故又称点集合。表示节点和节点之间的边所构成的集合，每一个边可以当作纯量或是向量，故又称为边集合。

图，可以用两种方式是表示，一种方法类似前面Hash table中Chaining的表示法，每一个slot中含有一个链结串列，这个方法称为邻接串列(Adjacency list)表示，另一种方法为使用邻接矩阵(Adjacency Matrix)来表示。

而节点和节点之间，我们可以根据其走访的性质，定义他是有向图(Directed)，还是无向图(Undirected)，也就是节点和节点之间的边，是以线段来表示，还是以向量来表示。

对於图，使用邻接串列表示法包含有条串列的阵列所构成，阵列中每一个元素中有一条串列。对於每一个属於集合的节点，包含所有与节点有边相连的节点，或是可以称为的邻居，而邻接矩阵也是使用差不多的概念，给定一个无向图，我们可以以下面两种方式进行表示

在图(a)中，我们可以知道点集合为, 边集合，如果在实务上，我们直接使用集合来寻找和1节点有关连的所有节点，我们就必须遍历整个集合，需要线性时间，因此我们会使用上面提及的邻接串列法或是邻接矩阵法来进行处理。

我们可以对邻接串列表示法做出一点修改，为每一条边加上权重，那麽，所产生出的图就是权重图。我们可以将权重储存在链结串列中的每一个节点当中，当作是一个节点的属性。而这种表示法具有一些可靠性与安全性在一些系统应用中，像是输入错误或是系统崩溃等等，也具有一定的方便修改性，可以进行一些简单的修改就让他支援其他图的形式与操作。

邻接串链有几个缺点，那就是我们无法快速的判断一条边是否为图中的边，且和邻接矩阵相比，每一个节点需要更多的储存空间，包含一个整数，和下一个节点位置的指标。

而邻接矩阵的优点在於矩阵中每一个元素都只需要1 bit就可以表示，只需奥表示有没有节点就可以了，但是也有一个缺点，当发生很多元素，但却很少边的情况，会浪费掉许多空间。

当图的规模较小时，我们会优先使用邻接矩阵。

图的表示

上图A,B,C等节点，我们会称为图的节点或是顶点(Vertex or Node)，节点与节点之间相连的称为边，这个范例中，边是属於没有方向的，因此，这是一张无向图。边上的数字表示权重。

上面这张图，如果以邻接矩阵的方式表示，可以表示成下面这个样子

int map[5][5]=
{ {0,0,1,1,1}
  {0,0,0,0,1}
  {1,0,0,0,1}
  {1,0,0,0,0}
  {1,1,1,0,0}
};

说明: 以第一行{0,0,1,1,1}为例子，表示0这个节点，和2,3,4节点有存在边的关系。其实我们可以指细观察，上面这个二为矩阵其实存在一种对称关系，以方阵的对角线为对称轴，这个性质可以使我们使用一些技巧，花费更少的空间，去记住节点和边之间的关系。

以这个图为例子，我们可以使用邻接矩阵，来表示这个具有权重的图

int map[5][5] =
{ {0,1,6,INT_MAX,INT_MAX}
  {1,0,4,3,1}
  {6,4,0,1,INT_MAX}
  {INT_MAX,3,1,0,1}
  {INT_MAX,1,INT_MAX,1,0}
};

说明: 以第一行{0,1,6,INT_MAX,INT_MAX}为例，表示0这个节点和其他节点之间的权重，如果不存在，则以一个标示符号作为表示。

如果以串列的形式，则为以下

struct edge {
    int id;
    int weight;
    struct node *next;
};
struct map[5]

参考资料:Introduction to algorithms 3rd, 北一女资讯集训