(9) 기본 적 인 그림 알고리즘

그림 의 표시
그림 의 기 호 는 G = (V, E) 로 두 가지 데이터 구조 로 인접 링크 와 인접 행렬 을 표시 할 수 있다.

note: 실제 응용 에 서 는 보통 하나의 Vertex V [VNUM] 1 차원 배열 로 노드 를 저장 하고 2 차원 행렬 w [VNUM] [VNUM] 또는 인접 링크 로 가중치 를 저장 해 야 합 니 다.

인접 링크

구성: | V | 체인 테이블 로 구 성 된 수조 Adj, 그 중 어느 결점 의 체인 테이블 은 Adj [u] 이다.

저장 공간: | V | 링크 가 있 습 니 다.Θ(V), 이 링크 의 결산 점 을 합치 면 모두 | E | 줄 또는 | 2E | 개의 결산 점 이 있어 야 합 니 다. 그러면...Θ(E) 그래서 합치 면Θ(V+E);

장점: 인접 링크 가 비교적 치밀 하고 공간 을 절약 하 며 희소 도 (E 는 V ^ 2 보다 훨씬 작 음) 에 적합 하기 때문에 대부분 알고리즘 은 그림 이 인접 링크 로 표시 된다 고 가정 합 니 다.

단점: u, v 두 노드 사이 에 변 (u, v) 이 있 는 지 신속하게 판단 할 수 없고 Adj [u] 에서 링크 를 검색 할 수 밖 에 없습니다.

인접 행렬

구성: | V |× |V | 행렬 은 두 결점 사이 의 변 의 상황 을 나타 낸다.

저장 공간:Θ(V^2)

장점: 조밀도 (E 는 V ^ 2 에 가깝다) 상황 에서 인접 행렬 이 더욱 좋다.인접 행렬 은 임의의 두 노드 사이 에 가장자리 가 있 는 지 신속하게 판단 하 는 수 요 를 만족 시 킬 수 있다.

단점: 더 큰 저장 공간 이 사라 지고 한 단계 높 아 졌 다.

범위 우선 검색 (BFS)
알고리즘

BFS(G, s)
/*   */
for each vertex u ∈ G.V - {s}
    u.color = white;
    u.pr = null;
    u.d = ∞;
s.color = gray;
s.pr = null;
s.d = 0;
Q = ∅;  //Queue is empty;
Enqueue(Q, s);
/*  */
while (Q != ∅) 
    u = Dequeue(Q);  //take u off from queue head;
    for each v of G.Adj[u]
        if (v.color == white) 
            v.color = gray;
            v.pr = u;  
            v.d = u.d+1;
            Enqueue(Q, v);  //push v into the queue tail;
    u.color = black;  //u's job is done;

알고리즘 운행 시간 분석:

초기 화 단계:Θ(V);

while 순환 에서 모든 노드 가 한 번 씩 팀 을 나 가 야 하고 모든 노드 가 그의 변 을 탐지 해 야 한다. 그러면 방향 도, 즉 V 개의 노드 로 모두 E 개의 변 을 탐지 하 는 데 시간 이 걸린다.Θ(V+E);

