데이터 구조 – 그림 (1) (그림 의 저장 구조)

(1) 그림 의 추상 적 인 데이터 형식
데이터 형식 은 하나의 유형 과 이 유형 에 정 의 된 조작 집합 (예 를 들 어 정형 과 가감 승제 등 조작) 을 가리 키 며 추상 적 인 데이터 유형 은 논리 적 개념의 유형 과 이 유형의 조작 집합 을 가리킨다.
데이터 집합: 노드 집합 과 변 집합 으로 구성 된다.작업 집합: 노드 / 변 초기 화, 삽입 / 삭제, 인접 노드 찾기
(2) 그림 의 저장 구조
그림 에 저 장 될 정 보 는 노드 정보 + 노드 간 의 관 계 를 묘사 하 는 변 의 정보 노드 정보 에 대한 묘 사 는 실제 적 으로 선형 표 의 저장 문제 변 의 정보 묘 사 는 실제 적 으로 (n * n) 행렬 이 컴퓨터 에 저 장 된 문 제 는 변 의 저장 방식 에 따라 그림 의 저장 은 인접 행렬 저장 과 인접 표 저장 으로 나 뉜 다.
인접 매트릭스 저장 소
노드 는 1 차원 배열 로 저장 합 니 다.변 정보의 인접 행렬 은 2 차원 배열 로 저장 된다.
인접 행렬 저장 소 는 조밀 행렬 에 적용 된다.
인접 표 저장 소
그림 의 체인 저장 구조 도 에서 정점 은 1 차원 배열 로 저장 되 고 정점 배열 의 데이터 요 소 는 노드 정 보 를 저장 하 는 것 을 제외 하고 이 정점 의 첫 번 째 인접 점 의 지침 을 저장 하여 이 정점 의 변 정 보 를 쉽게 찾 을 수 있다.즉, 모든 정점 은 data 도 메 인, adj 도 메 인 두 부분 으로 구성 되 고 data 도 메 인 은 노드 정 보 를 저장 하 며 adj 도 메 인 은 이 정점 의 인접 정점 링크 의 헤드 포인터 를 저장 합 니 다.그림 에서 링크 로 저장 합 니 다.그림 에서 모든 정점 vi 에 하나의 단일 체인 표를 만 들 고 i 번 째 단일 체인 표 중의 각 노드 는 정점 vi 의 변 에 의존 하 는 것 을 나타 낸다.모든 노드 는 vex 역, wei 역, 그리고 next 역 으로 구성 되 어 있 으 며, vex 역 은 시작 정점 vi 와 연 결 된 인접 정점 vj 가 정점 배열 에서 의 아래 표 시 된 번 호 를 저장 합 니 다.wei 도 메 인 은 두 정점 사이 의 가중치 를 저장 합 니 다.next 다음 인접 노드 의 포인터 도 메 인 을 저장 합 니 다.
인접 표 저장 구 조 는 희소 도 에 적용 된다.
(3) 인접 행렬 도 류 디자인

public class AdjMWGraph{
    static final int maxWeight=10000;//         ，      

    private SeqList nodes;//        
    private int[][] edge;//          
    private int numOfEdge;//        

    public AdjMWGraph(int numOfNode){//numOfNode     
        nodes=new SeqList(numOfNode);//             
        edge=new int[numOfNode][numOfNode];
        for(int i=0;i