c++ - 计算无向图中的度数 - 逻辑问题

Question

我有关联矩阵，并基于它计算图中每个顶点的度数。

让我们假设这是当前的关联矩阵:

-1 -1  1  0  1  0
 1  0 -1 -1  0  1
 0  1  0  1 -1 -1

行是顶点，列是边。 -1 表示边从顶点出来，+1 表示它进来。

如果这是无向图，矩阵包含一些特定的模式，如下所示:

-1  0  1  0  0  0
 1  0 -1  0  0  0
 0  0  0  0  0  0

两行 - 相同的顶点。两条边，方向不同。这是代表:

但是这样写的:

---

在有向图中计算顶点的度数(与它相连的任何边)我只是在每一行中计算 -1 和 +1。那行得通。

问题是——在无向图中度数到处都乘以 2，因为矩阵自然地将线边“转换”为两个箭头边，如图所示。

问题是 -如果边是随机放置的，我怎样才能减少度数，以便它使用关联矩阵计算一条线边而不是两条箭头边？

---

澄清一下，这个算法不能正常工作我想要的:

for(int i = 0; i < cols; i++)
{
   int deg = 0;
   for(int j = 0; j < rows; j++)
   {
      if(matrix[i][j] != 0) deg++;
   }
   std::cout << "Degree of " << i + 1 << " vertex is " << deg;
}

如何更改 if 指令以减少重复的倒排列？

Answer 1

你所说的 incidence matrix真的不是。这是一个边缘列表。边列表存在您所看到的问题:重复、每个无向边的双重表示等。它们几乎从来都不是图形数据结构的最佳选择。

在关联矩阵中，行和列都是顶点。第 i 行第 i 列中的 1(或标签值，如果边被标记)表示从 i 到 j 有一条边。零(或其他表示“无”的值)表示没有边。

如果图是无向的，则矩阵是对称的:从 i 到 j 的边总是与从 j 到 i 的匹配。因此，您可以在不丢失信息的情况下删除矩阵的上三角或下三角。

一旦顶点被编号，关联矩阵就是唯一的。重复是不可能发生的。如果边缘未标记，则可以将其存储在位图中。

计算有向图的入度只是计算顶点列中的 1。出度是在行中计数 1。如果图是无向的，用三角形数组表示，同样的过程也能正常工作。不需要除以 2。

关联矩阵的主要缺点是它需要 O(n^2) 空间来存储每个 n 顶点的图，无论它有多少条边。如果图是“稀疏的”，即它只有 O(n) 条边，这可能是个问题。在这种情况下，首选数据结构是 adjacency list ，我会让您自己阅读。