Apakah graf berwajaran dan graf terarah, dan masalah apa yang mereka modelkan?

Question

IT Interview Practice · Accepted Answer

Dalam graf **terarah** (digraph), tepi memiliki **arah** (`A → B` ≠ `B → A`). Dalam graf **berwajaran**, setiap tepi membawa **biaya numerik** (jarak, waktu, kapasitas). Menggabungkan keduanya memodelkan sistem nyata di mana hubungan adalah satu arah dan memiliki biaya.

## Representation

```text
Weighted directed graph:
  A --5--> B
  A --2--> C
  C --1--> B
Adjacency list with weights:
  A: [(B,5), (C,2)]
  B: []
  C: [(B,1)]
```

```python
graph = {
    'A': [('B', 5), ('C', 2)],   # directed, weighted edges
    'B': [],
    'C': [('B', 1)],
}
# Shortest A->B is A->C->B = 2 + 1 = 3, not the direct edge 5.
```

## What they model

| Domain | Vertices | Weighted directed edges |
|---|---|---|
| Maps / GPS | intersections | one-way roads + travel time |
| Networks | routers | links + latency/bandwidth |
| Task scheduling | tasks | dependencies + durations |
| Finance | currencies | exchange rates |

## Key algorithms

| Goal | Algorithm | Complexity |
|---|---|---|
| Shortest path (non-negative weights) | Dijkstra | O((V+E) log V) |
| Shortest path (negative edges) | Bellman-Ford | O(VE) |
| Ordering with dependencies | Topological sort | O(V+E) |
| Detect cycles / reachability | DFS | O(V+E) |

## Mengapa Penting

Arah dan bobot adalah apa yang mengubah graf abstrak menjadi model setia dari masalah perutean, penjadwalan, dan ketergantungan yang mendorong aplikasi nyata.

Pilihan algoritma bergantung pada properti ini — misalnya, bobot negatif mengecualikan Dijkstra dan memerlukan Bellman-Ford.

Domain	Vertices	Weighted directed edges
Maps / GPS	intersections	one-way roads + travel time
Networks	routers	links + latency/bandwidth
Task scheduling	tasks	dependencies + durations
Finance	currencies	exchange rates

Goal	Algorithm	Complexity
Shortest path (non-negative weights)	Dijkstra	O((V+E) log V)
Shortest path (negative edges)	Bellman-Ford	O(VE)
Ordering with dependencies	Topological sort	O(V+E)
Detect cycles / reachability	DFS	O(V+E)

Representation

What they model

Key algorithms

Mengapa Penting

Soalan berkaitan