[자료구조] 그래프(Graph)란? +(인접 리스트vs인접행렬)

🚦 이번 포스팅에서는 〰️

▶️ 그래프(Graph)란?
▶️ 그래프(Graph) 의 종류
▶️ 그래프(Graph) 의 두가지 연산함수-Graph Traversal
▶️ 그래프(Graph) 구현 방법
▶️ 인접 행렬 vs 인접 리스트
▶️ 트리(Tree) vs 그래프(Graph)

 

 

📎 그래프(Graph)이란?

---

: 노드(node), 또는 버텍스(vertex)와 에지(edge)로 구성되었으며, 어떤 자료들간의 관계(relation)을 설명하는 매우 일반적인 자료구조이다.

그래프를 탐색하는 2가지 알고리즘인 DFS(Depth First Search)와 BFS(Breadth First Search)가 유명하다.

대부분의 그래프 관련 알고리즘은 이 두 알고리즘을 바탕으로 확장된 것이다.

 

그래프가 중요한 이유?

가장 일반적인 위상 구조이기 때문이다.

즉, 어떤 자료구조도 이 그래프 구조를 응용(확장/축소)하여 표현할 수 있는 만능자료구조라고 할 수 있다.

 

 

📌 그래프의 특징

• 네트워크 모델이다.
• 2개 이상의 경로가 가능하다=무방향/양방향 경로를 가질 수 있다.
• self-loop뿐 아니라 loop, circuit 모두 가능하다.
• 루트 노드, 부모-자식 관계 개념이 없다.
• 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
• 그래프는 크게 방향그래프(Directed)와 무방향그래프(Undirected)가 있다.
• 간선의 유무는 그래프의 종류에 따라 다르다.

 

 

📎 그래프(Graph)의 종류

---

1. 무방향 그래프 vs 방향 그래프
   • 무방향 그래프 (Undirected Graph)
     : 간선을 통해서 양방향으로 갈 수 있는 그래프
     정점 A와 정점 B를 연결하는 간선 (A,B), (B,A)는 같다.
   • 방향 그래프 (Directed Graph)
     : 간선에 방향성이 존재하는 그래프
     A->B로만 갈 수 있는 간선은 <A,B>로 표시한다.
     <A,B>와 <B,A>는 다르다.
2. 가중치 그래프
   • 간선에 비용이나 가중치가 할당된 그래프, "네트워크(Network)"라고도 한다.
3. 연결 그래프 vs 비연결 그래프
   • 연결 그래프 (Connected Graph)
     : 무방향 그래프에 있는 모든 정점쌍에 대해 항상 경로가 존재하는 그래프
     ex) Tree : 사이클을 가지지않는 연결 그래프
   • 비연결 그래프 (Disconnected Graph)
     : 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우
4. 사이클 vs 비순환 그래프
   • 사이클 (Cyclic)
     : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
     단순경로? 경로 중에서 반복되는 정점이 없는 경우
   • 비순환 (Acyclic) : 사이클이 없는 그래프
5. 완전 그래프
   • 그래프에 속해 있는 모든 정점이 서로 연결되어있는 그래프
   • 무방향 완전 그래프
     정점수가 n개이면 간선의 수는 n*(n-1)/2

 

 

📌 Graph Traversal - DFS&BFS

1. 모든 노드를 완벽하게 방문 = 빠짐없이 방문, 중복없이 방문
2. Depth First Search(DFS)
   • 대응되는 자료구조 : Stack
   • 알고리즘
     : 갈 수 있으면 갈 수 있는 곳까지 한 방향으로 간다. (+방문 check) 더이상 갈 수 없다면 바로 이전상태로 되돌아간다.
3. Breadth First Search(BFS)
   • 대응되는 자료구조 : Queue
   • 알고리즘
     : 현재의 위치에서 이웃한 모든 노드를 동시에 방문한다. 이 작업을 반복한다.

--> DFS, BFS란?에서 상세히 설명 예정

 

 

📎 그래프(Graph) 구현 방법

---

STL : tree와 같이 더이상 제공해주지 않음

(componentware 기반으로 활용하려면 Boost 사용해야 함, python에서는 NetworkX를 제공함)

python에서 NetworkX를 활용한 그래프 구현은 시간되면 다루는걸로..

 

 

1. 인접 리스트 (Adjacent List)

