데이터 구조 필기 정리 제6 장: 그림

제6 장 그림
이 장의 내용
본 장 은 주로 그림 의 개념, 저장 구조, 그림 의 옮 겨 다 니 는 방법, 가장 짧 은 경 로 를 계산 하고 나 무 를 최소 로 생 성 하 는 방법 등 을 소개 하 는데 본 장 은 연구 에 있어 중점 적 인 내용 이다.
6.1 그림 과 관련 된 기본 개념
그림 은 결점 (정점) 의 유 궁 집합 V 와 변 의 유 궁 집합 E 로 구성 되 어 있다.변 은 정점 의 질서 있 는 짝 짓 기 이다. 만약 에 두 정점 사이 에 한 변 이 존재 한다 면 이 두 정점 은 서로 인접 한 관 계 를 가 진 다 는 것 을 나타 낸다.
방향 도: 방향 이 있다.변 을 호 라 고 부 르 고 화살 표를 포함 한 한 끝 을 호 두 라 고 부 르 며 다른 한 끝 을 호 미 라 고 부른다.
6.2 그림 의 저장 구조
인접 행렬: 정점 간 의 인접 관 계 를 나타 내 는 행렬, 그림 의 순서 저장 구조.설정 G = (V, E) 는 n 개의 정점 을 가 진 그림 이 고 G 의 인접 행렬 은 다음 과 같은 정 의 를 가 진 n 단계 방진 A: A [i] [j] = 1 은 정점 i 와 정점 j 의 인접 을 나타 낸다.A [I] [j] = 0 은 정점 i 와 정점 j 가 인접 하지 않 음 을 나타 낸다.무방 향도: 인접 행렬 은 대칭 적 이 고 i 행 이나 i 열의 원소 의 합 은 정점 i 의 도이 다.방향 도: i 줄 요소 의 합 은 i 의 출 도 이 고 j 열 요소 의 합 은 j 의 입 도 이다.
인접 표: 그림 의 체인 저장 구조.첫 번 째 노드 는 정점 에 관 한 정 보 를 저장 하고 나머지 는 가장자리 에 있 는 정 보 를 저장 합 니 다.

//      
typedef struct ArcNode {
    int adjvex;//       
    struct ArcNode *nextarc;//         
    int info;//   
} ArcNode;

//    
typedef struct VNode {
    char data;
    ArcNode *firstarc;//         
} VNode;

//   
typedef struct AGraph {
    VNode adjlist[maxSize];
    int n, e;
} AGraph;

[예 1]: 인접 표
6.3 그림 의 스 트 리밍 알고리즘
깊이 우선 검색 스 트 리밍 (DFS): 이 진 트 리 와 같은 우선 순위 스 트 리밍: 먼저 출발점 V 에 접근 하고 방문 한 것 으로 표시 한 다음 V 와 인접 하지 않 은 임의의 정점 W 를 선택 하고 접근 합 니 다.W 와 인접 한 방문 되 지 않 은 임의의 정점 을 선택 하고 방문 하 며 순서대로 반복 합 니 다.한 정점 에 모든 인접 정점 이 방문 되 었 을 때 근처에 방문 한 정점 을 차례대로 되 돌려 줍 니 다. 만약 에 이 정점 에 다른 인접 정점 이 방문 되 지 않 았 다 면 그림 의 모든 정점 이 방문 할 때 까지 반복 적 으로 진행 합 니 다.

int visit[maxSize];//          ，    0
/*
 * @param   g       The graph to be visited.
 * @param   v       The start point of the graph.
 * Using DFS to visit graph.
 */
void DFS(AGraph *g, int v) {
    ArcNode *p;
    visit[v] = 1;//  v   （  ）    
    Visit(v);//            
    p = G->adjlist[v].firstarc;//p  v     
    while(p != null) {
        //          
        if (visit[p->adjvex] == 0) {
            DFS(g, p->adjvex);
            p = p->nextarc;
        }
    }
}

[예 2]: DFS
범위 우선 검색 스 트 리밍 (BFS): 이 진 트 리 와 같은 차원 스 트 리밍 은 하나의 대기 열 로 이 루어 져 야 합 니 다. 1. 그림 의 정점 을 선택 하고 방문 한 후에 들 어가 서 방문 한 것 으로 표시 합 니 다.2. 대기 열 이 비어 있 지 않 을 때 순환 실행: 팀 을 나 가 고 팀 의 정점 에 있 는 모든 인접 정점 을 차례대로 검사 합 니 다.방문 되 지 않 은 모든 인접 지점 을 방문 하여 입단 시 키 기;3. 대기 열 이 비어 있 을 때 순환 을 뛰 어 내 려 범위 우선 검색 이 완료 되 었 습 니 다.

