KURSOFT

Список рёбер (Edge List)

Пример ориентированого однонаправленного графа сделанный списком рёбер (edge list)

using System;
using System.Collections.Generic;

// Граф в виде списка рёбер (подходит для алгоритмов, работающих с рёбрами)
List<(int from, int to)> edgeList =
[
    (0, 1), // ребро 0 → 1
    (0, 2), // ребро 0 → 2
    (1, 3), // ребро 1 → 3
    (1, 4), // ребро 1 → 4
    (2, 5), // ребро 2 → 5
    (2, 6), // ребро 2 → 6
];

Console.WriteLine("Список рёбер:");
foreach (var edge in edgeList)
{
    Console.WriteLine($"{edge.from} → {edge.to}");
}

Далее визуализация ориентированого графа (Directed Graph т.е. имеет ориентацию движения ребер). В примере однонаправленный (Unidirectional Graph).

Наведите на графы мышкой

Пример неориентированого графа

using System;
using System.Collections.Generic;

// Граф в виде списка рёбер (подходит для алгоритмов, работающих с рёбрами)
List<(int from, int to)> edgeList =
[
    // Основные рёбра
    (0, 1), (1, 0), // 0 ↔ 1
    (0, 2), (2, 0), // 0 ↔ 2
    (1, 3), (3, 1), // 1 ↔ 3
    (1, 4), (4, 1), // 1 ↔ 4
    (2, 5), (5, 2), // 2 ↔ 5
    (2, 6), (6, 2)  // 2 ↔ 6
];

Console.WriteLine("Список рёбер:");
foreach (var edge in edgeList)
{
    Console.WriteLine($"{edge.from} → {edge.to}");
}

Наведите на графы мышкой

Пример BFS используя список рёбер (Edge List)

public class BFSDirectExample
{
    public static void Main()
    {
        // Ориентированный граф как список рёбер
        List<(int from, int to)> edgeList = new List<(int, int)>
        {
            (0, 1), // 0 → 1
            (0, 2), // 0 → 2
            (1, 3), // 1 → 3
            (1, 4), // 1 → 4
            (2, 5), // 2 → 5
            (2, 6)  // 2 → 6
        };

        // BFS без преобразования в словарь
        List<int> traversalOrder = BFSDirect(edgeList, 0);
        
        Console.WriteLine("Порядок обхода BFS: " + string.Join(" -> ", traversalOrder));
        // Вывод: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6
    }

    public static List<int> BFSDirect(List<(int from, int to)> edges, int start)
    {
        var result = new List<int>();
        var visited = new HashSet<int>();
        var queue = new Queue<int>();

        queue.Enqueue(start);
        visited.Add(start);

        while (queue.Count > 0)
        {
            int current = queue.Dequeue();
            result.Add(current);

            // Ищем все рёбра, исходящие из текущей вершины
            var neighbors = edges
                .Where(e => e.from == current)
                .Select(e => e.to);

            foreach (int neighbor in neighbors)
            {
                if (!visited.Contains(neighbor))
                {
                    visited.Add(neighbor);
                    queue.Enqueue(neighbor);
                }
            }
        }

        return result;
    }
}

Ключевые моменты:

1. Подготовка графа:
   • Список рёбер преобразуется в словарь смежности adjacencyList для эффективного доступа к соседям.
2. Алгоритм BFS:
   • Использует очередь (Queue) для обработки вершин.
   • Множество visited отслеживает посещённые вершины.
   • На каждом шаге берётся вершина из очереди, добавляются её непосещённые соседи.
3. Особенности для неориентированного графа:
   • Автоматически учитываются рёбра в обоих направлениях.
   • Нет риска «застревания» — все связи двусторонние.
4. Сложность:
   • Время: O(V + E), где V — вершины, E — рёбра.
   • Память: O(V) для хранения очереди и посещённых вершин.

Пример вывода:

Для графа из примера обход начнётся с вершины 0 и выведет:

Порядок обхода BFS: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6

Это классический BFS, который гарантированно обходит все вершины связного неориентированного графа в порядке увеличения расстояния от стартовой вершины.

Не понимаю зачем использовать не официальные некачественные библиотеки. Это лишняя обертка, медленная и много потенциальных проблем.

Альтернатива

1. Через python-telegram-bot (telegram)

Это официальная библиотека от команды Telegram, простая и удобная.

from telegram import Update
from telegram.ext import Updater, CommandHandler, CallbackContext

