[자료구조] 그래프(Graph)

https://bennettgarner.medium.com/what-the-graph-a-beginners-simple-intro-to-graphs-in-computer-science-3808d542a0e5

그래프(Graph)

    - 여러 개의 점들이 서로 선으로 복잡하게 연결되어 있는 관계를 표현한 자료구조

    - 하나의 점을 정점(vertex), 하나의 선을 간선(edge)라고 함

    - 두 점끼리 직접적인 관계가 있는 경우 점 사이를 이어주는 간선이 존재하며, 두 정점은 인접하다고 표현함

    - 간접적인 관계를 가진 두 점은 몇 개의 점과 선에 걸쳐서 이어짐

 

그래프의 표현 방식

    - 인접 행렬

        두 점간 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)로 표시한 2차원 배열 형태의 행렬로 표현

        두 정점 사이에 관계가 있는지 확인하거나, 가장 빠른 경로를 찾고자 할 때 사용

    - 인접 리스트

        각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현

        인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에, 메모리를 효율적으로 사용하고 싶을 때 인접 리스트 사용

 

기타 그래프 용어들

    - 인접 정점(adjacent vertex) : 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점

    - 가중치 그래프(weighted graph) : 연결의 강도(정점 간 추가적인 정보: 거리 등)가 얼마나 되는지 적혀져 있는 그래프

    - 비가중치 그래프(unweighted graph) : 연결의 강도가 적혀져 있지 않는 그래프

    - 무(방)향 그래프(undirected graph) : 간선의 방향이 적혀져 있지 않는 그래프

    - 진입차수(in-degree) / 진출차수(out-degree) : 한 정점에 진입(들어오는 간선)/진출(나가는 간선)하는 간선의 개수

    - 자기 루프(self loop) : 정점에서 진출하는 간선이 다른 정점을 거치지 않고 곧바로 자기 자신에게 진입하는 경우

    - 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있는 경우