int visit[maxSize]//          ，    0
/*
 * @param   g       The graph to be visited.
 * @param   v       The start point of the graph.
 * Using BFS to visit graph.
 */
void BFS(AGraph *g, int v) {
    ArcNode *P;
    Queue  q;
    int temp;//         
    visit[v] = 1;
    Visit(v);
    q.initial();
    q.push(v);
    while(!q.empty()) {
        q.pop(temp);
        p = G->adjlist[temp].firstarc;//p           
        //p      ，         
        while(p != null) {
            if (visit[p->adjvex] == 0) {
                Visit(p->adjvex);
                visit[p->adjvex] = 1;
                q.push(p->adjvex);
            }
            p = p->nextarc;
        }
    }
}

【 예 3 】: BFS 가 인접 표를 이용 하여 그림 을 저장 할 때 두 가지 알고리즘 의 시간 복잡 도 는 O (n + e) 가 인접 행렬 을 이용 하여 저장 할 때 두 가지 알고리즘 의 시간 복잡 도 는 O (n ^ 2) 이다.
6.4 최소 대가 생 성 트 리 알고리즘
n 개의 결점 이 있 는 연통 도 생 성 트 리 는 원 그림 의 극소 연통 서브 맵 이 고 원 그림 의 모든 n 개의 결점 을 포함 하 며 그림 의 연결 을 유지 하 는 가장 작은 변 이 있다.[1] 여기 서 우 리 는 최소 생 성 트 리 를 만 드 는 두 가지 알고리즘 을 소개 한다. 프 림 알고리즘 과 크 루스 칼 알고리즘 이다.이 두 가지 알고리즘 은 대학원 과정 에서 사고 와 과정 을 비교 하고 코드 의 실현 방식 에 대한 고찰 이 많 지 않 기 때문에 나 무 를 만 드 는 과정 을 중점적으로 이해 해 야 한다. 여 기 는 코드 를 붙 이지 않 는 다.
프 림 알고리즘: 그림 에서 하 나 를 정점 으로 선택 하고 나무 로 삼 은 다음 에 이 나무 와 연 결 된 가장자리 에서 가장 짧 은 경로 (가중치 가 가장 작은) 의 가장 자 리 를 선택 하고 이 가장자리 와 연 결 된 정점 도 나무 에 합 쳐 서 그림 의 모든 정점 이 나무 에 합 쳐 질 때 까지 유추 합 니 다.[예 4]: 프 림 알고리즘 은 최소 생 성 트 리 크 루 스 칼 알고리즘 을 구 합 니 다. 한 마디 로 이 알고리즘 을 설명 합 니 다. 링 이 구성 되 지 않 은 상황 에서 매번 옵션 값 을 최소 화하 면 생 성 트 리 를 추가 합 니 다.[예 5]: 크 루스 칼 알고리즘 최소 생 성 트 리 구하 기
두 알고리즘 의 비교
6.5 최 단 경로 알고리즘
다른 정점 까지 의 가장 짧 은 경 로 를 구하 십시오. 디 제 스 트 라 알고리즘 과 프로 이 드 알고리즘 입 니 다.디 제 스 트 라 알고리즘: 정점 에서 다른 정점 까지 의 가장 짧 은 경 로 를 구하 세 요.(1) 초기 화: 기점 V 에서 이 정점 W 까지 의 직접 변 을 최 단 경로 로 초기 화하 고 그렇지 않 으 면 표시 로 설정 합 니 다.(2) 가장 짧 은 경 로 를 구하 지 않 은 종점 에서 경로 길이 가 가장 작은 종점 U 를 선택 하 십시오. 즉, V 에서 U 까지 의 가장 짧 은 경 로 를 구 하 는 것 입 니 다.(3) 최 단 경로 수정: U 의 인접 점 의 최 단 경 로 를 계산 하여 대체 합 니 다.(4) V 에서 나머지 모든 정점 까지 의 최 단 경 로 를 구 할 때 까지 상기 절 차 를 반복 한다.알고리즘 복잡 도: O (n ^ 2) [예 6]: 디 제 스 트 라 알고리즘 은 최 단 경로 dist [] 를 구 합 니 다. 현재 찾 은 출발점 V0 에서 다른 정점 Vi 까지 의 최 단 경로 길 이 를 저장 합 니 다.path []: 기점 V0 에서 다른 정점 Vi 의 가장 짧 은 경로 중 Vi 의 앞 정점 을 저장 합 니 다.상기 과정 에서 알 수 있 듯 이 정점 0 에서 정점 1 ~ 6 * * 최 단 경로 길이 * * 는 각각 4, 5, 6, 10, 9, 16 이다.
프로 이 드 알고리즘: 그림 에서 한 쌍 의 정점 사이 의 가장 짧 은 경 로 를 찾 습 니 다.(시험 을 볼 확률 이 크 지 않 고, 시험 을 봐 도 내용 과 형식 이 어렵 지 않다) (1) 행렬 A, Path 를 설정 하여 그림 의 인접 행렬 을 A 에 게 할당 하고 Path 를 모두 - 1 로 초기 화 합 니 다.(2) 정점 K 를 중간 정점 으로 J 는 0 ~ n - 1 (n 을 그림 의 정점 개수 로) 을 취하 고 그림 의 모든 정점 을 {i, j} 에 대해 다음 과 같이 검 측 하고 수정 합 니 다. 만약 에 A [i] [j] > A [i] [k] [j] 를 A [i] [k] + A [k] [j] 의 값 으로 바 꾸 고 Path [i] [j] 를 k 로 바 꿉 니 다.

