toposort하는 방법; 도수 작성

Question

학교 과제를위한 그래프 구조를 작성 중입니다. 현재는 인접성 목록으로 표시됩니다. 키가 그래프의 노드 (정점)이고 값이 가장자리 인 목록 (원본 노드와 대상 노드 포인터가 포함 된 개체가 "가중치"인 해시 맵을 사용하고 있습니다.)를 생성한다.

다음 과제는 토폴로지 정렬을 코딩하는 것입니다.하지만 막혔습니다. 가장 좋은 방법은 각 노드 객체에 정수 필드 (노드로 이어지는 가장자리의 양)를 제공하는 것입니다.하지만이 방법을 모든 노드에 할당 할 수는 없습니다. 내가 가진 것을 줘.

제안 사항?

Answer 1

노드 개념을 만들 것을 제안합니다. 당신이 Edge 객체 일뿐만 아니라 Node 객체를 가질 수도 있다는 것을 의미합니다. 더 나은 모델링은 항상 문제를 더 빨리 해결할 수 있도록 도와줍니다. Node 인스턴스에 추가 정보를 저장할 수 있기 때문에 Node로 정의 된 HashMap에 키가 있으면 Integer가이 경우 도움이됩니다.

그러나 현재 구조를 유지하기를 원한다면 주어진 노드로 연결되는 가장자리의 수를 알기 위해서는 HashMap entrySet의 다양한 값을 반복해야한다. 가장자리 목록 일 것입니다.) 그리고 찾고있는 노드가있는 노드가 대상 노드를 가지고 있는지 확인하십시오.이 정보는 보조 구조에 저장해야합니다 (예 : 다른지도가 있음)