인접 목록의 자바 구현

Question

각 노드와 그 무향 그래프에 정수 값을 갖는 n * m 행렬이 있습니다. 나는 그것에 대한 인접 목록을 만들고 싶다. 어떻게해야합니까? 어떤 도움이라도 대단히 감사합니다.

Answer 1

첫 번째 설명은 사용자가 m을 n으로 말하면서는 제외하고 인접 매트릭스로 보입니다. 인접 행렬은 항상 정사각형이므로 m==n으로 가정해야합니다. 행렬 요소는 모서리 가중치입니다.

그래프의 인접성 목록 표현은 (일반적으로) 쌍 집합의 배열 adj입니다. 세트 adj[i]은 표현 된 그래프에서 정사각형 i에서 j까지 w의 정방향 에지 i--w-->j이있는 경우 쌍 <j, w>을 포함합니다.

이 정의를 사용하면 n 빈 인접성 집합을 adj[i]으로 시작한 다음 행렬 요소 m[i][j] = w을 반복해야합니다. 각각에 대해 <j, w> ~ adj[i]을 추가하십시오.

이 자바 코드는 매우 사소한 것이므로 필자는 쓰지 않을 것이다. 인접 목록으로 표현 된 그래프의 유형은 ArrayList<HashMap<Integer, Integer>> adjacencies과 같습니다. 쌍 <j,w> in adj[i]은 해시 표 adjacencies.get(i)에 저장된 j -> w의 매핑입니다. 이러한 인접성을 생성하는 코드는 adjacencies.get(i).put(j, w)입니다.

이 방법을 사용하면, 해시 테이블 adjacencies.get(i)에 키를 통해 반복하여 i에 인접한 정점을 반복 모든 일반적인 그래프 작업 등 w = adjacencies.get(i).get(j)에 주어진 가장자리 i--w-->j의 무게를보고, 할 수 있습니다.

N이 연결됩니다 목록 가변 크기의 각 :

Answer 2

는 여기에 문제에 인접 list.According를 만들기위한 간단한 구현입니다.

먼저 초기화 정수의 연결리스트의 ArrayList를 :

ArrayList<LinkedList<Integer>> adj_list = new ArrayList<LinkedList<Integer>>(); 

그리고 간단하게 다음과 같은 코드를 반복하여 링크 된 목록을 추가 :의 당신이 그래프를 표현하기 위해 그것을 사용하는 경우,

adj_list.add(new LinkedList<Integer>()); 

을 더 linked lists = no vertices.So 위의 n (꼭지점 수) 번 반복해야합니다.

는

adj_list.get(0).add(3); 
adj_list.get(0).add(4); 
adj_list.get(0).add(5); 

그것은 단순히 3,4에 정점 0에서 그래프의 가장자리가 의미

말은 이제 다음 첫 번째 연결 lists.Do에 숫자 3,4,5를 추가 할 , 5.