주리 알고리즘 4 -- 도 론

1. 그림 정의

사물 간 의 관 계 를 묘사 하 다

결점 집합 V = {v1, v2,..., vn}

변 집합 E = {e1, e2,..., em}, 그 중 ei = (vi, vi '). G =

방향 도

공간 복잡 도: O (n + m) 또는 O (n 2)

인접 행렬 인접 표

2. 토폴로지 정렬
2.1 정의

유향 무 환 도 (DAG)

장면: 퀘 스 트 의존

시간 복잡 도 O (n + m)

부가 공간 복잡 도 O (n)

매번 0 의 점 을 찾는다

유지 보수 입도

2.2 과정
2.3 응용

당신 에 게 임무 가 있다 고 가정 하고 이 임무 들 간 의 의존 관계

퀘 스 트 마다 완료 시간 이 하나씩 있 습 니 다 Ti

무한 병행 이 가능 하 다 고 가정 하면 최소 얼마나 걸 려 야 완성 할 수 있 습 니까?

2.4 작업

Leetcode 207. Course Schedule

3. 최 단 로 (Dijkstra, Floyed)
3.1 정의

E 집합 (변 집) 이 가중치 라 고 가정

구상 V 집합 은 도시 E 집합 을 대표 하고 도시 간 고속도 로 를 대표 하 며 가중치 는 고속도로 길이

이다.

두 점 사이 에 몇 개의 통로 가 존재 한다

길이 가 가장 짧 은 통로 - > 최 단 로

3.2 단원 최 단 로

주어진 기점 s, 임의의 지점 의 최 단 로 (Dijkstra)

욕심: 가장 가 까 운 점 을 찾 을 때마다

점 당 거리 까지 s 유지

부분 최 우수 는 전체 국면 최 우수

와 같다.

시간 복잡 도 O (n 2)

부가 공간 복잡 도 O (n)

Q = {}
d[s] = 0,         
while (|Q| < |V|)
      Q     d[i]
  for (i    j，j   Q) 
    d[ j] = min(d[ j], d[i] + c[i][ j])//     
  Q = Q + {i}

3.3 단원 최 단 로 작업

변 권 이 마이너스 일 수 있 습 니까?

마이너스 회로 가 존재 할 수 있 습 니까?

하나의 Dijkstra

실현

프 림 알고리즘 (최소 생 성 트 리) 과 의 차이 비교

m < n 2 (희소 도) 시 어떻게 최적화 할 것 인 가 를 생각한다

더미 최적화

3.4 단일 소스 단락

출발점 s 를 정 하고 임 의적 인 단락 (거리 가 가장 짧 은 길 보다 큰 가장 짧 은 길)

을 구한다.

v 의 차 단락: 정점 u 의 최 단 로 에 u - > v 의 변 정점 u 의 차 단락 에 u - > v 의 변

원래 코드 에 단락 을 추가 하면 됩 니 다

3.5 임의의 두 점 최 단 로

임 두 점 간 최 단 로 (Floyed)

유사 한 동적 계획: 매번 한 점 씩 가입

임의의 두 점 사이 의 거 리 를 유지 합 니 다

시간 복잡 도 O (n 3)

부가 공간 복잡 도 O (n 2)

for i := 1 to n do 
  for j := 1 to n do 
    read(f[i, j]); 
for k := 1 to n do 
  for i := 1 to n do 
    for j := 1 to n do 
      f[i, j]= min(f[i, j], f[i, k] + f[k, j]);

3.6 사고
변 권 은 마이너스 가 될 수 있 습 니까? 마이너스 회로 가 존재 할 수 있 습 니까? N 차 dijkstra = Floyed?
4. 최소 생 성 트 리

무방 향도

나무 - > 무 환 (권). 파 권법, 피 권법

Prime 시간 복잡 도 O (n ^ 2)

SPFA(Bellman-Ford)

Q={s} 
While not empty(Q) 
  u = dequeue(Q) 
  for v ∈ adj[u] 
    if d[u] + g[u, v] < d[v] 
      d[v] = d[u] + g[u, v] 
      if not v in Q 
        enqueue(v);

레 퍼 런 스

1) 면접 구직 4 기

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

다양한 언어의 JSON

JSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

주리 알고리즘 4 -- 도 론

좋은 웹페이지 즐겨찾기