Создать матрицу смежности для заданных соединений узлов

Question

Я хочу создать матрицу смежности с n строками, представляющими частичную связь между некоторыми узлами графа. Например, из-за того, что каждая строка представляет клику, строки A-B; B-C; C-D; A-E-D сформировать следующий график.

Мой первый подход был с использованием for loop читать каждую строку, для каждой строки я использую другую for loop получить каждый узел в нем, наконец, с другим for loop Я проверяю, находятся ли остальные узлы в списке adyacence анализируемого узла, если нет, я добавляю его. Все это дает O(n^3) сложность. Есть ли другой способ сделать эту задачу с меньшей сложностью? Возможно ли завершить это с помощью O(n)?

Answer 1

В псевдокоде вы можете сделать что-то вроде этого:

A[n,n] <- {0 ... 0n}    // Dense matrix size n x n , initalized to zero.

for L in LINES:          // Loop through input lines
  {N,adj}=Split(L)       // Split Node and adjecencies
  I=IDNameToIndex(N)  // Numeric index corresponding to Node name or id.
  for n in adj:          // Loop through adjecencies 
     i=IDNameToIndex(n)  // Numeric index corresponding to Node name or id.
     A[I,i]=1;           // Set unidrectional adjecency 
     A[i,I]=1;           // Set bidirectional adjecency(optional, depending on input)