[algorithm] 객체 그래프 표현을 인접 목록 및 행렬 표현과 비교

개체 및 포인터

이것들은 다른 답변에서 말한 hammar와 같은 기본 데이터 구조 Java입니다.이를 가장자리 및 정점과 같은 클래스로 표현할 수 있습니다. 예를 들어 가장자리는 두 개의 정점을 연결하고 방향을 지정하거나 지정하지 않을 수 있으며 가중치를 포함 할 수 있습니다. 정점은 ID, 이름 등을 가질 수 있습니다. 대부분 둘 다 추가 속성이 있습니다. 따라서 다음과 같이 그래프를 구성 할 수 있습니다.

Vertex a = new Vertex(1);
Vertex b = new Vertex(2);
Edge edge = new Edge(a,b, 30); // init an edge between ab and be with weight 30

이 접근 방식은 객체 지향 사용자에게 더 읽기 쉽고 편리하기 때문에 객체 지향 구현에 일반적으로 사용됩니다.

매트릭스

행렬은 단순한 2 차원 배열입니다. 다음과 같이 int 배열로 나타낼 수있는 정점 ID가 있다고 가정합니다.

int[][] adjacencyMatrix = new int[SIZE][SIZE]; // SIZE is the number of vertices in our graph
adjacencyMatrix[0][1] = 30; // sets the weight of a vertex 0 that is adjacent to vertex 1

일반적으로 인덱스 액세스가 필요한 조밀 한 그래프에 사용됩니다. 이것으로 무 / 방향 및 가중치 구조를 나타낼 수 있습니다.

인접 목록

이것은 단순한 데이터 구조 혼합이며, 일반적으로 HashMap<Vertex, List<Vertex>>. 유사하게 HashMultimap구아바에서 사용할 수 있습니다 .

O (1) (상각 된) 정점 조회가 있고 내가 요구 한 특정 정점에 인접한 모든 정점의 목록을 반환하기 때문에이 접근 방식은 멋집니다.

ArrayList<Vertex> list = new ArrayList<>();
list.add(new Vertex(2));
list.add(new Vertex(3));
map.put(new Vertex(1), list); // vertex 1 is adjacent to 2 and 3

이것은 희소 그래프를 나타내는 데 사용됩니다. Google에 지원하는 경우 웹 그래프가 희소하다는 것을 알아야합니다. BigTable을 사용하여보다 확장 가능한 방식으로 처리 할 수 ​​있습니다 .

아 그리고 BTW, 여기 에 멋진 사진과 함께이 게시물의 아주 좋은 요약이 있습니다.)