图算法

---

---

图是一种抽象的表示方法，用于表示对象对之间的连接。一个图由：

• 顶点 - 图中相互连接的对象称为顶点。顶点也称为节点。

• 边 - 边是连接顶点的链接。

图有两种类型：

• 有向图 - 在有向图中，边具有方向，即边从一个顶点指向另一个顶点。

• 无向图 - 在无向图中，边没有方向。

图着色

图着色是一种为图的顶点分配颜色，使得任何两个相邻顶点不具有相同颜色的方法。一些图着色问题包括：

• 顶点着色 - 一种为图的顶点着色，使得任何两个相邻顶点不共享相同颜色的方法。

• 边着色 - 这是一种为每条边分配颜色，使得任何两条相邻边不具有相同颜色的方法。

• 面着色 - 它为平面图的每个面或区域分配一种颜色，使得任何两个共享公共边界的面对不具有相同颜色。

色数

色数是为图着色所需的最少颜色数。例如，下图的色数为 3。

图着色的概念应用于制作时间表、移动无线电频率分配、数独、寄存器分配和地图着色。

图着色步骤

• 将n维数组中每个处理器的初始值设置为1。

• 现在，要为顶点分配特定颜色，请确定该颜色是否已分配给相邻顶点。

• 如果处理器检测到相邻顶点具有相同颜色，则它将其在数组中的值设置为0。

• 进行n²次比较后，如果数组的任何元素为1，则这是一个有效的着色。

图着色的伪代码

begin

   create the processors P(i0,i1,...in-1) where 0_iv < m, 0 _ v < n
   status[i0,..in-1] = 1
	
   for j varies from 0 to n-1 do
      begin
		
         for k varies from 0 to n-1 do
         begin
            if aj,k=1 and ij=ikthen
            status[i0,..in-1] =0
         end
			
      end
      ok = ΣStatus
		
   if ok > 0, then display valid coloring exists
   else
      display invalid coloring
      
end

最小生成树

其所有边的权重（或长度）之和小于图G所有其他可能生成树的生成树称为最小生成树或最小成本生成树。下图显示了一个加权连通图。

上图的一些可能的生成树如下所示：

在所有上述生成树中，图(d)是最小生成树。最小成本生成树的概念应用于旅行商问题、电子电路设计、高效网络设计和高效路由算法设计。

为了实现最小成本生成树，使用以下两种方法：

• Prim 算法
• Kruskal 算法

Prim 算法

Prim 算法是一种贪心算法，它帮助我们找到加权无向图的最小生成树。它首先选择一个顶点，然后找到与该顶点关联的具有最低权重的边。

Prim 算法的步骤

• 选择图G的任何顶点，例如v₁。

• 选择图G的一条边，例如e₁，使得e₁ = v₁v₂，且v₁ ≠ v₂，并且e₁在图G中与v₁关联的边中具有最小权重。

• 现在，按照步骤2，选择与v₂关联的最小权重边。

• 继续此步骤，直到选择了n-1条边。这里n是顶点数。

最小生成树是：

Kruskal 算法

Kruskal 算法是一种贪心算法，它帮助我们找到连通加权图的最小生成树，在每个步骤中添加成本递增的弧。这是一种最小生成树算法，它找到连接森林中任何两个树的最小可能权重的边。

Kruskal 算法的步骤

• 选择最小权重的边；例如图G中的e₁，且e₁不是环。

• 选择连接到e₁的下一个最小权重的边。

• 继续此步骤，直到选择了n-1条边。这里n是顶点数。

上图的最小生成树是：

最短路径算法

最短路径算法是一种查找从源节点(S)到目标节点(D)的最低成本路径的方法。在这里，我们将讨论 Moore 算法，也称为广度优先搜索算法。

Moore 算法

• 标记源顶点S，并将其标记为i，并设置i=0。

• 查找与标记为i的顶点相邻的所有未标记顶点。如果没有任何顶点连接到顶点S，则顶点D未连接到S。如果有顶点连接到S，则将其标记为i+1。

• 如果D已标记，则转到步骤4，否则转到步骤2以增加i=i+1。

• 找到最短路径的长度后停止。