Incidence Matrix를 사용하여 그래프를 표현하는 C++ 프로그램

그래프의 입사 행렬은 메모리에 저장할 그래프의 또 다른 표현입니다. 이 행렬은 정방 행렬이 아닙니다. 입사 행렬의 순서는 V x E입니다. 여기서 V는 정점의 수이고 E는 그래프의 가장자리 수입니다.

이 행렬의 각 행에 정점을 배치하고 각 열에 모서리를 배치합니다. 에지 e {u, v}에 대한 이 표현에서는 e열의 u 및 v 위치에 대해 1로 표시됩니다.

인접 행렬 표현의 복잡성

• 입사 행렬 표현은 계산되는 동안 O(Vx E)의 공간을 차지합니다. 완전한 그래프의 경우 모서리 수는 V(V-1)/2입니다. 따라서 입사 행렬은 메모리에서 더 많은 공간을 차지합니다.

입력

출력

알고리즘

add_edge(u, v)

입력 − 에지의 u 및 v {u,v}

출력 − 그래프 G

처음에는 에지 카운트가 있습니다. ed_cnt는 입사 행렬에 대해 0입니다.

Begin
   ed_cnt := ed_cnt + 1
   inc_matrix[u, ed_cnt] := 1
   inc_matrix[v, ed_cnt] := 1
End

예시 코드(C++)

#include<iostream>
using namespace std;
int inc_arr[20][20]; //initial array to hold incidence matrix
int ed_no = 0;
void displayMatrix(int v, int e) {
   int i, j;
   for(i = 0; i < v; i++) {
      for(j = 0; j < e; j++) {
         cout << inc_arr[i][j] << " ";
      }
      cout << endl;
   }
}
void add_edge(int u, int v) { //function to add edge into the matrix with edge number
   inc_arr[u][ed_no] = 1;
   inc_arr[v][ed_no] = 1;
   ed_no++; //increase the edge number
}
main(int argc, char* argv[]) {
   int v = 6; //there are 6 vertices in the graph
   int e = 9; //there are 9 edges in the graph
   add_edge(0, 4);
   add_edge(0, 3);
   add_edge(1, 2);
   add_edge(1, 4);
   add_edge(1, 5);
   add_edge(2, 3);
   add_edge(2, 5);
   add_edge(5, 3);
   add_edge(5, 4);
   displayMatrix(v, e);
}

출력

1 1 0 0 0 0 0 0 0
0 0 1 1 1 0 0 0 0
0 0 1 0 0 1 1 0 0
0 1 0 0 0 1 0 1 0
1 0 0 1 0 0 0 0 1
0 0 0 0 1 0 1 1 1