Java java지도 시간 가중치 그래프 표현

가중치 그래프 표현

Sep 06, 2024 am 06:07 AM

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

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

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

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

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

Representing Weighted Graphs

가중치는 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). 정점 ij가 연결되지 않은 경우 weights[i][j]null입니다. 예를 들어, 위 그림 (a)의 그래프에서 가중치는 인접행렬을 이용하여 다음과 같이 표현할 수 있습니다.

Representing Weighted Graphs

인접 목록

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

Representing Weighted Graphs

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

로 확장합니다.

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

를 구현합니다.

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

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

Representing Weighted Graphs

Representing Weighted Graphs

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

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

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

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

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

인기 기사

<gum> : Bubble Gum Simulator Infinity- 로얄 키를 얻고 사용하는 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
Nordhold : Fusion System, 설명
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌
Mandragora : 마녀 트리의 속삭임 - Grappling Hook 잠금 해제 방법
3 몇 주 전 By 尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

회사의 보안 소프트웨어가 응용 프로그램이 실행되지 않습니까? 문제 해결 및 해결 방법은 무엇입니까? 회사의 보안 소프트웨어가 응용 프로그램이 실행되지 않습니까? 문제 해결 및 해결 방법은 무엇입니까? Apr 19, 2025 pm 04:51 PM

일부 애플리케이션이 제대로 작동하지 않는 회사의 보안 소프트웨어에 대한 문제 해결 및 솔루션. 많은 회사들이 내부 네트워크 보안을 보장하기 위해 보안 소프트웨어를 배포 할 것입니다. ...

분류를 구현하고 그룹의 일관성을 유지하기 위해 이름을 숫자로 변환하려면 어떻게합니까? 분류를 구현하고 그룹의 일관성을 유지하기 위해 이름을 숫자로 변환하려면 어떻게합니까? Apr 19, 2025 pm 11:30 PM

많은 응용 프로그램 시나리오에서 정렬을 구현하기 위해 이름으로 이름을 변환하는 솔루션, 사용자는 그룹으로, 특히 하나로 분류해야 할 수도 있습니다.

맵 구조를 사용하여 시스템 도킹에서 필드 매핑 문제를 단순화하는 방법은 무엇입니까? 맵 구조를 사용하여 시스템 도킹에서 필드 매핑 문제를 단순화하는 방법은 무엇입니까? Apr 19, 2025 pm 06:21 PM

시스템 도킹의 필드 매핑 처리 시스템 도킹을 수행 할 때 어려운 문제가 발생합니다. 시스템의 인터페이스 필드를 효과적으로 매핑하는 방법 ...

데이터베이스 쿼리 조건을 구축하기 위해 엔티티 클래스 변수 이름을 우아하게 얻는 방법은 무엇입니까? 데이터베이스 쿼리 조건을 구축하기 위해 엔티티 클래스 변수 이름을 우아하게 얻는 방법은 무엇입니까? Apr 19, 2025 pm 11:42 PM

데이터베이스 작업에 MyBatis-Plus 또는 기타 ORM 프레임 워크를 사용하는 경우 엔티티 클래스의 속성 이름을 기반으로 쿼리 조건을 구성해야합니다. 매번 수동으로 ...

Intellij Idea는 로그를 출력하지 않고 스프링 부팅 프로젝트의 포트 번호를 어떻게 식별합니까? Intellij Idea는 로그를 출력하지 않고 스프링 부팅 프로젝트의 포트 번호를 어떻게 식별합니까? Apr 19, 2025 pm 11:45 PM

IntellijideAultimate 버전을 사용하여 봄을 시작하십시오 ...

Java 객체를 어레이로 안전하게 변환하는 방법은 무엇입니까? Java 객체를 어레이로 안전하게 변환하는 방법은 무엇입니까? Apr 19, 2025 pm 11:33 PM

Java 객체 및 배열의 ​​변환 : 캐스트 유형 변환의 위험과 올바른 방법에 대한 심층적 인 논의 많은 Java 초보자가 객체를 배열로 변환 할 것입니다 ...

Redis 캐시 솔루션을 사용하여 제품 순위 목록의 요구 사항을 효율적으로 실현하는 방법은 무엇입니까? Redis 캐시 솔루션을 사용하여 제품 순위 목록의 요구 사항을 효율적으로 실현하는 방법은 무엇입니까? Apr 19, 2025 pm 11:36 PM

Redis 캐싱 솔루션은 제품 순위 목록의 요구 사항을 어떻게 인식합니까? 개발 과정에서 우리는 종종 a ... 표시와 같은 순위의 요구 사항을 처리해야합니다.

전자 상거래 플랫폼 SKU 및 SPU 데이터베이스 설계 : 사용자 정의 속성과 귀속없는 제품을 모두 고려하는 방법은 무엇입니까? 전자 상거래 플랫폼 SKU 및 SPU 데이터베이스 설계 : 사용자 정의 속성과 귀속없는 제품을 모두 고려하는 방법은 무엇입니까? Apr 19, 2025 pm 11:27 PM

전자 상거래 플랫폼에서 SKU 및 SPU 테이블의 디자인에 대한 자세한 설명이 기사는 전자 상거래 플랫폼에서 SKU 및 SPU의 데이터베이스 설계 문제, 특히 사용자 정의 판매를 처리하는 방법에 대해 논의 할 것입니다 ...

See all articles