def start(update: Update, context: CallbackContext):
    update.message.reply_text("Привет! Я бот.")

updater = Updater("TOKEN")
updater.dispatcher.add_handler(CommandHandler("start", start))
updater.start_polling()
updater.idle()

2. Через requests (Raw API)

Telegram Bot API — это HTTP-интерфейс, и можно работать с ним напрямую.

import requests

TOKEN = "YOUR_BOT_TOKEN"
BASE_URL = f"https://api.telegram.org/bot{TOKEN}"

def send_message(chat_id, text):
    requests.post(f"{BASE_URL}/sendMessage", json={"chat_id": chat_id, "text": text})

# Пример обработки входящих сообщений (например, через вебхук)
3. Другие библиотеки
pyTelegramBotAPI (telebot) – простая и популярная альтернатива.

3. Другие библиотеки

• pyTelegramBotAPI (telebot) – простая и популярная альтернатива.

import telebot

bot = telebot.TeleBot("TOKEN")

@bot.message_handler(commands=['start'])
def start(message):
    bot.reply_to(message, "Привет!")

bot.polling()

while (l < r) {
     // [chars[l], chars[r]] = [chars[r], chars[l]];
     const temp = chars[l]
     chars[l] = chars[r]
     chars[r] = temp
     l++
     r--
 }

Алгоритм поиска в ширину (Breadth-First Search, BFS) используется для поиска или обхода узлов в графе или дереве. BFS начинает с корневого узла и исследует соседние узлы на каждом уровне, прежде чем переходить к узлам следующего уровня.

Ниже приведен простой пример реализации алгоритма BFS на C#. В этом примере мы будем использовать неориентированный граф, представленный в виде списка смежности.

Пример реализации BFS на C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // Создаем граф как словарь списков смежности (adjacency list)
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>()
        {
            {0, new List<int> {1, 2}},
            {1, new List<int> {0, 3, 4}},
            {2, new List<int> {0, 5, 6}},
            {3, new List<int> {1}},
            {4, new List<int> {1}},
            {5, new List<int> {2}},
            {6, new List<int> {2}}
        };

        // Вызываем BFS начиная с узла 0
        BFS(graph, 0);
    }

    static void BFS(Dictionary<int, List<int>> graph, int startNode)
    {
        // Очередь для хранения узлов, которые нужно посетить
        Queue<int> queue = new Queue<int>();
        // Хэш-набор для отслеживания посещенных узлов
        HashSet<int> visited = new HashSet<int>();

        // Начинаем с добавления начального узла в очередь и помечаем его как посещенный
        queue.Enqueue(startNode);
        visited.Add(startNode);

        while (queue.Count > 0)
        {
            // Извлекаем узел из очереди
            int currentNode = queue.Dequeue();
            Console.WriteLine("Посещаем узел: " + currentNode);

            // Проходим по всем соседям текущего узла
            foreach (int neighbor in graph[currentNode])
            {
                if (!visited.Contains(neighbor))
                {
                    // Если сосед не был посещен, добавляем его в очередь и помечаем как посещенный
                    queue.Enqueue(neighbor);
                    visited.Add(neighbor);
                }
            }
        }
    }
}

Объяснение кода

1. Граф как словарь списков смежности: Граф представлен как словарь, где ключом является узел, а значением — список соседних узлов. Например, узел 0 имеет соседей 1 и 2.

2. Функция BFS:

• Принимает граф и начальный узел.
• Использует очередь (Queue<int>) для хранения узлов, которые нужно посетить, и множество (HashSet<int>) для отслеживания посещенных узлов.
• Начинает с добавления начального узла в очередь и помечает его как посещенный.
• Пока очередь не пуста, узел извлекается из очереди, и его соседи проверяются. Если соседний узел еще не был посещен, он добавляется в очередь и помечается как посещенный.

3. Запуск программы:

• Программа начинает обход графа с узла 0 и посещает все узлы в графе в порядке BFS.

Результат выполнения программы

Посещаем узел: 0
Посещаем узел: 1
Посещаем узел: 2
Посещаем узел: 3
Посещаем узел: 4
Посещаем узел: 5
Посещаем узел: 6

В общем, задача протестировать MVP (minimum viable product), это специальный подход в it индустрии, когда делают простой проект быстро, тестируют на аудитории, получают результат, а дальше принимается решение расти или нет.

У нас была такая же мысль с MVP. Но где разворачивать сайт? Хотели использовать яндекс облако, но они откровенно не дешевые для MVP, в принципе есть бесплатный период теста, но опять же, крутить сайт, пусть даже за 5 тыс руб. в месяц без единого дохода так себе.

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

