The Graph data structure consists of three parts :

• A Vertex<T> class that represents a node in the graph.
• An Edge<T> class that forms a link between two vertices.
• A Graph<T> class that represents the collection of edges and vertices.

public class Vertex<T>
{
      // Methods
      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);      
      // ...
    
      // Properties
      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; }
      // ...
}

The Vertex<T> class represents a node in the graph. It keeps a list of edges (added by the graph) emanating from it (directed to the other vertex), and incident edges. These lists can be accessed by the EmanatingEdges and IncidentEdges properties. A data item is associated with the vertex to{ differentiate it from other vertices.

public class Edge<T>
{
      // Methods
      public Vertex<T> GetPartnerVertex(Vertex<T> vertex);
      // ...

      // Properties
      public Vertex<T> FromVertex { get; }
      public bool IsDirected { get; }
      public Vertex<T> ToVertex { get; }
      public double Weight { get; }
      public object Tag { get; set; }
      // ...
}

The Edge<T> class represents an edge between two vertices in a graph, which can be either directed or undirected depending on the graph type. Edges can be weighted, i.e., a value can be assigned to an edge to represent its payload or distance between the two vertices. The GetPartnerVertex method, given a vertex contained in the edge, returns the other vertex in the relationship.

[Serializable]
public class Graph<T> : IVisitableCollection<T>
{    
    // Methods
    public Graph(bool isDirected);    	
    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(T item);
    public bool ContainsVertex(Vertex<T> vertex);    
    public void DepthFirstTraversal(OrderedVisitor<Vertex<T>> visitor, Vertex<T> startVertex);    
    public IList<Vertex<T>> FindVertices(Predicate<T> predicate);    
    public Edge<T> GetEdge(T fromVertexValue, T toVertexValue);
    public Edge<T> GetEdge(Vertex<T> from, Vertex<T> to);
    public IEnumerator<T> GetEnumerator();
    public Vertex<T> GetVertex(T vertexValue);
    public bool IsCyclic();
    public bool IsStronglyConnected();
    public bool IsWeaklyConnected();
    public bool RemoveEdge(Edge<T> edge);
    public bool RemoveEdge(Vertex<T> from, Vertex<T> to);
    public bool RemoveVertex(T item);
    public bool RemoveVertex(Vertex<T> vertex);    
    public IList<Vertex<T>> TopologicalSort();    
    public void TopologicalSortTraversal(IVisitor<Vertex<T>> visitor);    
    // ...
	
    // Properties    
    public ICollection<Edge<T>> Edges { get; }
    public bool IsDirected { get; }    
    public ICollection<Vertex<T>> Vertices { get; }
    // ...
}

The Graph<T> class is a container of vertices and edges. All add and remove operations are performed by the graph. The standard add, remove, and get operations are implemented. Also implemented is a DepthFirstTraversal and a BreadthFirstTraversal similar to the tree data structures, except that they require a start vertex since a graph has no root.

The IsStronglyConnected and IsWeaklyConnected tests for connectivity in a graph. Weak connectedness ensures that there is an undirected edge between every vertex in the graph. In other words, all vertices are reachable from every other vertex. Note that for a directed graph, the algorithm represents directed edges as undirected edges. Testing if a graph is strongly connected entails ensuring that each vertex is reachable from every other vertex, and is only available on directed graphs.

More information on Graphs