그래프는 비선형 데이터 구조입니다. 노드를 사용하여 데이터를 나타내고 가장자리를 사용하여 관계를 나타냅니다. 그래프 G에는 두 개의 섹션이 있습니다. 꼭짓점과 모서리입니다. 정점은 집합 V를 사용하여 표현되고 가장자리는 집합 E로 표현됩니다. 따라서 그래프 표기법은 G(V,E)입니다. 아이디어를 얻기 위해 한 가지 예를 살펴보겠습니다.
이 그래프에는 5개의 꼭짓점과 5개의 모서리가 있습니다. 가장자리가 지시됩니다. 예를 들어 정점 B와 D를 연결하는 가장자리를 선택하면 소스 정점은 B이고 대상은 D입니다. 따라서 B를 D로 이동할 수는 있지만 D에서 B로 이동할 수는 없습니다.
그래프는 비선형이며 규칙적인 구조가 없습니다. 메모리에 그래프를 나타내기 위해 몇 가지 다른 스타일이 있습니다. 이러한 스타일은 -
- 인접 행렬 표현
- 에지 목록 표현
- 인접 목록 표현
인접 행렬 표현
인접 행렬을 사용하여 그래프를 나타낼 수 있습니다. 주어진 행렬은 인접 행렬입니다. 이진 정방행렬로 i번째 행에서 j번째 열까지 간선이 있으면 1로 표시합니다. 인접행렬을 사용하여 무방향 그래프를 표현하려고 하면 행렬은 대칭이 됩니다.
에지 목록 표현
그래프는 1차원 배열을 사용하여 표현할 수도 있습니다. 이것을 에지 목록이라고 합니다. 이 표현에는 5개의 가장자리가 있습니다. 각 가장자리에 대해 첫 번째 요소는 소스이고 두 번째 요소는 대상입니다. 무방향 그래프 표현의 경우 에지 목록의 요소 수가 두 배가 됩니다.
인접 목록 표현
이것은 또 다른 유형의 그래프 표현입니다. 인접 목록이라고 합니다. 이 표현은 연결 목록을 기반으로 합니다. 이 접근 방식에서 각 노드는 해당 정점과 직접 연결된 노드 목록을 보유합니다. 목록의 끝에서 각 노드는 null 값으로 연결되어 해당 목록의 끝 노드임을 알려줍니다.
