【Day19】[资料结构]-图Graph

图(Graph)，并非多数人直接联想到形状或图片，在计算机科学或离散数学中的图，是由数个顶点Vertex(或称节点Node)及数条边(Edge)所构成，顶点与顶点之间用边连接，用来表示两点的关联与关系。

一个图可以用G=( V, E )来定义

• G： 图形(Graph)
• V： 所有顶点(Vertice)的集合
• E： 所有边(Edges)的集合

同构(Isomorphism)

同构是指若两个以上的图，它们顶点与顶点之间的关联是一致的，就是同构的图。

上方图，无论直线或曲线，只要顶点间的关联一样，就属於同构图。

上方图，顶点位置被任意移动，只要顶点间的关联一样，就属於同构图。

有向图(Directed Graph)

具有方向性的边，表示某个边是单向的。

无向图(Undirected Graph)

不具有方向性的边，表示某个边是双向的。

加权图(Weighted Graph)

边上附有数值称为边的「加权」或 「权重」，可以表示出相联的两顶点的连接程度，常见的权值应用有: 成本、距离、时间……等。
可以想像台北捷运图，各站即为顶点，站与站之间的路线就是边，各站间会有票价权重;Google地图，两景点间路径计算，会有距离的权重;社交软件的关系链中，谁与谁的共同好友数可以为权重，又或是各服务器间通讯的时间。

图的术语

• 路径(Path)：两顶点经过的边。如上图:1到6，可以从1到4再到6，可以说(1,4,6)为其路径。
• 路径长度(Path Length)：两顶点路径上包含边的个数。如上图:1到6，路径为 {(1,4), (4,6)}，经过２条边。
• 简单路径(Simple Path)：路径上除了起点与终点可以相同外，其余顶点不能被重复经过。如上图:
  1 4 6为简单路径，顶点都未重复。
  1 4 3 2 1为简单路径，1为起终点，其余顶点都未重复。
  2 3 4 1 3 2不为简单路径，其中的顶点3出现2次。
• 循环(Cycle)：属於简单路径，且路径的起点与终点相同能构成循环。如上图:3 2 1 4 3，起点与终点都是3。
• 相邻(Adjacent)：兩个顶点间有一条边相连(不论是否具有方向性)，则这兩个顶点为相邻。如上图:3与1 2 4相邻。
• 分支度(Degree)：

  • 无向图中: 一个顶点含有几条边，如下图:B的分支度为2。
    

  • 有向图中: 入分支度与出分支度的总和，如下图B的分支度为3。

    • 入分支度(In-Degree)： 箭头指入此顶点的边数，如下图B的入分支度为2。
    • 出分支度(Out-Degree)： 箭头由此顶点指出的边数，如下图B的出分支度为1。
      
• 完整图(Complete Graph)：
  • 无向图中: n 个顶点，会有n(n-1) ÷ 2条边，如下图: 4个顶点，6条边。
    
  • 有向图中: n 个顶点，会有n(n-1)条边，如下图: 4个顶点，12条边。
    
• 子图(Subgraph)：如下图:乙图与丙图的顶点被包含在甲图的顶点集合中，且乙图与丙图的边也被包含在甲图的边集合中，则可以说乙与丙是甲的子图。
  

常见图的表示法

相邻矩阵 (Adjacency Matrix)

一个包含N个顶点的图，可以使用 N 乘 N 的二维阵列来表示，两个顶点间，若有边值为1；若没有边值为0。

• 无向图中:
  

矩阵会是对称的，如上图G[2][3] = G[3][2] = 1，只需保存上三角或下三角部份即可，n(n-1)/2的记忆体空间。
分支度: 该顶点在矩阵中列的总和，如上图：顶点2的分支度 = 1 + 0 + 1 + 0 = 2

• 有向图中:
  

矩阵不一定会是对称的，如上图G[1][3]=1，G[3][1]=0。
分支度: 该顶点入分支度与出分支度的总和。
出分支度： 第i列的总和，如上图的顶点3，出分支度为第3列的总和为 0。
入分支度： 第i行的总和，如上图的顶点3，入分支度为第3行的总和 1 + 1 + 0 = 2

相邻串列 (Adjacency List)

每个顶点使用单向链结串列來串接相邻的顶点，只处理有边的部分，没有边的部分不处理，有N个顶点，需准备N个串列，再用指标指向相邻顶点。

• 无向图中:
  

若有n个顶点，e条边，则需要n 个首节点与 2乘e 个子节点，如上图有4个顶点，与4条边，则需要4个首节点与8个子节点。
分支度: 该顶点串列子节点的总数，如上图:顶点1的串列，除了首节点之外，有3个子节点，分支度为 3

• 有向图中:
  

若有n个顶点，e条边，则需要n 个首节点与 e 个子节点，如上图有3个顶点，与4条边，则需要3个首节点与4个子节点。
出分支度： 该顶点串列子节点的总数，如上图:顶点1的串列，除了首节点之外，有2个子节点，出分支度为 2。
入分支度： 比较复杂，需要寻找其他顶点串列的子节点，是否出现该顶点，再加总。

相邻矩阵在路经很少的情况下容易浪费空间，但求分支度就非常方便，而相邻串列法比较节省空间，但求分支度时比较麻烦。