使用邻接矩阵的补图算法

Question

如何实现用邻接矩阵给出的补图（字面意思是任何图）？

我想知道如何制作该图的代码，但我不确定如何完成它。

我通常对这些“早期”实现使用伪代码。这是我到目前为止所提出的， 这只是代码的开始。我知道如何绘制补图，我知道它的定义，但我很难用代码完成它。

Complement (G,s)
int Arr[1...size(V)]
queue Q
  for i=1 to size(V)
    Arr[i]=0

Answer 1

您的问题是找到图的补集。它的解决方案取决于所使用的图形表示。在您提到的问题中，邻接矩阵 将用于表示图形。

伪代码

---

这是一个函数，它将 graph 作为 input 和 outputs 补图。两个图都使用邻接矩阵表示。

G = Graph
G.V = graph vertices
CG = complement graph   

Complement(G)
       
1: for i = 0 to G.V
2:     for j = 0 to G.V
3:         if i == j: continue
4:         if G[i][j] = 0: CG[i][j] = 1             
5:         else CG[i][j] = 0   
6:           
7: return CG        

---