/*            ，                  */
void Floyed(AGraph g, int A[][maxSize], int Path[][maxSize]) {
    int i, j, k;
    for (i = 0; i < g.n; i++) {
        for (j = 0; j < g.n; j++) {
            A[i][j] = g.edges[i][j];
            Path[i][j] = -1;
        }
    }
    for (k = 0; k < g.n; k++) {
        for (i = 0; i < g.n; i++) {
            for (j = 0; j < g.n; j++) {
                if (A[i][j] > A[i][k] + A[k][j]) {
                    A[i][j] = A[i][k] + A[k][j];
                    Path[i][j] = k;
                }
            }
        }
    }
}

6.6 토폴로지 정렬 과 관건 적 인 경로
AOV 네트워크: 정점 으로 활동 을 표시 하고 활동 의 선후 순 서 를 표시 하 며 회로 가 없 는 방향 도 를 나타 낸다.루프 없 는 그림 (DAG) 이 있 고 AOV 네트워크 는 토폴로지 정렬 을 합 니 다. 그림 의 모든 정점 을 선형 서열 로 배열 하여 그림 의 한 쌍 의 정점 U 와 V 를 만 듭 니 다. 만약 에 U 에서 V 까지 의 경로 가 존재 한다 면 토폴로지 정렬 서열 에서 반드시 U 가 V 앞 에 나타 날 것 입 니 다.만약 방향 이 있 는 그림 이 토폴로지 에 의 해 정렬 될 수 있다 면, 그것 은 틀림없이 방향 이 있 고 없 는 그림 일 것 이다.즉, 매번 입 도 0 의 정점 을 삭제 하고 출력 합 니 다. * *시간 복잡 도: * * O (n + e), n 은 정점 개수, e 대 표 변 의 개수 입 니 다.AOE 네트워크: 활동 을 표시 하면 서 가중치 가 있 고 활동 지속 시간 을 대표 합 니 다.관건 적 인 경로: 경로 길이 가 가장 긴 경로.[예 7]: 토폴로지 정렬 예 토폴로지 정렬 의 결 과 는 반드시 유일한 것 이 아니다. 예 를 들 어 ACBDE 도 상기 DAG 그림 의 토폴로지 질서 있 는 서열 이다.
관건 적 인 경로 알고리즘: 이벤트 (정점) i: 최초 로 이벤트 ve (i) 가 발생 하고 가장 늦게 발생 하 는 시간 vl (i) 활동 (변) a (i, j): 최초 로 시작 하 는 시간 e (e, j), 가장 늦게 시작 하 는 시간 l (i, j) (1) 은 토폴로지 에 따라 정점 을 질서 있 게 배열 합 니 다. 정점 토폴로지 에 대해 정렬 합 니 다.(2) 계산 ve (j): ve (1) = 0, ve (j) = max {ve (*) + a (*, j)}, 그 중 * 는 임의의 전구 이벤트 입 니 다.(3) 계산 vl (i): vl (n) = ve (n), vl (i) = min {vl (*) - a (i, *)}, 그 중 * 는 임의의 후계 이벤트 입 니 다.(4) 계산 e (i, j) 와 l (i, j): e (i, j) = ve (i), l (i, j) = vl (j) - a (i, j) (5) 공사 총 용 시 ve (n), 관건 적 인 활동 은 e (i, j) = l (i, j) 의 활동 은 a (i, j) [예 8]: 관건 적 인 경로 구법 공사 완공 에 15 가 필요 하고 관건 적 인 경 로 는 1 - > 2 - > 5 - > 6 - > 8 - > 9 이다.
참고 자료
1. 엄 울 민: 청화대학 출판사, 2011