Основы графов
Что такое граф?
Граф — это структура, состоящая из вершин (nodes/vertices) и рёбер (edges), соединяющих эти вершины.
A --- B
| / |
| / |
C --- D
Здесь вершины: {A, B, C, D}, рёбра: {A-B, A-C, B-C, B-D, C-D}.
Типы графов
Направленный vs ненаправленный
Ненаправленный: Направленный:
A --- B A --> B
| | | ^
C --- D v |
C --> D
Взвешенный vs невзвешенный
Невзвешенный: Взвешенный:
A --- B A --5-- B
| | | |
C --- D 3 2
| |
C --4-- D
Циклический vs ациклический
Циклический: Ациклический (DAG):
A -> B A -> B
^ | |
| v v
D <- C C -> D
DAG (Directed Acyclic Graph) — направленный ациклический граф. Используется для зависимостей, расписаний, порядка компиляции.
Представление графов
Adjacency List (список смежности)
Каждая вершина хранит список своих соседей. Самое распространённое представление.
PHPGo
<?php
declare(strict_types=1);
// Associative array of lists
/** @var array<string, list<string>> */
$graph = [
'A' => ['B', 'C'],
'B' => ['A', 'C', 'D'],
'C' => ['A', 'B', 'D'],
'D' => ['B', 'C'],
];
// With weights
/** @var array<string, list<array{0: string, 1: int}>> */
$weightedGraph = [
'A' => [['B', 5], ['C', 3]],
'B' => [['A', 5], ['D', 2]],
'C' => [['A', 3], ['D', 4]],
'D' => [['B', 2], ['C', 4]],
];
// Dynamic addition
$graph = [];
$graph['A'][] = 'B';
$graph['B'][] = 'A';
package main
// Adjacency list using map of slices
graph := map[string][]string{
"A": {"B", "C"},
"B": {"A", "C", "D"},
"C": {"A", "B", "D"},
"D": {"B", "C"},
}
// With weights
type Edge struct {
To string
Weight int
}
weightedGraph := map[string][]Edge{
"A": {{"B", 5}, {"C", 3}},
"B": {{"A", 5}, {"D", 2}},
"C": {{"A", 3}, {"D", 4}},
"D": {{"B", 2}, {"C", 4}},
}
// Dynamic addition
graph = make(map[string][]string)
graph["A"] = append(graph["A"], "B")
graph["B"] = append(graph["B"], "A")
PHPGo
<?php
declare(strict_types=1);
// 0 = no edge, 1 = edge exists
// A B C D
// A [[0, 1, 1, 0],
// B [1, 0, 1, 1],
// C [1, 1, 0, 1],
// D [0, 1, 1, 0]]
/** @var list<list<int>> */
$matrix = [
[0, 1, 1, 0],
[1, 0, 1, 1],
[1, 1, 0, 1],
[0, 1, 1, 0],
];
// 0 = no edge, 1 = edge exists
// A B C D
// A [[0, 1, 1, 0],
// B [1, 0, 1, 1],
// C [1, 1, 0, 1],
// D [0, 1, 1, 0]]
matrix := [][]int{
{0, 1, 1, 0},
{1, 0, 1, 1},
{1, 1, 0, 1},
{0, 1, 1, 0},
}
PHPGo
<?php
declare(strict_types=1);
/** @var list<array{0: string, 1: string}> */
$edges = [
['A', 'B'],
['A', 'C'],
['B', 'C'],
['B', 'D'],
['C', 'D'],
];
// With weights
/** @var list<array{0: string, 1: string, 2: int}> */
$weightedEdges = [
['A', 'B', 5],
['A', 'C', 3],
['B', 'D', 2],
['C', 'D', 4],
];
type Edge struct {
From, To string
}
edges := []Edge{
{"A", "B"},
{"A", "C"},
{"B", "C"},
{"B", "D"},
{"C", "D"},
}
// With weights
type WeightedEdge struct {
From, To string
Weight int
}
weightedEdges := []WeightedEdge{
{"A", "B", 5},
{"A", "C", 3},
{"B", "D", 2},
{"C", "D", 4},
}
| Операция | Adj. List | Adj. Matrix | Edge List |
|---|---|---|---|
| Память | O(V + E) | O(V²) | O(E) |
| Проверить ребро (u,v) | O(degree) | O(1) | O(E) |
| Все соседи вершины | O(degree) | O(V) | O(E) |
| Добавить ребро | O(1) | O(1) | O(1) |
| Плотный граф (E ~ V²) | Неэффективно | Хорошо | Хорошо |
| Разреженный граф (E << V²) | Хорошо | Расточительно | Хорошо |
Построение графа из списка рёбер
PHPGo
<?php
declare(strict_types=1);
/**
* @param list<array{0: string, 1: string}> $edges
* @return array<string, list<string>>
*/
function buildGraph(array $edges, bool $directed = false): array
{
$graph = [];
foreach ($edges as [$u, $v]) {
$graph[$u][] = $v;
if (!$directed) {
$graph[$v][] = $u;
}
}
return $graph;
}
// LeetCode format: n vertices (0..n-1), list of edges
/**
* @param list<array{0: int, 1: int}> $edges
* @return list<list<int>>
*/
function buildFromEdges(int $n, array $edges): array
{
$graph = array_fill(0, $n, []);
foreach ($edges as [$u, $v]) {
$graph[$u][] = $v;
$graph[$v][] = $u;
}
return $graph;
}
func buildGraph(edges [][2]string, directed bool) map[string][]string {
graph := make(map[string][]string)
for _, e := range edges {
u, v := e[0], e[1]
graph[u] = append(graph[u], v)
if !directed {
graph[v] = append(graph[v], u)
}
}
return graph
}
// LeetCode format: n vertices (0..n-1), list of edges
func buildFromEdges(n int, edges [][2]int) [][]int {
graph := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
graph[u] = append(graph[u], v)
graph[v] = append(graph[v], u)
}
return graph
}
- Степень (degree) — количество рёбер, инцидентных вершине
- Для направленных: in-degree (входящие) и out-degree (исходящие)
PHPGo
<?php
declare(strict_types=1);
// Undirected: degree = count of neighbors
$degreeA = count($graph['A']); // 2
// Directed: compute in-degree
/** @return list<int> */
function computeInDegree(array $graph, int $n): array
{
$inDegree = array_fill(0, $n, 0);
for ($u = 0; $u < $n; $u++) {
foreach ($graph[$u] as $v) {
$inDegree[$v]++;
}
}
return $inDegree;
}
// Undirected: degree = count of neighbors
degreeA := len(graph["A"]) // 2
// Directed: compute in-degree
func computeInDegree(graph [][]int, n int) []int {
inDegree := make([]int, n)
for u := 0; u < n; u++ {
for _, v := range graph[u] {
inDegree[v]++
}
}
return inDegree
}
- Связный граф — из любой вершины можно попасть в любую другую
- Компоненты связности — максимальные связные подграфы
PHPGo
<?php
declare(strict_types=1);
function countComponents(int $n, array $edges): int
{
$graph = buildFromEdges($n, $edges);
$visited = [];
$count = 0;
$dfs = function (int $node) use (&$dfs, &$visited, $graph): void {
$visited[$node] = true;
foreach ($graph[$node] as $neighbor) {
if (!isset($visited[$neighbor])) {
$dfs($neighbor);
}
}
};
for ($i = 0; $i < $n; $i++) {
if (!isset($visited[$i])) {
$dfs($i);
$count++;
}
}
return $count;
}
func countComponents(n int, edges [][2]int) int {
graph := buildFromEdges(n, edges)
visited := make([]bool, n)
count := 0
var dfs func(node int)
dfs = func(node int) {
visited[node] = true
for _, neighbor := range graph[node] {
if !visited[neighbor] {
dfs(neighbor)
}
}
}
for i := 0; i < n; i++ {
if !visited[i] {
dfs(i)
count++
}
}
return count
}
Итоги
- Граф = вершины + рёбра
- Типы: направленный/ненаправленный, взвешенный/невзвешенный
- Adjacency List: O(V+E) памяти, оптимален для разреженных
- Adjacency Matrix: O(V^2), оптимален для плотных
- Связность: DFS/BFS для подсчёта компонент
- DAG: направленный ациклический, для зависимостей