Представление графа. Матрица смежности

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

Допустим, у нас есть некоторый массив, который описывает пользователей. Каждый элемент этого массива – это имя пользователя. Теперь нам нужно как-то задать в программе, что 2 пользователя являются друзьями.

string[] users = { "Roma", "Vlad", "Vika", "Ahmed" };

Для каких задач это нужно? Допустим, у нас на странице пользователя A нужно вывести всех друзей пользователя. Представить, кто кому является другом, мы можем с помощью такой матрицы:

byte[,] friends =
{
    { 0, 0, 0, 0 },
    { 0, 0, 0, 0 },
    { 0, 0, 0, 0 },
    { 0, 0, 0, 0 },
};

Что она означает? Каждый элемент такой матрицы отображает связь одного объекта с другим. Проще воспринимать это так, что каждая строка матрицы принадлежит 1 пользователю. А числа – это связь. В первой строке находится связь первого пользователя с остальными, в первом элементе – с самим собой, во второй – с пользователем с ID 2, и т.д.

Если связь без направления, то матрица может сократится. Дело в том, что значение 0:1 будет дублировать 1:0. Например, так будет выглядеть то, что пользователи 1 и 2 друзья.

byte[,] friends =
{
    { 0, 1, 0, 0 },
    { 1, 0, 0, 0 },
    { 0, 0, 0, 0 },
    { 0, 0, 0, 0 },
};

В таком случае, однёрки дублируют друг друга. Система друзей обычно не допускает поведение, что один пользователь другому друг, а другой нет. Но если связь направленная, то обе части от диагонали имеют смысл. Иначе они будут симметрично повторять друг друга.

Такая матрица может моделировать – есть ли переход из одного уровня в другой. Например, есть переход из уровня A в уровень B, тогда единица стоит на одной стороне. А вот обратно из B в A не попасть, и там будет стоять ноль. А вот из B в C и из C в B попасть можно, тогда в обеих сторонах будет единица.

Если количество вершин у графа небольшое (такой граф называют разряженным), то вместо матриц используют списки. Каждая вершина просто хранит список вершин, в которые можно попасть из неё.

Давайте попробуем описать простую функцию, она возвращает true, если два пользователя являются друзьями:

static string[] _users = { "Roma", "Vlad", "Vika", "Ahmed" };

static byte[,] _friends =
{
    { 0, 1, 0, 0 },
    { 1, 0, 0, 0 },
    { 0, 0, 0, 0 },
    { 0, 0, 0, 0 },
};

public static void Main(string[] args)
{
    Console.WriteLine(IsFriend("Roma", "Vlad"));
}

private static bool IsFriend(string userA, string userB)
{
    var userAIndex = Array.IndexOf(_users, userA);
    var userBIndex = Array.IndexOf(_users, userB);

    return _friends[userAIndex, userBIndex] == 1;
}

Всё очень просто! Давайте усложним задачу… Сколько общих друзей есть у пользователя A и пользователя B?

static string[] _users = { "Roma", "Vlad", "Vika", "Ahmed" };

static byte[,] _friends =
{
    { 0, 1, 1, 1 },
    { 1, 0, 1, 1 },
    { 1, 1, 0, 0 },
    { 1, 1, 0, 0 },
};

public static void Main(string[] args)
{
    Console.WriteLine(GetMutualFriendsCount("Roma", "Vlad"));
}

private static int GetMutualFriendsCount(string userA, string userB)
{
    var userAIndex = Array.IndexOf(_users, userA);
    var userBIndex = Array.IndexOf(_users, userB);

    var userAFriends = GetFriendsIds(userAIndex).ToArray();
    var userBFriends = GetFriendsIds(userBIndex).ToArray();

    var mutualCount = 0;

    for (int a = 0; a < userAFriends.Count(); a++)
        for (int b = 0; b < userBFriends.Count(); b++)
            if (userAFriends[a] == userBFriends[b])
                mutualCount++;

    return mutualCount;
}

private static IEnumerable<int> GetFriendsIds(int userIndex)
{
    for (int i = 0; i < _friends.GetLength(1); i++)
        if (_friends[userIndex, i] == 1)
            yield return i;
}

В данном примере мы выбрали два массива (списка смежности), которые содержат друзей пользователя A и B, и нашли сколько схожих элементов в них.

Данное решение работает за O(n ^ 2). Можем ли мы улучшить алгоритм? Да! Если присмотреться в строки такой матрицы, то мы можем обнаружить один интересный факт – это уже списки смежности, да ещё и удобно отсортированные. И в итоге мы можем сделать подсчёт за O(n).

static string[] _users = { "Roma", "Vlad", "Vika", "Ahmed" };

static byte[,] _friends =
{
    { 0, 1, 1, 1 },
    { 1, 0, 1, 1 },
    { 1, 1, 0, 0 },
    { 1, 1, 0, 0 },
};

public static void Main(string[] args)
{
    Console.WriteLine(GetMutualFriendsCount("Roma", "Vlad"));
}

private static int GetMutualFriendsCount(string userA, string userB)
{
    var userAIndex = Array.IndexOf(_users, userA);
    var userBIndex = Array.IndexOf(_users, userB);

    var mutualCount = 0;

    for (int i = 0; i < _friends.GetLength(0); i++)
        if (_friends[i, userAIndex] == 1 && _friends[i, userBIndex] == 1)
            mutualCount++;

    return mutualCount;
}

Структура данных может помочь нам оптимизировать некоторые операции. Зачастую, секрет производительности кроется в правильном выборе формы данных, но нет идеального решения. Как бы избито это не звучало – но для каждой ситуации свои методы. Например, матрицы смежности зачастую потребляют слишком много памяти.

А теперь давайте попробуем найти через сколько рукопожатий пользователь A знаком с B? Это число означает сколько друзей отделяет A от B.

static string[] _users = { "Roma", "Vlad", "Vika", "Ahmed" };

static byte[,] _friends =
{
    { 0, 1, 0, 0 },
    { 1, 0, 1, 0 },
    { 0, 1, 0, 1 },
    { 0, 0, 1, 0 },
};

public static void Main(string[] args)
{
    Console.WriteLine(GetDistance(0, 1, new List<int>()));
}

private static int GetDistance(int currentUserIndex, int targetUserIndex, List<int> blacklist, int step = 0)
{
    if (_friends[currentUserIndex, targetUserIndex] == 1)
        return step;

    blacklist.Add(currentUserIndex);

    for (int i = 0; i < _friends.GetLength(0); i++)
    {
        if (_friends[i, currentUserIndex] == 1)
        {
            if (blacklist.Contains(i))
                continue;

            return GetDistance(i, targetUserIndex, blacklist, step + 1);
        }
    }

    return -1;
}

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

Если вы нашли ошибку, пожалуйста выделите её и нажмите Ctrl+Enter.


Leave a Reply

Your email address will not be published. Required fields are marked *