Чем отличается дерево от графа? Какие задачи решаются с их помощью?

Графы и деревья — это фундаментальные структуры данных, широко используемые в программировании и компьютерных науках. Они помогают решать множество задач, включая навигацию, моделирование сетей и оптимизацию маршрутов. Разница между ними заключается в их структуре и ограничениях.

Что такое граф?

Граф — это множество узлов (вершин), соединённых рёбрами. В графах могут существовать циклы, несколько путей между вершинами и различные веса рёбер.

Виды графов

• Ориентированный граф — рёбра имеют направление.
• Неориентированный граф — рёбра не имеют направления.
• Взвешенный граф — каждому ребру присвоен вес.
• Невзвешенный граф — рёбра не содержат дополнительной информации.

Пример графа в C#

using System;
using System.Collections.Generic;

class Graph
{
    private Dictionary<int, List<int>> adjList = new();

    public void AddEdge(int u, int v)
    {
        if (!adjList.ContainsKey(u))
            adjList[u] = new List<int>();
        if (!adjList.ContainsKey(v))
            adjList[v] = new List<int>();

        adjList[u].Add(v);
        adjList[v].Add(u);
    }
}

Что такое дерево?

Дерево — это частный случай графа, в котором нет циклов и существует единственный путь между любыми двумя вершинами. У дерева есть корень, и каждое поддерево является деревом само по себе.

Виды деревьев

• Двоичное дерево — каждая вершина имеет не более двух потомков.
• Двоичное дерево поиска — левый потомок содержит меньшие значения, правый — большие.
• Балансированные деревья — AVL-дерево, красно-чёрное дерево.

Пример дерева в C#

class TreeNode
{
    public int Value;
    public TreeNode? Left;
    public TreeNode? Right;

    public TreeNode(int value)
    {
        Value = value;
        Left = Right = null;
    }
}

Основные различия между деревом и графом

Применение графов и деревьев

Задачи, решаемые с помощью графов:

• Поиск кратчайшего пути (алгоритм Дейкстры)
• Оптимизация маршрутов
• Анализ социальных сетей

Задачи, решаемые с помощью деревьев:

• Быстрый поиск элементов (двоичное дерево поиска)
• Организация данных (файловые системы)
• Вычисление выражений (синтаксические деревья)