알고리즘

그래프(Graph)와 행렬(matrix)

최근영 2023. 9. 22. 17:09

❓그래프

  • Vertex(정점)과 Edge(간선)으로 이루어진 자료구조
  • 정점과 정점 사이의 관계를 Edge(간선)으로 표현한다.

 

좌 : 무방향 그래프 / 우 : 방향 그래프

 

그래프 구성 요소

  • Vertex/Node(정점) : Node 혹은 Vertex 라고 표현하며 그래프에서 각각 지점을 의미한다. (위 그림은 1, 2, 3 등)

  • Edge/Link(간선) : Node 와 Node 혹은 Vertex 와 Vertex등 각 정점들을 연결하는 선을 의미한다. (그래프 사이 선)

  • Weight(가중치) : 간선을 통해 이동하는데 소요되는 비용등을 표시하는 곳에 사용한다. ( 표기되어 있지 않지만 간선과 간선사이의 비용등을 나타냄 )

  • Direction Graph : 방향이 있는 그래프를 의미하고 간선의 방향에 따라 이동만 가능한 경우에 사용된다.

  • Undirected Graph : 방향이 없는 무방향 그래프를 의미하고 양방향 이동이 가능한 그래프이다.

  • Adjacency : 간선으로 연결된 인접 정점들을 의미한다.

  • Degree : 각 정점에 연결된 Edge들의 수를 의미한다. Out-Degree 와 In-Degree로 나뉘며 이 둘의 합을 통해 그 정점에서 Degree를 구할 수 있다. ( 나가는 간선과 들어오는 간선을 뜻한다. )

  • Path : 정점 A에서 B로 이동할 수 있는 경로를 의미힌다. 여러 종류의 길이 존재할 수 있으며 길이 존재하면 Reachable 할 수 있다고 표현한다.

Cycle, Self-loop 그래프

 

  • Self-loops : 정점에서 자기 자신으로 돌아오는 간선을 뜻한다. (위 그림에서 4번)

  • Simple Path : 경로 상 모든 정점들이 중복되지 않으면 이 경로를 simple path라고 한다. ( ex : 1 2 6 )

  • Cycle : 그래프가 Path를 따라 동일한 정점으로 돌아올 수 있는 경우를 의미한다. < 1, 2, 3 >가 사이클을 이룬다. 시작점과 끝점을 제외하고 중복을 이루면 안된다.

 

그래프 구현 방법

 그래프를 구현하는 방법에는 인접리스트와 인접행렬 방식이 존재한다.

 

 

인접리스트

 인접 리스트는 연결리스트를 이용하여 각 정점과 인접한 다른 정점들을 저장하는 방법

무방향 그래프 리스트

 

  • 무방향 그래프의 경우 노드가 양방향으로 연결되어 있으므로 각각 연결된 노드들의 리스트를 2차원 배열로 만들어준다.
graph = [
    [],
    [2,3],
    [1,4],
    [1],
    [2,6],
    [6],
    [4,5]
]

 

방향 그래프 리스트

  • 방향 그래프의 경우 각 화살표가 가리키는 방향의 노드들을 추가해준다.
graph = [
    [],
    [2,3],
    [6],
    [4],
    [],
    [6],
    []
]

 

인접행렬

무방향 그래프 인접 행렬

 

  • 인접 행렬을 만드는 경우는 각각 인덱스와 매칭되도록 좌표값에 1을 표시해서 연결 되었음을 알려준다.
  • 대각선을 기준으로 대칭으로 배열이 생성된다.
matrix = [
    [0,1,1,0,0,0],
    [1,0,0,1,0,0],
    [1,0,0,0,0,0],
    [0,1,0,0,0,1],
    [0,0,0,0,0,1],
    [0,0,0,1,1,0],
]

 

방향 그래프 인접 행

 

  • 방향 그래프 행렬의 경우 화살표가 연결된 부분만 1로 표시해준다.
matrix = [
    [0,1,1,0,0,0],
    [0,0,0,0,0,1],
    [0,0,0,1,0,0],
    [0,0,0,0,0,0],
    [0,0,0,0,0,1],
    [0,0,0,0,0,0],
]

 

인풋값으로 입력된 값을 통해 리스트와 행렬 만들기

 

from pprint import pprint

N = int(input())

matrix = [ [0] * (N+1) for _ in range(N+1) ]

graph = [ [] for _ in range(N+1) ]

for _ in range(10):
    A, B = map(int,input().split())

    graph[A].append(B)
    graph[B].append(A)
    matrix[A][B] = 1
    matrix[B][A] = 1

print(graph)
pprint(matrix)

7
1 3
1 2
2 5
2 7
3 4
1 6
5 6
4 7
7 3
1 7

[[], [3, 2, 6, 7], [1, 5, 7], [1, 4, 7], [3, 7], [2, 6], [1, 5], [2, 4, 3, 1]]
[[0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 1, 1, 0, 0, 1, 1],
 [0, 1, 0, 0, 0, 1, 0, 1],
 [0, 1, 0, 0, 1, 0, 0, 1],
 [0, 0, 0, 1, 0, 0, 0, 1],
 [0, 0, 1, 0, 0, 0, 1, 0],
 [0, 1, 0, 0, 0, 1, 0, 0],
 [0, 1, 1, 1, 1, 0, 0, 0]]
저작자표시 (새창열림)