그림 이론 - 생 성 트 리

최소 생 성 트 리
욕심 에 기초 한 두 가지 알고리즘 을 자주 사용한다.
Prim
Dijksrta 에서 단원 의 가장 짧 은 경 로 를 구 하 는 과정 과 유사 합 니 다.매번 방문 한 결점 에서 나무의 거리 결점 이 가장 작은 결점 을 선택 하고 다른 결점 에서 나무의 결점 까지 의 거 리 를 업데이트 하 며 모든 결점 이 접근 할 때 까지 이 과정 을 반복 한다 (즉, 나무 한 그루 가 생 성 된다).보통 1, 1, 1 을 초기 결산 점 으로 한다.

int dis[N], G[N][N];
bool vis[N];

int Prim() {
  int mst = 0;
  memset(dis, 0x3f, sizeof(dis)), dis[1] = 0;
  for (int k = 1; k <= n; ++k) {
    int u = 0;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && dis[u] > dis[i]) u = i;
    vis[u] = true;
    mst += dis[u];
    for (int v = 1; v <= n; ++v)
      dis[v] = min(dis[v], G[u][v]);
  }
  return mst;
}

시간 복잡 도 O (n 2) O (n ^ 2) O (n2).
최적화 하 다.
Dijkstra 와 같이 매번 d i s dis dis 의 가장 작은 노드 를 찾 는 과정 은 더미 나 선분 트 리 등 데이터 구조 로 최적화 할 수 있 습 니 다. 여기 서 최적화 코드 를 드 립 니 다.

int dis[N], G[N][N];
bool vis[N];
priority_queue<pair<int, int>,
  vector<pair<int, int> >, greater<pair<int, int> > > Q;

int Prim() {
  int mst = 0;
  memset(dis, 0x3f, sizeof(dis)), dis[1] = 0;
  Q.push(make_pair(0, 1));
  while (!Q.empty()) {
    int u = Q.top().second; Q.pop();
    if (vis[u]) continue;
    vis[u] = true;
    mst += dis[u];
    for (int v = 1; v <= n; ++v)
      if (dis[v] > G[u][v]) {
        dis[v] = G[u][v];
        Q.push(make_pair(dis[v], v));
      }
  }
  return mst;
}

시간 복잡 도 O (m log ⁡ n) O (m \ \ log n) O (mlogn)
Kruskal
Kruskal 알고리즘 은 최소 생 성 트 리 에 끝 을 붙 이 는 과정 으로 볼 수 있 습 니 다.알고리즘 프로 세 스 는 다음 과 같 습 니 다.

그림 의 모든 변 수 를 가중치 에 따라 작은 것 에서 큰 것 으로 정렬 하여 각 노드 가 있 는 집합 을 초기 화 합 니 다.

각 변 을 순서대로 고려 하고 이 변 의 두 점 u u, v v v 가 같은 집합 에 없 으 면 이 변 을 최소 생 성 트 리 에 넣 고 u u, v v 가 있 는 집합 을 합 친다.

n - 1 n - 1 n - 1 변 을 선택 할 때 까지 이 과정 을 반복 한다.시간 복잡 도 O (m log ⁡ m) O (m \ log m) O (mlogm).

최소 생 성 숲
k k 그루 나무 가 있 는 최소 생 성 트 리 숲 에 대해 서도 Kruskal 알고리즘 을 사용 할 수 있 습 니 다.최소 생 성 트 리 의 절차 와 차이 점 은 종료 조건 을 n - k n - k - k 변 으로 바 꾸 는 것 이다.
Kruskal 재 구성 트 리
지금
성질
회로 성
원본 그림 에서 링 을 선택 하면 링 의 가중치 가 가장 큰 변 은 최소 생 성 트 리 에 나타 나 지 않 습 니 다.
절단 성
노드 를 S 와 T 두 부분 으로 나 누고 S 와 T 를 연결 하 는 모든 변 에서 변 권 이 가장 작은 것 은 반드시 최소 생 성 트 리 에 나타 납 니 다.
차 소 생 성 트 리
절단 성질 에서 결론 을 얻 을 수 있 듯 이 차 소 생 성 나무 와 최소 생 성 나 무 는 한 변 의 차이 만 있다.그래서 먼저 최소 생 성 트 리 를 구하 고 모든 비 트 리 변 (u, v) (u, v) (u, v), w (u, v) w (u, v) w (u, v) w (u, v) 로 u u u 에서 v v v v 의 최대 변 을 교체 합 니 다.이 과정 은 나무 위 에서 배로 늘 려 최적화 할 수 있다.총 시간 복잡 도 O (m log ⁡ n + m log ⁡ m + mα ( n ) ) O(m \log n + m \log m + m \alpha(n)) O(mlogn+mlogm+mα(n))。
최 단 경로 트 리
네 거 티 브 링 이 없 는 그림 에 대해 하나의 소스 를 선택 하고 이 소스 는 각 점 의 가장 짧 은 경로 로 나 무 를 구성 합 니 다.
Prufer 수열
Prufer 수열 은 뿌리 없 는 나무의 수열 로 n n 개의 결점 이 있 는 나무 에서 전 환 된 Prufer 수열 의 길 이 는 n - 2 n - 2 n - 2 이다.
뿌리 없 는 나무 회전 Prufer 수열
n n 개의 결점 이 있 는 뿌리 없 는 나무 에 대해 서 는 반복 적 으로 삭제 하 는 방식 으로 Prufer 수열 을 구 할 수 있 습 니 다.절 차 는 다음 과 같다.

잎 결점 중 번호 가 가장 작은 결점 을 찾 아 그것 과 연 결 된 가장 자 리 를 삭제 하고 이 가장자리 에 연 결 된 다른 결점 을 Prufer 수열 에 추가 합 니 다.

상기 절 차 를 반복 하여 원 그림 에 두 개의 결점 만 남 을 때 까지 한다.

Prufer 수열 회전 뿌리 없 는 나무
{a n - 2} \ {a {n - 2} \ \} {an - 2} 을 한 나무의 Prufer 수열 로 설정 하고 {G n} \ {G n \} 을 점 집합 으로 설정 하면 Prufer 수열 을 뿌리 없 는 나무 로 변환 하 는 절 차 는 다음 과 같 습 니 다.

{G n} \ {G n \} {Gn} 에 {a n - 2} \ \ {a {n - 2} 에 나타 나 지 않 은 최소 수 를 찾 아 {a n - 2} \ {a n - 2} \ \ {a {n - 2} 의 첫 번 째 항목 과 연결 시 키 고 이 점 을 {a n - 2} \ {a n - 2} 의 첫 번 째 항목 과 삭제 합 니 다.

나무 한 그루 가 생 성 될 때 까지 상기 절 차 를 반복 한다.

Prufer 수열 의 응용
주어진 조건 을 만족 시 키 는 생 성 트 리 가 모두 몇 가지 인지 알 아 보 는 데 사용 할 수 있다.
생 성 트 리 개수
매트릭스 트 리 정리
지금 은...
완전 그림 생 성 트 리
n n 개의 결점 이 있 는 완전한 그림 으로 n - 2 n ^ {n - 2} n - 2 그루 의 생 성 나무 가 있 습 니 다.한 그루 의 생 성 트 리 가 하나의 prufer 수열 에 대응 하기 때문에 prufer 수열 은 n - n - 2 n ^ {n - 2} n - 2 개 이기 때문에 n - n - 2 n ^ {n - 2} n - 2 그루 의 생 성 트 리 가 있 음 을 증명 합 니 다.