algorithmgraphgraph-algorithmpseudocodecomplement

Algorithm of a complement graph using adjacency matrix


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


Solution

  • 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