그래프

그래프

정의

• 그래프: 정점과 간선으로 이루어진 자료구조
• 차수(degree): 각 정점에 대해서 간선으로 연결된 이웃한 정점의 개수
• 무방향 그래프(Undirected Graph): 간선의 방향이 없는 그래프
• 방향 그래프(Directed Graph): 간선의 방향이 있는 그래프
• 순환 그래프(Cyclic Graph): 순환을 가지고 있는 경우
• 비순환 그래프(Acyclic Graph): 순환이 없는 경우
• 완전 그래프(Complete Graph): 모든 서로 다른 두 정점 쌍이 간선으로 연결된 그래프
• 연결 그래프(Connected Graph): 임의의 두 정점 사이에 경로가 항상 존재하는 그래프
• 단순 그래프(Simple Graph): 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프

  표현법

  인접 행렬

• 그래프의 연결 관계를 이차원 배열로 나타냄
• 연결된 두 정점에는 1 연결되지 않으면 0
• g[i][j]: 노드 i에서 노드 j로 가는 간선이 있으면 1 없으면 0
• 장점: 정점이 V개이고 간선이 E개일 때, 어떤 두 점이 연결되어 있는지를 O(1)에 알 수 있음
• O(V^2)의 공간을 필요로 함
• 어떤 점에 연결되어 있는 모든 정점을 알고 싶을때에도 시간복잡도는 O(V)
• 코드

  #include<iostream>
  using namespace std;
  int g[10][10];
  void init(){
    for(int i=0;i<10;i++){
        for(int j=0;j<10;j++){
            g[i][j]=0;
        }
    }
  }
  void showgraph(int N){
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cout<<g[i][j];
        }
        cout<<'\n';
    }
  }
  int main(void){
    int V,E;
    cin>>V>>E;
    // 방향 그래프
    for(int i=0;i<E;i++){
        int f,s;
        cin>>f>>s;
        g[f][s]=1;
    }
    showgraph(V);
    init();
    // 무방향 그래프
    for(int i=0;i<E;i++){
        int f,s;
        cin>>f>>s;
        g[f][s]=1;
        g[s][f]=1;
    }
    showgraph(V);
    return 0;
  }
  

  인접 리스트

• 인접 행렬과 비교했을 때 정점이 많고 간선이 상대적으로 적은 상황에서 공간 절약 가능
• V개 리스트를 만들어 각 리스트에 자신과 연결된 정점을 저장
• 필요한 공간: O(V+E)
• 코드

  #include<iostream>
  #include<vector>
  using namespace std;
  vector<int> g[10];
  void init(){
    for(int i=0;i<10;i++){
        g[i].clear();
    }
  }
  void showgraph(int N){
    for(int i=1;i<=N;i++){
        for(int j=0;j<(int)g[i].size();j++){
            cout<<i<<' '<<g[i][j]<<'\n';
        }
    }
  }
  int main(void){
    int V,E;
    cin>>V>>E;
    // 방향 그래프
    for(int i=0;i<E;i++){
        int f,s;
        cin>>f>>s;
        g[f].push_back(s);
    }
    showgraph(V);
    init();
    // 무방향 그래프
    for(int i=0;i<E;i++){
        int f,s;
        cin>>f>>s;
        g[f].push_back(s);
        g[s].push_back(f);
    }
    showgraph(V);
    return 0;
  }
  

• Tip(STL을 사용하지 못하는 경우/방향 그래프)

  //방향 그래프
  #include<iostream>
  using namespace std;
  int edge[10][2];
  int deg[10]; // 각 정점의 outdegree
  int* adj[10];
  int idx[10]; // adj[i]에서 새로운 정점을 추가할 때의 위치
  int main(void){
    int v,e;
    cin>>v>>e;
    for(int i=0;i<e;i++){
        cin>>edge[i][0]>>edge[i][1];
        deg[edge[i][1]]++;
    }
    for(int i=1;i<=v;i++){
        adj[i]=new int[deg[i]];
    }
    for(int i=0;i<e;i++){
        int f=edge[i][0];
        int s=edge[i][1];
        adj[f][idx[f]]=s;
        idx[f]++;
    }
    return 0;
  }
  

• Tip(STL을 사용하지 못하는 경우/무방향 그래프)

  //무방향 그래프
  #include<iostream>
  using namespace std;
  int edge[10][2];
  int deg[10]; // 각 정점의 outdegree
  int* adj[10];
  int idx[10]; // adj[i]에서 새로운 정점을 추가할 때의 위치
  int main(void){
    int v,e;
    cin>>v>>e;
    for(int i=0;i<e;i++){
        cin>>edge[i][0]>>edge[i][1];
        deg[edge[i][0]]++;
        deg[edge[i][1]]++;
    }
    for(int i=1;i<=v;i++){
        adj[i]=new int[deg[i]];
    }
    for(int i=0;i<e;i++){
        int f=edge[i][0];
        int s=edge[i][1];
        adj[f][idx[f]]=s;
        idx[f]++;
        adj[s][idx[s]]=f;
        idx[s]++;
    }
    return 0;
  }
  

  비교

  ||인접 행렬|인접 리스트|
  |—|—|—|
  |공간 복잡도|O(V^2)|O(V+E)|
  |정점 u,v가 연결되어 있는지 확인하는 시간 복잡도|O(1)|O(min(deg(u),deg(v))|
  |정점 v와 연결된 모든 정점을 확인하는 시간 복잡도|O(V)|O(deg(v))|
  |효율적인 상황|두 점의 연결여부를 자주 확인할 때 E가 V^2에 가까울 때|특정 정점에 연결된 모든 정점을 자주 확인할 때 E가 V^2보다 훨씬 작을 때|