BFS 성질: 그 알고리즘 은 임의의 결점 의 최 단 경로 거 리 를 정확하게 계산 할 수 있다.δ
(1) 최 단 경로 거리 성질: 변 (u, v) 8712 ° E, 있 음δ(s, v) ≤ δ(s, u)+1;
증명: 만약 에 s 가 u 에 도착 할 수 있 고 v 에 도착 할 수 있 으 며 변 (u, v) 이 존재 한다 면 s 에서 v 까지 의 가장 짧 은 경로 거 리 는 s 에서 u 까지 의 가장 짧 은 경로 와 변 보다 더 길 수 없다.s 가 u 에 도착 하지 못 하면,δ(s, u) = ∞, 그러면 성질 도 성립 된다.
이어서 BFS 가 계산 한 v. d 를 증명 하기 위해 =δ(s, v), 우 리 는 먼저 v. d ≥, 재 증 ≤;
(2) BFS 가 계산 한 v. d ≥δ(s, v);
증명: (수학 귀납법, 전 과정 관찰) ① 초기 화 시: for s, s. d =δ(s,s) = 0; for each v∈G.V - {s}, v.d = ∞ >= δ(s, v); ② BFS 연산 시: assume u has u. d > =δ(s, u). when u just does its dequeue, then we see that for edge(u, v), the BFS algorithm says v.d = u.d+1 ≥ δ(s, u)+1 [this is our assumption] ≥ δ(s, v) [cuz edge(u,v)exists, and we have property (1)]. And after this operation, node v's color turns gray and v.d no longer changes. Thus we prove our property(2).
(3) BFS 중대 열 에 대열 에 최대 두 개의 서로 다른 d 값 이 포함 되 어 있 고 팀 의 d 값 은 오름차 순 (v [i]. d < = v [i + 1]. d) 을 유지 합 니 다.
증명: (수학 귀납법) - 머리 조건: s 만 팀 에 있 을 때 s. d = 0 만 있 고 정리 만족;s 가 팀 을 떠 난 후에 팀 에 결점 을 추가 하 는 단계 에 추 가 된 모든 s. adj 결점 은 v. d = 1 이 고 정리 도 만족 합 니 다. 즉, v [1] 가 팀 을 떠 나 기 전에 v [r] d = v [1] d = 1 < = v [1]. d + 1 과 v [i] d = v [i + 1] d = 1 < = v [i + 1] d 를 만족 시 켰 습 니 다.원래 v [1] 가 팀 을 떠 난 후에 팀 에 새로운 결산 점 을 추가 하 는 단 계 는 모두 v. d = 원래 v [1]. d + 1 = 2 < = v [2]. d + 1 을 만족 시 킵 니 다. 우 리 는 원래 의 v [2] 를 새로운 v [1] 로 봅 니 다. 즉, v [r]. d < = 새로운 v [1]. d + 1 이 설립 되 었 습 니 다.그리고 우 리 는 현재 v [1] ~ v [k] 에 d = 1, v [k + 1] ~ v [r] 에 d = 2 가 있다 는 것 을 알 고 있 기 때문에 반드시 v [i]. d < = v [i + 1]. d 가 있다.귀납 단계: u 가 팀 을 떠 나 기 전에 정 리 는 만족 하 다 고 가정 하고 u 를 v [1], 즉 v [r]. d < = v [1]. d + 1 로 기록한다.동시에 v [i]. d < = v [i + 1]. d 도 성립 된다 고 가정 하면 v [1]. d < = v [2]. d 가 있다.
u 가 팀 에서 나 와 팀 에 요 소 를 추가 할 때 새로 가입 한 노드 마다 v. d = u. d + 1 < = 원 v [2]. d + 1 이 있 고 원 v [2] 를 새로운 v [1] 로 기록 하면 v [r]. d < = v [1] + 1 이 아직도 성립 된다.두 번 째 가설 을 보고 대열 의 원래 부분 에 대해 계속 성립 한다.대기 열 에 원래 와 새로운 부분 이 교차 하 는 곳 에 대해 원래 v [r]. d < = 원 v [1]. d + 1 < = 원 v [2] + 1, 현재 새로 가입 한 v = u + 1 = 원 v [1]. d + 1 > = 원 v [r]. d 를 알 고 있 기 때문에 인수 부분 도 v [i] < = v [i + 1] 가 성립 됩 니 다.그리고 새로운 추가 부분 에 대해 서 는 v [i] = v [i + 1] 이 있 고 v [i] < = v [i + 1] 에 부합 합 니 다.종합 적 으로 초기 조건 과 귀납 단계 가 모두 성립 되 기 때문에 정리 가 성립 된다.
(4) BFS 가 구 한 v. d =δ(s, v) 모든 v * 8712 ° V 는 s 가 BFS 알고리즘 을 통 해 발견 한 결점, 즉 s 가 모든 v 에 도달 할 수 있다 는 것 을 알 고 있 습 니 다.
증명: (반증 법) v. d 가 존재 한다 고 가정 합 니 다! =δ(s, v), v. d > =δ(s, v) 정리, v. d >δ(s,v); 그러면 이러한 존 재 는 두 가지 상황 이 있 습 니 다. 그림 에 일부 결점 이 있 는 v. d >δ(s, v) 그림 의 모든 노드 에 v. d > 가 있 거나δ(s, v). - 후 자 는 분명히 불가능 하 다. 왜냐하면 적어도 변 (s - > a) 은 a 결점 을 a. d = 에 만족 시 킬 수 있 기 때문이다.δ(s, a); --전자의 상황 을 보면 s 가 출발 하 는 한 경로 에서 u 이전의 결점 은 정상 이 고 v 부터 뒤의 결점 은 모두 v. d > 가 나 타 났 다.δ(s, v) 그 유일한 가능성 은 결점 v 가 다른 더 짧 은 경로 로 연결 되 었 기 때 문 입 니 다. 이 때 는 BFS 알고리즘 이 가장 짧 은 경로 보다 더 빨리 추진 되 었 다 는 것 을 의미 합 니 다. 그들의 머리 는 모두 회색 입 니 다. 이것 은 대열 d 값 과 같은 시간 에 두 개 만 유지 하 는 것 과 모순 입 니 다. - - 이렇게 증명 할 수 있 습 니 다. s 에서 v 까지 의 가장 짧 은 경로 에서 앞의 결점 은 x 입 니 다.그러면 x. d =δ(s, x), 그리고δ(s, v) = δ(s, x) + 1 (이것 이 가장 짧 은 경로 라 고 명 확 히 밝 혔 습 니 다), v. d >δ(s, v) = δ(s, x) + 1 = x. d + 1. 이것 은 바로 우리 가 상술 한 v 가 더 긴 경로 에서 먼저 탐색 되 는 문제 이다. 우 리 는 x 탐색 의 측면 에서 볼 때 왜 이것 이 불가능 한 지 알 아 보 자. 만약 에 x 에서 v 를 탐색 할 때 v 가 흰색 이 라면 v. d = x. d + 1, 모순;만약 에 v 가 검은색 이 고 이때 x 가 회색 이 라면 v 가 x 보다 먼저 팀 을 나 가 야 한 다 는 것 이다. 그러면 v. d < = x. d, 모순;만약 에 v 가 회색 이 라면 v 는 특정한 결점 u 에 의 해 먼저 탐색 되 었 을 것 이다. 그러면 u 는 x 보다 먼저 대열 에 들 어가 u. d < = x. d 를 만족 시 켰 다. 그러면 v. d = u. d + 1 < = x. d + 1, 모순;종합 하면 BSF 알고리즘 에서 감지 할 수 있 는 모든 노드 v, v. d =δ(s, v) 반드시 성립 된다.
깊이 우선 검색

