Назад к основам – обобщенные структуры данных и алгоритмы в .NET 2.0 - Графы
ОГЛАВЛЕНИЕ
Граф
Структура данных граф состоит из трех частей:
• Класс Vertex<T>, представляющий узел в графе.
• Класс Edge<T>, образующий связь между двумя вершинами.
• Класс Graph<T>, являющийся коллекцией ребер и вершин.
Vertex<T>
public class Vertex<T>
{
// методы
public Edge<T> GetEmanatingEdgeTo(Vertex<T> toVertex);
public Edge<T> GetIncidentEdgeWith(Vertex<T> toVertex);
public bool HasEmanatingEdgeTo(Vertex<T> toVertex);
public bool HasIncidentEdgeWith(Vertex<T> fromVertex);
// ...
// свойства
public T Data { get; set; }
public int Degree { get; }
public IEnumerator<Edge<T>> EmanatingEdges { get; }
public IEnumerator<Edge<T>> IncidentEdges { get; }
public int IncidentEdgesCount { get; }
// ...
}
Класс Vertex<T> представляет узел в графе. Он хранит список ребер (добавленный графом), выходящих из него (направленных к другой вершине), и смежные ребра. К этим спискам можно обратиться с помощью свойств EmanatingEdges и IncidentEdges. Элемент данных связан с вершиной, чтобы отличить ее от других вершин.
Edge<T>
public class Edge<T>
{
// методы
public Vertex<T> GetPartnerVertex(Vertex<T> vertex);
// ...
// свойства
public Vertex<T> FromVertex { get; }
public bool IsDirected { get; }
public Vertex<T> ToVertex { get; }
public double Weight { get; }
// ...
}
Класс Edge<T> представляет ребро между двумя вершинами в графе, которая бывает направленной или ненаправленной, в зависимости от типа графа. Ребра бывают взвешенными, т. е. ребру можно присвоить значение, представляющее его полезную нагрузку или расстояние между двумя вершинами. Метод GetPartnerVertex, если дана вершина, содержащаяся в ребре, возвращает другую вершину в отношении.
Graph<T>
public class Graph<T> : IVisitableCollection<T>
{
// методы
public void AddEdge(Edge<T> edge);
public Edge<T> AddEdge(Vertex<T> from, Vertex<T> to);
public Edge<T> AddEdge(Vertex<T> from, Vertex<T> to, double weight);
public void AddVertex(Vertex<T> vertex);
public Vertex<T> AddVertex(T item);
public void BreadthFirstTraversal(IVisitor<Vertex<T>> visitor,
Vertex<T> startVertex);
public bool ContainsEdge(Edge<T> edge);
public bool ContainsEdge(Vertex<T> from, Vertex<T> to);
public bool ContainsEdge(T fromValue, T toValue);
public bool ContainsVertex(Vertex<T> vertex);
public bool ContainsVertex(T item);
public void DepthFirstTraversal(OrderedVisitor<Vertex<T>> visitor,
Vertex<T> startVertex);
public Edge<T> GetEdge(Vertex<T> from, Vertex<T> to);
public bool RemoveEdge(Edge<T> edge);
public bool RemoveEdge(Vertex<T> from, Vertex<T> to);
public bool RemoveVertex(Vertex<T> vertex);
public bool RemoveVertex(T item);
// ...
// свойства
public int EdgeCount { get; }
public IEnumerator<Edge<T>> Edges { get; }
public bool IsDirected { get; }
public bool IsStronglyConnected { get; }
public bool IsWeaklyConnected { get; }
public int VertexCount { get; }
public IEnumerator<Vertex<T>> Vertices { get; }
// ...
}
Класс Graph<T> является контейнером вершин и ребер. Граф выполняет все операции добавления и удаления. Реализованы стандартные операции добавления, удаления и получения. Также реализованы DepthFirstTraversal и BreadthFirstTraversal аналогично структурам данных дерево, за исключением того что они требуют начальную вершину, так как граф лишен корня.
IsStronglyConnected и IsWeaklyConnected проверяют на возможность соединения в графе. Слабая связанность гарантирует наличие ненаправленного ребра между каждой вершиной в графе, то есть все вершины достижимы из любой другой вершины. Для направленного графа алгоритм представляет направленные ребра как ненаправленные ребра. Проверка, является ли граф сильно связанным, влечет за собой проверку того, что каждая вершина достижима из любой другой вершины и доступна только в направленных графах.
[Дополнительная информация о графах]
Куча
public class Heap<T> : IVisitableCollection<T>, IHeap<T>
{
// методы
public override void Add(T item);
public T RemoveSmallestItem();
// ...
// свойства}
public T SmallestItem { get; }
// ...
}
Структура данных куча является древовидной структурой с особым свойством: наименьший элемент (неубывающая куча) или наибольший элемент (невозрастающая куча) содержится в корне дерева. Куча, реализованная в этой библиотеке, может быть неубывающей кучей или невозрастающей кучей, что устанавливается в конструкторе. Для невозрастающей кучи используемый экземпляр IComparer<T> обертывается в экземпляр ReverseComparer<IComparer<T>>, тем самым инвертируя решение сравнения и сортируя в обратном порядке.