Представление графа на основе таблиц смежности – это не самая частая задача. Хоть и такие матрицы можно увидеть в различных отношениях сущностей в системе, но прямое выражение – это редкость.
Допустим, у нас есть некоторый массив, который описывает пользователей. Каждый элемент этого массива – это имя пользователя. Теперь нам нужно как-то задать в программе, что 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;
}Решается такая задача на основе алгоритма обхода графа. В данном случае мы видим рекурсивную реализую обхода в глубину. Важное дополнение, что мы тут находим – не всегда кратчайший путь. Задачи найти минимальную дистанцию за разумное время – не такая тривиальная, как может показаться.