그래프

wonjoogu·2021년 3월 16일
0

SSAFY TIL

목록 보기
3/18

자료구조

  • [ 선형 자료구조 ] : 전후관계가 1:1 관계, 한줄로 줄세울 수 있다.

  • [ 비선형 자료구조 ] : 전후관계가 1:1이 아닌 관계 ( 1:다, 다:다 )
    ex) 트리구조(1:다), 그래프(다:다)

  • Tree 구성 요소 : Node

  • 무향그래프(방향성 존재x) : V개의 정점일 때 V x (V-1)/2 (양방향 관계)
    ex) 5개의 정점일 때 -> 5 * 4/2 = 10
    양방향 관계를 선 하나로 표현

  • 유향그래프(방향성 존재o, 단방향 관계) : V * (V-1)

  • 가중치그래프 : 관계의 정도를 수치로 표현한 그래프

  • 사이클 없는 방향 그래프 : 같은 정점을 두번 이상 발생하지 않는 것

  • 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프
    V개 정점 : 모든 정점이다. V-1개 간선을 갖는 그래프
    따라서 V * (V-1)/2는 완전 그래프를 나타내는 것이다.

  • 부분 그래프 : 원래 그래프에서 부분집합 느낌. 일부의 정점이나 간선을 제외한 그래프

  • 트리는 싸이클이 없는 무향 연결 그래프이다.
    -> 두 노드 사이에는 유일한 경로가 존재
    -> 각 노드는 최대 하나의 부모 노드가 존재할 수 있다
    -> 각 노드는 자식노드가 없거나 하나 이상 존재

  • 인접 : 두 개의 정점에 간선이 연결되어 있으면 서로 인접하다.(연결되어 있다, 관계되어 있다)

  • 그래프는 어떤 정점에서든 연결되어 있어서 어디서 시작해도 상관없다.
    (무향그래프일 때 가능(루트 개념이 없으니까 정점 모두 동등 레벨로 본다), 유향그래프는 정점에 오기만 하는 경우도 있을 수 있어서)

  • 경로 : 어떤 정점에서 시작하여 다른 정점으로 끝나는 순회로 두 정점 사이를 잇는 간선들을 순서대로 나열한 것
    -> 0-6의 경로
    정점들:0-2-4-6
    간선들:(0,2),(2,4),(4,6)

  • 경로 중 한 정점을 최대 한번만 지나면 단순 경로, 그렇지 않으면 순환경로(Cyclic path, 경로의 시작점과 끝점이 같거나 경로에서 어떤 정점을 2번 이상 거치는 경우 ex)1-3-5-1)

[ 간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정 ]

  • 인접 행렬 : 정점개수가 V개일 때 V x V 크기의 2차원 배열, g[from][to]
    인접해 있으면 1, 그렇지 않으면 0 or boolean 배열도 가능
    from과 to가 같은 곳은 모두 0으로 지정, 대칭이 되는 자리에 같은 숫자의 정보를 갖고 있음
    g[from][j] = 간선 정보 ex) 간선: 8개면 무향그래프 의미로의 간선 수는 2배로 16개다
    유향그래프에서는 간선이 8개면 의미로의 간선도 8개(1인 것은 8개)
    단점 : 희소그래프(정점은 많은데 간선이 적은 것): 항상 배열의 사이즈는 V * V이지만 간선은 적기 때문에 공간을 너무 차지한다. ex)정점이 10000개인데 V x V = 100000000 -> 400MB 인데 메모리 제약은 보통 256이나 512다. 따라서 불가능하다. vs 밀집그래프(정점 간선 비례가 많은 것 (완전그래프:한 정점에서 모든 정점에 다 연결되어 있으므로))

  • 인접 리스트 : 인접한 정점만 목록으로 유지한다(순차적). 목록 유지할 때 연결리스트로 표현(LinkedList)
    ex) 0번 정점과 인접합 정점 연결리스트 or (List 자료구조 활용(ArrayList))
    목록 유지 위한 링크 포인터 : 목록을 유지하기 위해서 따라갈 수 있는 포인터 역할이지 두 관계를 연관시키는 것이 아니다.
    (연결리스트에 Head(첫번째)를 갖고 있으면 다 갖고 있는 것이다.)
    from은 정점 개수만큼 만들고 여기에는 ArrayList, ArrayList[]
    무향그래프: 무향 그래프 노드 수 = 간선의 수 * 2, 각 정점의 노드 수 = 정점의 차수
    유향그래프: 방향 그래프 노드 수 = 간선의 수, 각 정점의 노드 수 = 정점의 진입 차수

  • 간선 리스트 : 간선 정보를 나타내는 리스트, 간선 개수를 알고 있다면 배열, 간선 개수를 모르고 있다면 List 사용

*** 정점 중심의 해결 : 인접 행렬, 인접 리스트
*** 간선 중심의 해결 : 간선 리스트

  • V * V 정방 행렬

  • 무향 그래프 : 대칭이 되게 배열을 채워야함, i번째 행의 합 = i번째 열의 합 = Vi의 차수
    g[fromg][to] = go[to][from]
    대칭으로 값의 개수가 같아서 대칭으로 계산해도됨

  • 유향 그래프 : 간선의 정보가 정확하게 나눠져있음(from과 to가 나눠져있음)
    g[from][to] != g[to][from]
    행 i의 합 = Vi의 진출 차수
    열 i의 합 = Vi의 진입 차수
    열을 고정해놓고 행의 진입 차수 본다.

  • 그래프 탐색(순회)
    : 그래프 순회는 비선형구조인 그래프로 표현된 모든 자료(정점)을 빠짐없이 탐색하는 것

  1. 너비 우선 탐색
  2. 깊이 우선 탐색
  • BFS : 너비 우선 탐색, 임의의 시작점에서 인접한 정점들을 모두 차례로 방문한 후 방문한 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식(각 정점 기준으로 자식들을 탐색, 트리와 비슷), 큐를 활용함(선입선출)
    -> 초기 상태 : Visited 배열 생성 및 false로 초기화 (트리 구조와는 다르게 visited 배열을 생성해야한다.)
    -> 큐 생성, 큐에 넣고 방문 체크를 미리 함(효율적)
profile
SSAFY 5th

0개의 댓글