c - 在用邻接矩阵表示的图中插入元素

Question

我正在学习 C 中的图数据结构，并且我已经用邻接矩阵表示了一个图。到目前为止，我创建了邻接矩阵，这意味着(至少在我的理解中)我已经指定了“哪些顶点之间将有边”，尽管我还没有创建任何实际的节点。现在，完成此操作后，我想用包含我自己的数据类型的节点实际填充我的图表(例如包含一些元素的结构中的每个节点)。我在谷歌上搜索了很多，但我发现的只是有关如何创建邻接矩阵的示例，但解释将就此停止，而不会显示您实际上如何在图中插入新元素。

我已经编写了填充邻接矩阵的代码。我提供了以下代码:

#include<stdio.h>
#define V 5

void init(int arr[][V])
{
  int i,j;
  for(i = 0; i < V; i++)
  for(j = 0; j < V; j++)
   arr[i][j] = 0;
}

void addEdge(int arr[][V],int src, int dest)
{
  arr[src][dest] = 1;
}

void printAdjMatrix(int arr[][V])
{
     int i, j;

     for(i = 0; i < V; i++)
     {
         for(j = 0; j < V; j++)
         {
           printf("%d ", arr[i][j]);
         }
     printf("\n");
 }
}

int main()
{
  int adjMatrix[V][V];

  init(adjMatrix);
  addEdge(adjMatrix,0,1);
  addEdge(adjMatrix,0,2);
  addEdge(adjMatrix,0,3);
  addEdge(adjMatrix,1,3);
  addEdge(adjMatrix,1,4);
  addEdge(adjMatrix,2,3);
  addEdge(adjMatrix,3,4);

  printAdjMatrix(adjMatrix);

  return 0;
}

现在我的问题是:要使用新节点填充我的图表，我是否必须创建另一个大小为 noofnodes x noofnodes 的数组并填充它？这是正确的方法还是有其他方法？我想知道正常且被认为正确的方法是如何做到这一点的。

感谢您的阅读。

Answer 1

我认为最简单的实现方法如下:

• 将每个节点(例如由字符串表示)映射到一个整数
• 将此映射存储在表示 Graph 对象的类中
• 不存储整数数组，而是存储 std::vector<std::vector<int>>

现在，当您添加某些内容时，过程变得非常简单:

• 将新节点添加到映射中，其对应的整数为邻接矩阵的大小std::vector<std::vector<int>>
• 添加新的 std::vector<int>到邻接矩阵，用零填充

更新邻接矩阵很容易:

public void setAdjMat(const std::string& n0, const std::string& n1, int c){
    int i0 = nodeMap[n0];
    int i1 = nodeMap[n1];
    adjecencyMatrix[i0][i1] = c;
}

优点:

• 添加只需很少的努力，并且不需要重组整个邻接矩阵
• 删除可以通过两种方式实现；从 nodeMap 中删除和/或从 adjecencyMatrix 中删除