가중치 그래프 표현

가중치 가장자리는 인접 목록에 저장할 수 있습니다.

가중치 그래프에는 정점 가중치와 가장자리 가중치의 두 가지 유형이 있습니다. 꼭지점 가중치 그래프에서는 각 꼭지점에 가중치가 할당됩니다. 간선 가중치 그래프에서는 각 간선에 가중치가 할당됩니다. 두 가지 유형 중에서 간선 가중치 그래프가 더 많은 용도로 사용됩니다. 이 장에서는 간선 가중치 그래프를 고려합니다.

가중치 그래프는 간선의 가중치를 표현해야 한다는 점을 제외하면 비가중 그래프와 동일한 방식으로 표현할 수 있습니다. 비가중 그래프와 마찬가지로 가중치 그래프의 정점은 배열에 저장될 수 있습니다. 이 섹션에서는 가중치 그래프의 간선에 대한 세 가지 표현을 소개합니다.

가중치가 적용된 모서리 표현: Edge Array

가중치 모서리는 2차원 배열을 사용하여 표현할 수 있습니다. 예를 들어 아래 그림 (b)의 배열을 사용하여 아래 그림 (a)의 그래프에 있는 모든 간선을 저장할 수 있습니다.

가중치는 Integer, Double, BigDecimal 등 모든 유형이 될 수 있습니다. Object 유형의 2차원 배열을 사용하여 다음과 같이 가중치 가장자리를 나타낼 수 있습니다.

객체[][] 가장자리 = {
{new Integer(0), new Integer(1), new SomeTypeForWeight(2)},
{new Integer(0), new Integer(3), new SomeTypeForWeight(8)},
...
};

가중 인접 행렬

그래프에 n개의 정점이 있다고 가정합니다. 가중치와 같은 2차원 n * n 행렬을 사용하여 가장자리의 가중치를 나타낼 수 있습니다. weights[i][j]는 가장자리의 가중치를 나타냅니다(i, j). 정점 i과 j가 연결되지 않은 경우 weights[i][j]는 null입니다. 예를 들어, 위 그림 (a)의 그래프에서 가중치는 인접행렬을 이용하여 다음과 같이 표현할 수 있습니다.

인접 목록

가장자리를 표현하는 또 다른 방법은 가장자리를 객체로 정의하는 것입니다. AbstractGraph.Edge 클래스는 AbstractGraph.java에서 비가중 가장자리를 나타내도록 정의되었습니다. 가중치가 적용된 가장자리의 경우 아래 코드와 같이 WeightedEdge 클래스를 정의합니다.

AbstractGraph.Edge는 AbstractGraph 클래스에 정의된 내부 클래스입니다. 정점 u에서 v까지의 모서리를 나타냅니다. WeightedEdge는 AbstractGraph.Edge를 새로운 속성인 weight.

로 확장합니다.

WeightedEdge 객체를 만들려면 new WeightedEdge(i, j, w)를 사용하세요. 여기서 w는 가장자리의 가중치(i)입니다. , j). 종종 모서리의 가중치를 비교해야 합니다. 이러한 이유로 WeightedEdge 클래스는 Comparable 인터페이스

를 구현합니다.

비가중 그래프의 경우 인접 목록을 사용하여 간선을 나타냅니다. 가중치 그래프의 경우 여전히 인접 목록을 사용하며, 아래 그림 a의 그래프에서 정점에 대한 인접 목록은 다음과 같이 나타낼 수 있습니다.

java.util.List<WeightedEdge>[] 목록 = 새로운 java.util.List[5];

list[i]는 정점 i에 인접한 모든 가장자리를 저장합니다.

유연성을 위해 고정 크기 배열 대신 배열 목록을 사용하여 목록을 다음과 같이 표현합니다.

목록> 목록 = 새로운 java.util.ArrayList<>();

위 내용은 가중치 그래프 표현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!