코딩테스트 합격자 되기 - 7주차

공부한 내용

그래프

• 그래프 용어 정리

  • 

• 그래프의 특징과 종류
  • 흐름을 표현하는 방향성
    • 방향 그래프 : 방향이 있는 간선이 있는 그래프
    • 무방향 그래프(비방향 그래프) : 방향이 없는 간선이 있는 그래프
  • 흐름을 정도를 표현하는 가종치
    • 가중치 그래프 : 가중치가 있는 그래프
  • 시작과 끝의 연결 여부를 보는 순환
    • 순환그래프 : 순환이 있는 그래프
    • 비순환 그래프 : 순환이 존재하지 않는 그래프
• 그래프 구현
  • 그래프 예시
    • ex) 서울에서 부산으로 유동인구 8000명
    • 데이터를 담고 있는 노드(서울, 부산)
    • 노드를 잇는 간선(서울과 부산의 연결 유뮤)
    • 간선의 방향 (서울에서 부산 방향으로)
    • 간선의 가중치(유동인구 8000명)
    • 그래프의 구현 방식에는 인접 행렬과 인접 리스트가 있다
  • 인접 행렬 그래프 표현
    • 보통 배열 사용
    • 노드는 인덱스, 가중치는 배열의 값으로 생각

    • 

• • 인접 리스트 그래프 표현
    • 값, 가중치, 다음노드를 묶어 관리한다.

    • 

    1. 우선은 노드 개수만큼 배열을 준비
    2. 배열의 인덱스는 각 시작 노드를 의미하며 배열의 값에는 다음 노드를 연결
    -