Home > OS >  Algorithm of a complement graph using adjacency matrix
Algorithm of a complement graph using adjacency matrix

Time:09-23

How to implement a complement graph which is given with adjacency matrix (literally any graph)?

I am wondering how to make a code of that graph, but I am not sure how to complete it.

I usually use pseudocode for these "early" implementations. This is what I have come up so far, it is just the beginning of the code. I know how to draw the complement graph, I know it's definitions, but I struggle with finishing it with the code.

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

CodePudding user response:

Your question is to find the complement of a graph. Its solution depends on the representation of graph used. In the question you have mentioned that adjacency matrix will be used to represent the graph.

Pseudocode


Here is a function which takes a graph as input and outputs the complement graph. Both the graph are represented using adjacency matrix.

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        

  • Related