Вставка элемента в граф, представленный с помощью матрицы смежности

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;
}

Преимущества:

• Добавление требует очень мало усилий и не требует реструктуризации всей матрицы приличия