그래프 데이터 구조란 무엇입니까?
ㅏ 그래프 정점과 가장자리로 구성된 비선형 데이터 구조입니다. 정점은 노드라고도 하며 가장자리는 그래프의 두 노드를 연결하는 선 또는 호입니다. 보다 공식적으로 그래프는 정점 세트로 구성됩니다( 안에 ) 및 모서리 세트( 그리고 ). 그래프는 다음과 같이 표시됩니다. 지(V, E) .
그래프의 표현
그래프를 표현하는 가장 일반적인 두 가지 방법은 다음과 같습니다.
- 인접 행렬
- 인접 목록
인접 행렬
인접 행렬은 그래프를 부울(0과 1) 행렬로 표현하는 방법입니다.
있다고 가정하자 N 그래프의 꼭짓점 따라서 2D 행렬을 만듭니다. adjMat[n][n] n x n 차원을 가짐.
- 꼭지점에 모서리가 있는 경우 나 에게 제이 , 표시 adjMat[i][j] ~처럼 1 .
- 꼭지점에서 모서리가 없는 경우 나 에게 제이 , 표시 adjMat[i][j] ~처럼 0 .
인접 행렬에 대한 무방향 그래프 표현:
아래 그림은 방향이 없는 그래프를 보여줍니다. 처음에는 전체 Matrix가 초기화되어 0 . 소스에서 대상까지 가장자리가 있으면 삽입합니다. 1 두 경우 모두 ( adjMat[목적지] 그리고 조정매트 [ 목적지]) 왜냐하면 우리는 어느 쪽으로든 갈 수 있기 때문입니다.
인접 행렬에 대한 무방향 그래프
인접 행렬에 대한 방향 그래프 표현:
아래 그림은 방향성 그래프를 보여줍니다. 처음에는 전체 Matrix가 초기화되어 0 . 소스에서 대상까지 가장자리가 있는 경우 삽입합니다. 1 그 특정을 위해 adjMat[목적지] .
인접 행렬에 대한 방향 그래프
인접 목록
목록 배열은 두 정점 사이의 가장자리를 저장하는 데 사용됩니다. 배열의 크기는 배열의 수와 같습니다. 정점(즉, n) . 이 배열의 각 인덱스는 그래프의 특정 꼭짓점을 나타냅니다. 배열의 인덱스 i에 있는 항목에는 정점에 인접한 정점을 포함하는 연결 리스트가 포함되어 있습니다. 나 .
있다고 가정하자 N 그래프의 꼭짓점 목록의 배열 크기의 N ~처럼 adjList[n].
자바의 임의 값 생성기
- adjList[0]은 정점에 연결된(이웃) 모든 노드를 갖습니다. 0 .
- adjList[1]은 정점에 연결된(이웃) 모든 노드를 갖습니다. 1 등등.
인접 목록에 대한 무방향 그래프 표현:
아래 무방향 그래프에는 3개의 정점이 있습니다. 따라서 각 인덱스가 정점을 나타내는 크기 3의 목록 배열이 생성됩니다. 이제 정점 0에는 두 개의 이웃(즉, 1과 2)이 있습니다. 따라서 배열의 인덱스 0에 정점 1과 2를 삽입합니다. 마찬가지로 정점 1의 경우 두 개의 이웃(즉, 2와 0)이 있으므로 배열의 인덱스 1에 정점 2와 0을 삽입합니다. 마찬가지로 정점 2의 경우 목록 배열에 이웃을 삽입합니다.
인접 목록에 대한 무방향 그래프
인접 목록에 대한 방향 그래프 표현:
아래 방향 그래프에는 3개의 정점이 있습니다. 따라서 각 인덱스가 정점을 나타내는 크기 3의 목록 배열이 생성됩니다. 이제 정점 0에는 이웃이 없습니다. 정점 1의 경우 두 개의 이웃(즉, 0과 2)이 있으므로 배열의 인덱스 1에 정점 0과 2를 삽입합니다. 마찬가지로 정점 2의 경우 목록 배열에 이웃을 삽입합니다.
인접 목록에 대한 방향 그래프