logo

TechCodeview

그래프 데이터 구조 및 알고리즘

그래프 데이터 구조 의 모음입니다 노드 연결됨 가장자리 . 서로 다른 엔터티 간의 관계를 나타내는 데 사용됩니다. 그래프 알고리즘 그래프를 조작하고 분석하여 다음과 같은 다양한 문제를 해결하는 데 사용되는 방법입니다. 최단 경로 찾기 또는 주기를 감지합니다.



내용의 테이블

씨

그래프의 구성요소:

  • 정점: 정점은 그래프의 기본 단위입니다. 때로는 정점을 정점 또는 노드라고도 합니다. 모든 노드/정점에는 레이블이 지정되거나 지정되지 않을 수 있습니다.
  • 가장자리: 모서리는 그래프의 두 노드를 연결하는 데 그려지거나 사용됩니다. 방향성 그래프에서 노드 쌍을 정렬할 수 있습니다. Edge는 가능한 모든 방법으로 두 노드를 연결할 수 있습니다. 규칙이 없습니다. 때로는 모서리를 호라고도 합니다. 모든 가장자리에 라벨을 붙이거나 라벨을 붙이지 않을 수 있습니다.

그래프의 기본 작업:

그래프의 기본 작업은 다음과 같습니다.



  • 그래프에 노드/에지 삽입 – 그래프에 노드를 삽입합니다.
  • 그래프에서 노드/에지 삭제 – 그래프에서 노드를 삭제합니다.
  • 그래프에서 검색 – 그래프에서 엔터티를 검색합니다.
  • 그래프 순회 – 그래프의 모든 노드를 순회합니다.

그래프의 응용:

실제 적용 사례는 다음과 같습니다.

  • 그래프 데이터 구조는 패스, 슛, 태클 등 팀 내 선수 간의 상호 작용을 나타내는 데 사용할 수 있습니다. 이러한 상호 작용을 분석하면 팀 역학과 개선 영역에 대한 통찰력을 얻을 수 있습니다.
  • 소셜 미디어의 친구 네트워크와 같은 소셜 네트워크를 나타내는 데 일반적으로 사용됩니다.
  • 그래프는 라우터와 스위치 간의 연결과 같은 컴퓨터 네트워크의 토폴로지를 나타내는 데 사용할 수 있습니다.
  • 그래프는 도로, 공항 등 교통망의 여러 장소 간 연결을 나타내는 데 사용됩니다.
  • 그래프는 정점이 뉴런을 나타내고 가장자리가 뉴런 사이의 시냅스를 나타내는 신경망에서 사용됩니다. 신경망은 우리의 뇌가 어떻게 작동하는지, 학습할 때 연결이 어떻게 변하는지 이해하는 데 사용됩니다. 인간의 뇌에는 약 10^11개의 뉴런과 10^15개의 시냅스가 있습니다.

그래프의 기본:

그래프의 BFS 및 DFS:

  • 그래프의 너비 우선 순회
  • 그래프의 깊이 우선 순회
  • 깊이우선탐색의 응용
  • 너비 우선 탐색의 응용
  • 반복 깊이 우선 검색
  • 연결이 끊긴 그래프를 위한 BFS
  • DFS를 사용한 그래프의 전이적 폐쇄
  • BFS와 DFS의 차이점

