Что такое граф? Приведите примеры и способы представления в коде.

Так, слушай, смотри, я тебе сейчас про графы расскажу, но не так, как эти зануды в учебниках. Представь себе, что граф — это типа такая всратая тусовка.

Вот есть у тебя куча народу — это вершины, они же узлы. А рёбра — это когда они друг с другом знакомы, или один другому должен денег, или они просто переписываются. Вот и вся, блядь, философия.

Какие они бывают, эти графы-уроды:

• Неориентированный: Это когда вы с соседом по даче просто здороваетесь. Он тебе «привет», ты ему «привет». Всё панибратски, на равных. Как друзья вконтакте, только без подколов.
• Ориентированный (орграф): А это уже пошла политика. Ты можешь подписаться на какую-нибудь блогершу, а она на тебя — хуй с горы. Направление есть. Как в твиттере — лайкнул, а тебя в ответ послали нахуй.
• Взвешенный: Это когда не просто «знаком», а ещё и с цифрами. Например, расстояние от твоего дома до ближайшего ларька с пивом — 500 метров, а до работы — 15 километров, и вес этого ребра — твоё ебаное нежелание туда тащиться.

Как эту хуйню в коде хранить? Два главных способа, как жить: на широкую ногу или по-скромному.

1. Матрица смежности. Представь таблицу, как в экселе, огроменную. Если твой друг №3 знаком с другом №7, то на пересечении строки 3 и столбца 7 ставишь единичку (или вес, если взвешенный). Подходит, когда у тебя народу немного, но они все друг друга знают, как в деревне. Пиздец как накладно по памяти, если народу овердохуища, а знакомств — кот сука собака.
2. Список смежности. А это по-хитрому. Для каждого чувака в тусовке заводишь свой личный список: «а вот с этими я вожусь». Экономично, удобно. Именно так все умные делают, если граф не супер-плотный.

Смотри, как на Go это выглядит, список смежности:

package main

import "fmt"

// Graph — это наша тусовка, где у каждого свой список корешей
type Graph struct {
    vertices map[int][]int
}

// NewGraph создаёт новую, пока ещё пустую, пьянку
func NewGraph() *Graph {
    return &Graph{
        vertices: make(map[int][]int),
    }
}

// AddEdge — один чувак (src) теперь знает другого (dest)
func (g *Graph) AddEdge(src, dest int) {
    // Если чувака-источника ещё нет в карте — регистрируем
    if _, ok := g.vertices[src]; !ok {
        g.vertices[src] = []int{}
    }
    // Если чувака-приёмника нет — тоже пусть будет, мало ли
    if _, ok := g.vertices[dest]; !ok {
        g.vertices[dest] = []int{}
    }
    // Записываем: src теперь водится с dest
    g.vertices[src] = append(g.vertices[src], dest)
}

func main() {
    g := NewGraph()
    g.AddEdge(1, 2) // Первый узнал второго
    g.AddEdge(1, 3) // Первый узнал и третьего, раздолбай
    g.AddEdge(2, 3) // Второй, глядя на первого, тоже с третьим познакомился
    g.AddEdge(3, 4) // Третий пошёл ещё дальше, нашёл четвёртого

    // Смотрим, кто с кем
    for src, neighbors := range g.vertices {
        fmt.Printf("Чувак под номером %d тусит с: %vn", src, neighbors)
    }
}

А где это всё, блядь, применяется? Да везде, ёпта!

• Социалки: Друзья, подписки, «люди, которых вы можете знать» — это всё они, пидарасы-графы.
• Рекомендации: «Купив этот хуй, другие лохи также брали вот эту дичь» — это анализ связей.
• Карты и логистика: Как проехать от точки А до точки Б, чтобы не сесть в пробку и не выебать все колёса — классика, алгоритм Дейкстры там всякий.
• Зависимости в проекте: Твой package main сосёт из package utils, а тот, сука, тянет за собой ещё полгитхаба библиотек. Чтобы не было циклической хуйни — графы помогут.

Вот так вот, просто и с примерами. Не благодари.