graph - 给定节点连接创建邻接矩阵

Question

我想在给定 n 行的情况下创建一个邻接矩阵，这些行表示图的某些节点之间的部分连接。例如，由于每条线代表一个集团，这些线A-B; B-C; C-D; A-E-D形成下图。

我的第一种方法是使用 afor 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)