그래프의 주기:

  • 유방향 그래프에서 주기 감지
  • 무방향 그래프에서 사이클 감지
  • 색상을 사용하여 직접 그래프에서 사이클 감지
  • 그래프에서 음의 순환 감지 | (벨먼 포드)
  • 방향이 없고 연결된 그래프에서 길이 n의 주기
  • Floyd Warshall을 사용하여 음의 사이클 감지
  • 방향성 비순환 그래프 복제
  • Union-Find 알고리즘의 순위 및 경로 압축에 의한 Union
  • 그래프의 최단 경로:
    • Dijkstra의 최단 경로 알고리즘
    • 벨만-포드 알고리즘
    • 플로이드 워샬 알고리즘
    • 모든 쌍 최단 경로에 대한 Johnson의 알고리즘
    • 방향성 비순환 그래프의 최단 경로
    • 다이얼의 알고리즘
    • 다단계 그래프(최단 경로)
    • 비가중 그래프의 최단 경로
    • Karp의 최소 평균(또는 평균) 체중 주기 알고리즘
    • 0-1 BFS(이진 가중치 그래프의 최단 경로)
    • 무방향 그래프에서 최소 체중주기 찾기

    최소 스패닝 트리:

    • Prim의 최소 스패닝 트리(MST)
    • Kruskal의 최소 스패닝 트리 알고리즘
    • MST에 대한 Prim과 Kruskal 알고리즘의 차이점
    • 최소 스패닝 트리 문제의 응용
    • 모든 도시를 연결하는 데 필요한 최소 비용
    • 그래프의 총 스패닝 트리 수
    • 최소 제품 스패닝 트리
    • 최소 스패닝 트리에 대한 역삭제 알고리즘
    • 최소 스패닝 트리를 위한 Boruvka의 알고리즘

    토폴로지 정렬:

    • 토폴로지 정렬
    • 방향성 비순환 그래프의 모든 토폴로지 종류
    • 위상 정렬을 위한 Kahn의 알고리즘
    • DAG에 추가되어 DAG로 유지될 수 있는 최대 가장자리
    • 방향성 비순환 그래프의 가장 긴 경로
    • 정점의 출발시간을 이용한 그래프의 토폴로지 정렬

    그래프의 연결성:

    • 그래프의 연결점(또는 정점 절단)
    • 이중 연결된 구성요소
    • 그래프의 브리지
    • 오일러 경로 및 회로
    • 오일러 경로 또는 회로 인쇄를 위한 플뢰리 알고리즘
    • 강하게 연결된 구성요소
    • 정확히 k개의 간선을 사용하여 소스에서 목적지까지 가능한 모든 이동 횟수를 계산합니다.
    • 유향 그래프의 오일러 회로
    • 목표 단어에 도달하는 가장 짧은 사슬의 길이
    • 문자열 배열을 연결하여 원을 형성할 수 있는지 확인
    • 강하게 연결된 구성 요소를 찾는 Tarjan의 알고리즘
    • 각 Edge를 사용하여 각 노드를 이동하는 경로(Königsberg의 Seven Bridges)
    • 동적 연결 | 세트 1(증분)

    그래프의 최대 흐름:

    • 최대 흐름 문제 소개
    • 최대 흐름 문제에 대한 Ford-Fulkerson 알고리즘
    • 두 꼭지점 사이의 가장자리 분리 경로의 최대 수를 찾습니다.
    • 흐름 네트워크에서 최소 S-T 컷 찾기
    • 최대 이분 매칭
    • 채널 할당 문제
    • 푸시 재레이블 알고리즘 소개
    • Karger의 알고리즘 - 세트 1 - 소개 및 구현
    • 최대 흐름을 위한 Dinic의 알고리즘

    일부는 그래프에서 문제를 해결해야 합니다.

    • 부울 행렬에서 가장 큰 영역의 길이 찾기
    • 숲에 있는 나무의 수를 센다
    • 피터슨 그래프 문제
    • 무방향 그래프 복제
    • 그래프 컬러링(소개 및 응용)
    • 여행하는 세일즈맨 문제(TSP) 구현
    • 정점 커버 문제 | 세트 1(소개 및 근사 알고리즘)
    • K센터 문제 | 세트 1(그리디 근사 알고리즘)
    • Erdos Renyl 모델(무작위 그래프 생성용)
    • 중국 우체부 또는 경로 검사 | 세트 1(소개)
    • 유향 그래프를 위한 Hierholzer의 알고리즘
    • 주어진 그래프가 이분 그래프인지 아닌지 확인
    • 뱀과 사다리 문제
    • Boggle(문자판에서 가능한 모든 단어 찾기)
    • 최대 매칭을 위한 Hopcroft Karp 알고리즘 소개
    • 모든 오렌지가 썩는 데 필요한 최소 시간
    • 모든 정점의 주어진 각도에서 그래프를 구성합니다.
    • 유방향 그래프에 범용 싱크가 존재하는지 확인
    • 그래프의 싱크 노드 수
    • Two Clique 문제 (Graph를 두 개의 Clique로 나눌 수 있는지 확인)

    일부 퀴즈:

    • 그래프 순회에 관한 퀴즈
    • 그래프 최단 경로에 대한 퀴즈
    • 그래프 최소 스패닝 트리에 대한 퀴즈
    • 그래프에 대한 퀴즈

    빠른 링크 :

    자바 열거형 값
    • 깊이 우선 검색(DFS)에 대한 상위 10가지 인터뷰 질문
    • 몇 가지 흥미로운 최단 경로 질문
    • 그래프에 관한 비디오

    권장사항:

    • 데이터 구조와 알고리즘 배우기 | DSA 튜토리얼