using System.Collections.Generic;
public override string ToString() {
private readonly Dictionary<Node<T>, List<Node<T>>> _adj;
_adj = new Dictionary<Node<T>, List<Node<T>>>();
public void AddEdge(Node<T> node1, Node<T> node2) {
if(!_adj.ContainsKey(node1))
_adj[node1] = new List<Node<T>>();
if(!_adj.ContainsKey(node2))
_adj[node2] = new List<Node<T>>();
public Stack<Node<T>> ShortestPath(Node<T> source, Node<T> dest) {
var path = new Dictionary<Node<T>, Node<T>>();
var distance = new Dictionary<Node<T>, int>();
foreach(var node in _adj.Keys) {
var q = new Queue<Node<T>>();
foreach(var adj in _adj[node].Where(n => distance[n] == -1)) {
distance[adj] = distance[node] + 1;
var res = new Stack<Node<T>>();
public static void Main()
var g = new Graph<int>();
var n1 = new Node<int>(1);
var n2 = new Node<int>(2);
var n3 = new Node<int>(3);
var n4 = new Node<int>(4);
var n5 = new Node<int>(5);
var n6 = new Node<int>(6);
var n7 = new Node<int>(7);
Console.WriteLine("Shortest path is: {0}", string.Join("->", g.ShortestPath(n1, n7)));