DFS(G) {
/*   */
for each vertex u in G.V
    u.color = white
    u.pr = null;
time = 0  //init time;
for each vertex u in G.V
    if (u.color == white)
        DFS-Visit(G, u);
}

DFS-Visit(G, u) {
time = time+1;
u.d = time;
u.color = gray;
for each v of G.Adj[u]
    if v.color == white
        v.pr = u
        DFS-Visit(G, v);
u.color = black;
time = time+1;
u.f = time;
}

알고리즘 운행 시간 분석:

-        : Θ(V);
-               , Θ(V);    vertex        ,      Edge    , Θ(E);
-   Θ(V+E);

DFS 의 중요 성

괄호 화: 두 개의 결점 u, v 에 있어 세 가지 가능성 만 있다. 구간 분리, 구간 u 는 v 를 포함 하고 구간 v 는 u 를 포함한다.

흰색 경로: v 는 u 의 후손 이다.↔ u 를 발 견 했 을 때 u. d 는 결점 u 에서 v 까지 의 모든 흰색 결점 으로 구 성 된 경로 가 존재 할 수 있다.

변 의 분류: 처음 변 (u, v) 을 탐색 할 때 v 는 흰색 - > 나무 변 이다.v. 회색 - > 뒤로 가기;v. 검은색 - > 앞 방향 또는 가로 방향;

토폴로지 정렬

Topological-sort(G)
count finish time for each vertex using DFS(G);
once a vertex is finished (marked black), insert it into the linkedList;
return the linkedList

토폴로지 순서 정의: 그림 G 가 변 (u, v) 을 포함 하면 u 결점 은 순서 에서 항상 v 결점 앞 에 있다.

이 정 의 는 그림 G 가 토폴로지 순 서 를 생 성 할 수 있다 면 반드시 방향 무 환 도 가 있어 야 한다.

증명: (반증 법) 링 이 있 으 면 u - > v 도 있 고 v - > u 도 있다. 그러면 토폴로지 에서 u 결점 이 v 앞 에 있 는 것 을 만족 시 킬 수 없고 v 결점 이 u 앞 에 있 는 것 을 만족 시 켜 갈등 을 형성 할 수 없다.

TS 알고리즘 의 정확성: 방향 무 환 도 에 대해 TS 알고리즘 은 토폴로지 정렬 을 생 성 할 수 있 습 니 다.