• 각 정점에 인접한 정점들을 값으로 가진다.
• 즉, 정점의 개수만큼 인접리스트가 존재하며, 각각의 인접 리스트에는 인접한 정점 정보가 저장된다.
• 그래프는 각 인접리스트에 대한 헤드포인터를 배열로 갖는다.
• 무방향 그래프의 경우 반대편 간선도 저장되기 때문에 간선이 두번저장된다.

장점

• 존재하는 간선만 관리하면 되기 때문에 메모리 사용 측면에서 효율적이다.
• 그래프의 모든 간선의 수를 알아내려면 각 정점의 헤더 노드부터 모든 인접리스트를 탐색해야 하므로 O(n+e)시간 소요된다.

 

단점

• 두 정점을 연결하는 간선을 조회하거나 정점의 차수를 알기 위해서는 정점의 인접 리스트를 탐색해야 하기 때문에 정점의 차수만큼의 시간이 필요하다. O(degree(v))
• 구현이 비교적 어렵다.

 

 

 

2. 인접 행렬 (Adjacent Matrix)

: 그래프의 정점을 2차원 배열로 만든 것이다.

• 정점의 개수가 n개라면 n*n형태의 2차원 배열이 인접 행렬로 사용된다.
• 간선으로 연결된 정점의 인덱스에 1의 값을, 연결되지 않은 정점은 0이 저장된다.
• 인접 행렬에서 행과 열은 정점을 의미하며, 각각의 원소들은 정점 간의 간선을 나타낸다.
• 무방향 그래프는 두개의 정점에서 간선이 동시에 연결되어 있기 때문에 대칭적인 행렬 구조를 가진다.
• 가중치 그래프는 0과 1이 아닌 각 간선의 가중치 값이 행렬에 저장된다.

 

#include <deque>
#include <vector>
#include <unordered_set>
#include <unordered_map>
#include <iostream>
using namespace std ;

template<class Key>
class Graph {
  public:     // adds an undirected edge
    void addEdge(Key v1, Key v2) {
        Adj_.insert( {v1,v2} );
    }
    void printAdj();
    void BFS(Key v);     // Graph traversal functions
    void DFS(Key v);
  private:      // Adjacency list
   unordered_multimap<Key,Key> Adj_;
};

template<class Key> void Graph<Key>::printAdj() {
    auto it = Adj_.begin();
    while( it != Adj_.end() ) {
       cout << it->first << ": ";
        auto range = Adj_.equal_range(it->first);
        for ( auto local_it = range.first; local_it!= range.second; ++local_it ) {
           cout << local_it->second << " ";
            ++it;
        }
       cout << "\n";

    }
} // end of template<class>


//  BFS는 v부터 시작한다. 먼저 큐 Q를 만든다.
//  v를 방문한 경우에는 visited라고 mark하고 이것을 Q에 넣는다.
//  while Q is non-empty일때 까지
//  Q에서 head 원소 u를 꺼내서 이것을
//  mark하고 이웃한 unvisited neighbours of u를 모두 큐에 쳐 넣는다.


template<class Key> void Graph<Key>::BFS(Key v) {
   unordered_set<Key> visited;
   deque<Key> Q;
   Q.push_back(v);
   visited.insert(v);

    while(Q.size() > 0) { // while the queue is non-empty do
        v = Q.front();
        Q.pop_front();         // remove vertex at the front of the queue
       cout << v << " ";         // iterate over v's neighbors
        for(auto neighbor = Adj_.find(v); neighbor != Adj_.end(); ++neighbor) {
            // check if neighbor has been visited
            auto isthere = visited.find(neighbor->second);
            if(isthere == visited.end()) { // if neighbor has not been visited then
                visited.insert(neighbor->second);
                Q.push_back(neighbor->second); // add neighbor to back of the queue
            }
        }
    }
   cout << "\n";
} // end of BFS( )

// DFS starting from vertex v and create a stack S
// mark v as visited and push v onto S
//  while S is non-empty
//  peek at the top v of S
//  if v has an (unvisited) neighbor u, mark u and push it onto S  else pop S

