[알고리즘 기초]. 그래프를 표현하는 여러 방법 - 인접 행렬 / 인접 리스트

💡 인접 행렬(adjaency matrix)

그래프를 표현하기 위해서는 첫번째 표현방법인 인접 행렬 방법이 있다.
인접 행렬은 bool타입의 정사각행렬이다.

bool a[from][to] : 인접 행렬 이라는 의미를 부여하였다.

#include <iostream>
#include <algorithm>
using namespace std;
const int V = 10;
bool a[V][V], visited[V]; //visited는 V개의 노드를 방문했는지 안했는지 체크하는 배열
void go(int from) {
  visited[from] = 1;
  cout << from << '\n';
  for(int i = 0; i < V; i++) {
    if(visited[i]) continue; //이미 방문했다면
    if(a[from][i]) { //연결된 다른 노드가 있다면
      go(i); //다시 go함수 재귀호출
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  a[1][2] = 1, a[2][1] = 1;
  a[1][3] = 1, a[3][1] = 1;
  a[3][4] = 1, a[4][3] = 1;

  for(int i = 0; i < V; i++) {
    for(int j = 0; j < V; j++) { //그래프 탐색
      if(a[i][j] && visited[i] == 0)
        go(i);
    }
  }
}

💡 인접 리스트(adjaency list)

인접 리스트란 각 정점마다 연결리스트를 생성하는 방법이다.

vector< int > adj[V];

#include <iostream>
#include <vector>
using namespace std;
const int V = 10;
vector<int> adj[V];
bool visited[V];
void go(int idx){
  visited[idx] = 1;
  cout << idx << "\n";
  for(int there : adj[idx]) {
    if(visited[there]) continue;
    go(there);
  }
}
int main() {
  adj[1].push_back(2); adj[2].push_back(1);
  adj[3].push_back(1); adj[1].push_back(3);
  adj[3].push_back(4); adj[4].push_back(3);
  for(int i = 0; i < V; i++) {
    if(adj[i].size() && visited[i] == 0) go(i);
  }
}