증명: 우리 알고리즘 의 두 번 째 행사 반환 서열 은 종료 시간 f 의 역순 에 따라 배열 되 기 때문에 만약 에 변 (u, v) 이 G 그림 에 존재 한다 면 u. f > v. f 가 성립 된다 는 것 을 증명 하면 된다.(분류 토론) DFS 성질 중 변 의 분 류 를 이용 하여 G 에 존재 하 는 임의의 변 (u, v) 에 대해 토론 한다. 만약 에 이 변 이 DFS 에서 탐색 되 었 을 때 (1) v 결점 이 회색 이면 후 향 변 이 고 주어진 방향 무 환 도 조건 과 모순 (후 향 변 회 형 고리) 이 있 기 때문에 존재 할 수 없다.(2) 만약 에 v 결점 이 흰색 이 라면 이것 은 나무 옆 이 고 흰색 경로 로 정리 되 며 v 는 u 의 자 결점 이 고 괄호 화 정리 로 u. f > v. f 를 알 고 명제 가 성립 된다.(3) 만약 에 v 결점 이 검은색 이 라면 이것 은 전방 향 변 또는 가로 변 이다. 이때 v 결점 은 시간 도장 을 찍 었 고 u 가 끝나 지 않 았 다. 그러면 u. f > v. f 가 성립 되 고 명제 도 성립 된다.따라서 전제조건 이 무 환 도 에 성립 되면 TS 알고리즘 은 항상 토폴로지 순 서 를 생 성 할 수 있다.
강 한 연결 분량 (Strongly connected components)

Strongly-connected-components(G)
1. call DFS(G) to compute finish time for each vertex in the graph;
2. compute G (reverse the direction of all edges);
3. call DFS(G),  but from latest finish time to earliest at the main loop;
4. the trees that formed by second DF, are the components we look for;

정확성 증명:
(1) C 와 C ', 만약 u - > u' 가 있다 면 v '- > v 가 있 을 수 없다. 만약 에 실현 할 수 있다 면 이 두 가지 분량 의 임 의 요소 가 서로 상대방 에 게 도달 할 수 있 기 때문에 C 와 C' 는 한 분량 으로 합 칠 수 있다.
(2) C 와 C, u - > u 가 있다 면 f (C) 는 f (C) 입 니 다.
증명: (분류 토론) DFS 가 C 의 x 노드 에서 시작 하면 마지막 으로 x. f > max {Cnodes. f} 이면 f (C) > f (C);DFS 가 C '의 y 노드 에서 먼저 시작 하면 먼저 visit C' 의 결산 점 이 고 C '가 C 에 도착 하지 못 한 후에 DFS 가 C 에 대해 연산 을 시작 하면 f (C) > f (C) 를 얻 을 수 있 습 니 다.G 에 대해 동 리 는 성립 된다.
(3) SCC 알고리즘 은 G 를 얻 을 수 있다.
증명: 각 구 한 분량 을 n 개의 결점 으로 볼 수 있 습 니 다. 만약 에 알고리즘 세 번 째 줄 에서 G 에 대해 DFS 연산 을 하면 n 개의 독립 된 나무 가 충분 한 숲 을 형성 할 수 있다 면 알고리즘 은 정확 합 니 다. 수학 귀납법: 알고리즘 세 번 째 줄 의 조작 은 토폴로지 순서 (C. f > C '. f, C 앞) 에 따라 n 개의 결점 에 대해 DFS 를 진행 하 는 것 입 니 다. 여기 서 G 중의 모든 변 이 역방향 이 되 었 음 을 주의 하 십시오.
a. n = 1 일 때 숲 은 나무 한 그루 만 있 고 명제 가 성립 된 것 이 분명 하 다.b. n > 1 이 라 고 가정 할 때 일반적으로 토폴로지 순서 중의 C 와 C '에 대해 C 에 대해 DFS 를 먼저 진행 하면 C 는 토폴로지 순서 의 다음 결점 C' (G 에서 C - > C ', 그러나 이미 역방향 되 었 다) 가 없 기 때문에 C 는 단독으로 나무 가 되 었 고 DFS 는 C 에서 의 연산 은 C' 에 대해 어떠한 조작 도 하지 않 습 니 다. 이런 식 으로 유추 하면 알고리즘 은 n 개의 독립 된 나 무 를 연속 으로 생 성 할 수 있 습 니 다.