template<class Key> void Graph<Key>::DFS(Key v) {
   unordered_set<Key> visited;   // set of visited vertices
   vector<Key> S;
   visited.insert(v);
   S.push_back(v);
   cout << v << " ";

    while(S.size() > 0) {         // peek the top v of the stack
        v = S.back();     // find the index of the first unvisited neighbor of v
        typename unordered_multimap<Key,Key>::iterator neighbor;
        for(neighbor = Adj_.find(v); neighbor != Adj_.end(); ++neighbor) {
            // check if neighbor has been visited
            auto isthere = visited.find( neighbor->second );
            if( isthere == visited.end() )
                break;
        }
        if(neighbor != Adj_.end() ) { // the case in which an unvisited neighbor is found
            visited.insert(neighbor->second); // mark the neighbor u as visited
            S.push_back(neighbor->second);  // push u onto the stack
           cout << neighbor->second << " ";
        } else {
            S.pop_back();
        }
    }
}  // end of DFS( )

int main() {
    Graph<std::string> myGraph;
    myGraph.addEdge("a","b");
    myGraph.addEdge("b","c");
    myGraph.addEdge("c","d");
    myGraph.addEdge("b","a");
    myGraph.addEdge("c","b");
    myGraph.addEdge("d","c");
    myGraph.addEdge("c","e");
    myGraph.addEdge("e","f");
    myGraph.addEdge("b","f");
    myGraph.addEdge("e","c");
    myGraph.addEdge("f","e");
    myGraph.addEdge("f","b");
    myGraph.addEdge("f","g");
    myGraph.addEdge("a","g");
    myGraph.addEdge("g","f");
    myGraph.addEdge("g","a");
   cout << "\n 인접리스트 :\n";      myGraph.printAdj();
   cout << "\n\n vertex a에서 시작하는 BFS 방문순서:\n";
    myGraph.BFS("a");
   cout << "\n\n vertex a에서 시작하는 DFS 방문순서:\n";
    myGraph.DFS("a");
}

 

📌 인접 리스트 vs 인접 행렬

	인접 리스트	인접 행렬
사용하는 경우	그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프 (Sparase Graph)의 경우	그래프에 간선이 많이 존재하는 밀집 그래프 (Dense Graph)의 경우
장점	- 메모리 관련에서 효율적 ▶️ 간선만 관리하기 때문 - 그래프 안의 모든 간선의 수 : O(n+e) ▶️ 각 정점의 헤더 노드부터 모든 인접 리스트 탐색 - 어떤 노드에 인접한 노드들을 쉽게 찾을 수 있다.	- 두 정점을 연결하는 간선을 조회할 때 : O(1) ▶️ 모든 정점들의 간선 정보를 가지고 있기 때문 - 정점의 차수를 구할 때 : O(n) ▶️ 인접행렬 M의 i번째 행의 값을 모두 더하면 된다.
단점	- 두 정점을 연결하는 간선 조회 or 정점의 차수    : 정점의 차수만큼 시간필요 ▶️ 정점의 인접 리스트를 탐색해야 하기 때문	- 메모리 공간이 낭비 ▶️ 간선 수와 무관하게 항상 n^2 크기의 2차원 배열이 필요 - 모든 간선의 수 : O(n^2) ▶️ 인접 행렬 전체를 확인해야 함

 

 

 

 

📌 트리(Tree) vs 그래프(Graph)

---

	그래프 (Graph)	트리 (Tree)
정의	노드(node)와 노드를 연결하는 간선(edge)을 하나로 모아놓은 자료구조	그래프의 한 종류
방향성	Directed, Undirected 둘다 존재	Directed만 존재
사이클	가능 자체간선(self-loop), 순환 그래프(cyclic), 비순환 그래프(Acyclic) 모두 존재	불가능 비순환 그래프(Acyclic)
루트 노드	루트 노드의 개념 X	한개의 루트 노드만 존재 모든 자식 노드는 한개의 부모 노드만 가짐
부모-자식	부모-자식 개념 X	top-down(하향식) 또는 botton-top(상향식) 으로 이루어짐
모델	네트워크 모델	계층 모델
순회	DFS, BFS	DFS, BFS 안의 Pre-order, In-order, Post-order
간선의 수	그래프에 따라 간선의 수가 다름 (없을 수도 있음)	노드가 N인 트리는 항상 N-1의 간선을 가짐
경로	X	임의의 두 노드 간의 경로는 유일
예시 및 종류	지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로, 선수 과목	이진 트리, 이진 탐색 트리, 균형트리(AVL 트리, red-black 트리), 이진 힙(최대 힙, 최소 힙) 등

 

 

 

 

🔆 [자료구조] 다른 Posting 보러 가기 🔆

✅ 스택(Stack)이란?

✅ 큐(Queue)란?

 

 

 

[참고]

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html