13 · СВЯЗИ

Графы

Список смежности и visited превращают связи во множество достижимых вершин.

2 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Список смежности

graph := make([][]int, n)
graph[from] = append(graph[from], to)

Для плотного графа матрица проще, но требует O(V²) памяти.

Visited

seen := make([]bool, n)
seen[start] = true

Отмечай вершину перед рекурсией или enqueue.

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Число провинций

Запускаем DFS из каждой непосещённой вершины.

O(V²) time · O(V) space

solution.go

func findCircleNum(g [][]int) int {
    seen, count := make([]bool, len(g)), 0
    var dfs func(int)
    dfs = func(v int) {
        seen[v] = true
        for next, edge := range g[v] {
            if edge == 1 && !seen[next] { dfs(next) }
        }
    }
    for v := range g { if !seen[v] { count++; dfs(v) } }
    return count
}

ПРИМЕР РЕШЕНИЯ

Клонирование графа

Map связывает старый узел с уже созданной копией.

O(V + E) time · O(V) space

solution.go

func cloneGraph(node *Node) *Node {
    copies := map[*Node]*Node{}
    var clone func(*Node) *Node
    clone = func(n *Node) *Node {
        if n == nil { return nil }
        if copy, ok := copies[n]; ok { return copy }
        copy := &Node{Val:n.Val}; copies[n] = copy
        for _, next := range n.Neighbors { copy.Neighbors = append(copy.Neighbors, clone(next)) }
        return copy
    }
    return clone(node)
}

ПРИМЕР РЕШЕНИЯ

Путь между вершинами

DFS останавливается, как только достигает целевой вершины.

O(V + E) time · O(V + E) space

solution.go

func validPath(n int, edges [][]int, source, target int) bool {
    graph := make([][]int, n)
    for _, e := range edges {
        graph[e[0]] = append(graph[e[0]], e[1])
        graph[e[1]] = append(graph[e[1]], e[0])
    }
    seen := make([]bool, n)
    var dfs func(int) bool
    dfs = func(v int) bool {
        if v == target { return true }
        seen[v] = true
        for _, next := range graph[v] { if !seen[next] && dfs(next) { return true } }
        return false
    }
    return dfs(source)
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Ориентированный граф или нет
Возможны ли циклы
Нужен путь, число компонент или порядок