Нужно ли мне отчитываться перед государством, если я подниму сайт дома?

Скажу честно, не знаю откуда взялась эта довольно идиотская байка. Для государства нет никакой разницы арендуете ли вы сайт в облаке или развернули у себя. Если есть заработок, платите налоги — всё, никаких претензий.

Настройка ноутбука под сайт

Что необходимо:

1. Более менее нормальный интернет (я давно использую 300 Мбит/с)
2. Статический адрес (арендовать у провайдера за 150 руб. в месяц)
3. Старый ноутбук.
4. Домашний роутер (лучше гигабитный)

Статический адрес

Статический IP адрес — по сути адрес вашего домашнего/офисного интернет оборудования для общения с вашим провайдером. При первом подключении к провайдеру, провайдер не выдает индивидуальный IP адрес, он формируется динамически, время от времени менятся. Поэтому если настроить сайт на такой адрес, то после изменений ваш сайт просто не найдут. Но в сети есть варианты как настроить бесплатный статический адрес с хитростями. Но мне было лень это изучать и как-то не по-взрослому, ты зависишь от каких-то сторонних сервисов и о надежности не приходиться говорить. Мне проще заплатить 150 рублей в месяц.

Настройка статического адреса

Небольшая вводная история. Я еще года 2 — 3 назад хотел настроить себе статич. адрес для игры в CS 1.6 🙂 В общем думаю — “ну фигня вопрос!”. Заказываю статический IP адрес, как вы думаете у кого, у ростелекома. Ага, значит пытаюсь настроить, всё делаю по феншую, но никак не могу запустить. Звоню узнать — аХа, щас. Ихние спецы — полный ноль. Звонил раз 5. Короче “выдающиеся” ничем мне не помогли, переписывался даже в VK, к сожалению не могу приложить переписку, удалил от злости и заблокировал их. Короче, начал сомневаться в своих когнитивных способностях. Как это обычно бывает, решил прибегнуть к кардинальному решению — сменить к чертям «надежного» провайдера. В итоге всё заработало с первого раза.

В принципе роутер настраивается просто, сами интерфейсы роутера сильно разные, поэтому я просто опишу куда смотреть на примере tp-link.

1. Вам нужно добавить статический адрес, который либо выдает оператор в договоре либо можно посмотреть в личном кабинете провайдера или просто увидеть его через myIp.ru

2. Далее указываем внутри вашего роутера, куда переадресовываться трафик. В моём случае “Тип сервер” произвольное название. “Внешний порт” — это как раз потр для сайта, обычно это 80, указываем его. А вот для CS 1.6 порт по умолчанию = 27015. “Внутренний IP” — это IP вашей машины дома. Таким образом можно подключить любое количество компьютеров, которые будут “общаться” внутри только вашей сети, а внешний доступ иметь по единственному, дефолтному порту. Остальные настройки произвольные.

Внутренний IP машины на ms windows можно посмотреть через команду ipconfig.

3. Тут необязательные настройки. Чтобы внутренний адрес вашей машины не менялся произвольно, когда ему захочется. Привяжите MAC-адрес (уникальный адрес сетевого устройства, задается еще на заводе) своей машины и её текущий адрес

Поднимаем сайт на ноутбуке

Если у вас windows это делается очень просто. Всё что вам нужно это запустить веб-сервер (IIS). В windows он встроен. По-моему, его нет только в windows home basic. В русской версии это “IIS Службы”. Выберите Панель управления (Control Panel) > Программы и компоненты (Programs and Features) > Включение или отключение компонентов Windows (Turn Windows Features on or off). Разверните узел Службы IIS (Internet Information Services).

Нажмите окей, после некоторой загрузки откройте браузер и напишите в поисковой строке localhost или явно укажите порт 80 — localhost:80. Откроется тестовая страница. Поздравляю вы запустили сайт. С помощью IIS веб-сервера можно запускать сайты, например, на WordPress или много другое.

Мы же конечно используем более серьезный стек на сайте. Это Microsoft dotnet работает на linux-е. Кстати да, может вы всё еще не знаете, но Microsoft любит линукс. И уже с 2016-го года выпускают свой программный флагман dotnet под все платформы, т.е. кроссплатформенно. Для фронтенда у нас Angular последних версий. Также есть CI/CD на Azure DevOps, он бесплатный до 5 человек.