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

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

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

#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的数组并将其填充？这是正确的方法还是还有其他方法？我想知道执行此操作的正常方法和正确方法。

感谢您的阅读。

最佳答案

我认为最简单的方法是：


将每个节点（例如，由字符串表示）映射为整数
将此映射存储在表示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中删除