Kalıp #20

Topolojik Sıralama

İleri

Her yönlü kenar erken → geç olsun diye düğümleri sırala.

Ne zaman kullanılır

Önkoşullar, derleme sırası veya herhangi bir DAG bağımlılık kısıtı.

Tanıma ipuçları

Ders programı / sıra
Alien dictionary
Indegree kuyruğu (Kahn) veya DFS postorder

Yaygın tuzaklar

Döngü tespit etmemek (eksik sıra)
Grafı yanlış yönde kurmak
Birden fazla geçerli sıra: belirtilmedikçe herhangi biri olur

90 saniyelik tanıma egzersizi

Hangisi en iyi uyuyor?

Ders programı / sıra
Alien dictionary
Indegree kuyruğu (Kahn) veya DFS postorder

Geri İzlemeHızlı ve Yavaş İşaretçiTopolojik SıralamaCevap Üzerinde İkili Arama

Etkileşimli

Zihinsel model

Değişmezin tam adım adım anlatımı. Duraklat, noktalara tıkla veya ← → kullan. Her adımı kendi cümlelerinle anlatmayı hedefle.

Adım 1 / 8

indegree A0 B1 C1 D2

Önkoşul grafı: A, B ve C'den önce; B ve C, D'den önce.

Nasıl düşünülür

DAG’ta indegree 0 düğümler önce gelebilir. Kahn: onları kuyruğa al, çıkar, komşuların indegree’sini azalt. n’den az düğüm çıkarırsan döngü vardır. DFS: çocukları gezdikten sonra düğümü öne ekle.

Şablon şekilleri

Şekil	Temel hamle	Notlar
Kahn BFS	Indegree + kuyruk	Sayıyla döngü tespit
DFS	Özyineleme renkleri	Postorder öne ekle
Sözlükçe en küçük	Kuyruk yerine min-heap	Belirleyici sıra

Karmaşıklık temeli

O(V+E) zaman ve alan.

Şablondan probleme

Komşuluk listesi ve indegree dizisi kur.
Tüm indegree 0’ı kuyruğa al.
Pop, sıraya ekle, komşuları azalt; 0 olursa kuyruğa.
order.length < n → döngü / imkânsız.

Şablon

TypeScript, Python ve C#’te aynı iskelet. Değişmezi uyarla; yapıyı koru.

Topolojik Sıralama · Şablon

/** Topo template: Kahn BFS; empty array if cycle. */
export function topoSort(n: number, edges: number[][]): number[] {
  const g: number[][] = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [u, v] of edges) {
    g[u!]!.push(v!);
    indeg[v!]++;
  }
  const q: number[] = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
  const order: number[] = [];
  while (q.length) {
    const u = q.shift()!;
    order.push(u);
    for (const v of g[u]!) if (--indeg[v]! === 0) q.push(v);
  }
  return order.length === n ? order : [];
}

/** Topo template: Kahn BFS; empty array if cycle. */
export function topoSort(n: number, edges: number[][]): number[] {
  const g: number[][] = Array.from({ length: n }, () => []);
  const indeg = new Array(n).fill(0);
  for (const [u, v] of edges) {
    g[u!]!.push(v!);
    indeg[v!]++;
  }
  const q: number[] = [];
  for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
  const order: number[] = [];
  while (q.length) {
    const u = q.shift()!;
    order.push(u);
    for (const v of g[u]!) if (--indeg[v]! === 0) q.push(v);
  }
  return order.length === n ? order : [];
}

Yol

Yola başla Problem tarayıcısında gör →

#ProblemTürZorlukBitti

1#207 Course ScheduleRehbermedium
2#210 Course Schedule IIRehbermedium
3#269 Alien DictionaryRehberhard
4#310 Minimum Height TreesRehbermedium
5#1136 Parallel CoursesRehbermedium
6#1203 Sort Items by Groups Respecting DependenciesRehberhard