I have implemented in C# a graph data structure (undirected graph) using TDD technique, tests are provided upfront. This implementation provides common graph methods also it traverses graph using DFS algorithm.Tests are passing so I guess, implementation is correct.I would appreciate any test case that I might be missing (edge cases) and general code review.using System;using Microsoft.VisualStudio.TestTools.UnitTesting;using GraphDataStructure;namespace Tests{    public static class Helper    {        public static string ToJoinedString(this char[] array)        {            return string.Join( , array);        }    }    [TestClass]    public class Tests    {        #region graphs        public static char[][] graph1 = new char[][] {                new char [] {'A', 'B'},                new char [] {'A', 'D'},                new char [] {'A', 'C'},                new char [] {'C', 'D'},                new char [] {'C', 'E'}            };        public static char[][] graph2 = new char[][]        {            new char [] {'A', 'G'},            new char [] {'A', 'C'},            new char [] {'A', 'B'},            new char [] {'A', 'D'},            new char [] {'C', 'G'},            new char [] {'C', 'B'},            new char [] {'D', 'B'},            new char [] {'D', 'E'},            new char [] {'B', 'F'},        };        public static char[][] graph3 = new char[][]        {            new char [] {'A', 'G'}        };        #endregion        #region graph1        [TestMethod]        public void TestGraph1Initialisation()        {            var graph = new Graph();            graph.initGraph(graph1);            var expectedAdjecencyMatrix = new char[][]            {                new char[] { 'B', 'C', 'D' },                new char[] { 'A' },                new char[] { 'A', 'D', 'E' },                new char[] { 'A', 'C' },                new char[] { 'C' },            };            //Testing vertices            var expectedVertices = new char[] { 'A', 'B', 'C', 'D', 'E' };            Assert.AreEqual(expectedVertices.ToJoinedString(), graph.Vertices.ToJoinedString());            //Testing adjecency matrix            int i = 0;            foreach (var row in expectedAdjecencyMatrix)                Assert.AreEqual(row.ToJoinedString(), graph.AdjecencyMatrix[i++].ToJoinedString());        }        [TestMethod]        public void TestGraph1GetAdjecents()        {            var graph = new Graph();            graph.initGraph(graph1);            var expectedAdjecents = new char[] { 'B', 'C', 'D' };            Assert.AreEqual(expectedAdjecents.ToJoinedString(), graph.getAdjecents('A').ToJoinedString());            expectedAdjecents = new char[] { 'C' };            Assert.AreEqual(expectedAdjecents.ToJoinedString(), graph.getAdjecents('E').ToJoinedString());        }        [TestMethod]        [ExpectedException(typeof(InvalidOperationException))]        public void TestGraph1GetAdjecentsOfNonExistentVertex()        {            var graph = new Graph();            graph.initGraph(graph1);            graph.getAdjecents('Y');        }        [TestMethod]        public void TestGraph1Traversal()        {            var graph = new Graph();            graph.initGraph(graph1);            var expectedResult = new char[] { 'A', 'B', 'C', 'D', 'E' } ;            char[] result = graph.Traverse();            Assert.AreEqual(expectedResult.ToJoinedString(), result.ToJoinedString());        }        #endregion        #region graph2        [TestMethod]        public void TestGraph2Initialisation()        {            var graph = new Graph();            graph.initGraph(graph2);            var expectedAdjecencyMatrix = new char[][]            {                new char[] { 'B', 'C', 'D', 'G' },  //A                new char[] { 'A', 'C', 'D', 'F' },  //B                new char[] { 'A', 'B', 'G' },       //C                new char[] { 'A', 'B', 'E' },       //D                new char[] { 'D' },                 //E                 new char[] { 'B' },                 //F                new char[] { 'A', 'C' },            //G            };            //Testing vertices            var expectedVertices = new char[] { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };            Assert.AreEqual(expectedVertices.ToJoinedString(), graph.Vertices.ToJoinedString());            //Testing adjecency matrix            int i = 0;            foreach (var row in expectedAdjecencyMatrix)                Assert.AreEqual(row.ToJoinedString(), graph.AdjecencyMatrix[i++].ToJoinedString());        }        [TestMethod]        public void TestGraph2GetAdjecents()        {            var graph = new Graph();            graph.initGraph(graph2);            var expectedAdjecents = new char[] { 'B', 'C', 'D', 'G' };            Assert.AreEqual(expectedAdjecents.ToJoinedString(), graph.getAdjecents('A').ToJoinedString());            expectedAdjecents = new char[] { 'A', 'B', 'E' };            Assert.AreEqual(expectedAdjecents.ToJoinedString(), graph.getAdjecents('D').ToJoinedString());        }        [TestMethod]        [ExpectedException(typeof(InvalidOperationException))]        public void TestGraph2GetAdjecentsOfNonExistentVertex()        {            var graph = new Graph();            graph.initGraph(graph2);            graph.getAdjecents('Y');        }        [TestMethod]        public void TestGraph2Traversal()        {            var graph = new Graph();            graph.initGraph(graph2);            var expectedResult = new char[] { 'A', 'B', 'C', 'G', 'D', 'E', 'F' };            char[] result = graph.Traverse();            Assert.AreEqual(expectedResult.ToJoinedString(), result.ToJoinedString());        }        #endregion        #region graph3        [TestMethod]        public void TestGraph3Initialisation()        {            var graph = new Graph();            graph.initGraph(graph3);            var expectedAdjecencyMatrix = new char[][]            {                new char[] { 'G' },  //A                new char[] { 'A' },  //G            };            //Testing vertices            var expectedVertices = new char[] { 'A', 'G' };            Assert.AreEqual(expectedVertices.ToJoinedString(), graph.Vertices.ToJoinedString());            //Testing adjecency matrix            int i = 0;            foreach (var row in expectedAdjecencyMatrix)                Assert.AreEqual(row.ToJoinedString(), graph.AdjecencyMatrix[i++].ToJoinedString());        }        [TestMethod]        public void TestGraph3GetAdjecents()        {            var graph = new Graph();            graph.initGraph(graph3);            var expectedAdjecents = new char[] { 'G' };            Assert.AreEqual(expectedAdjecents.ToJoinedString(), graph.getAdjecents('A').ToJoinedString());            expectedAdjecents = new char[] { 'A'};            Assert.AreEqual(expectedAdjecents.ToJoinedString(), graph.getAdjecents('G').ToJoinedString());        }        [TestMethod]        [ExpectedException(typeof(InvalidOperationException))]        public void TestGraph3GetAdjecentsOfNonExistentVertex()        {            var graph = new Graph();            graph.initGraph(graph3);            graph.getAdjecents('Y');        }        [TestMethod]        public void TestGraph3Traversal()        {            var graph = new Graph();            graph.initGraph(graph3);            var expectedResult = new char[] { 'A', 'G'};            char[] result = graph.Traverse();            Assert.AreEqual(expectedResult.ToJoinedString(), result.ToJoinedString());        }        #endregion    }}using System;using System.Collections.Generic;using System.Linq;namespace GraphDataStructure{    public class Graph    {        private char[][] adjecencyMatrix;        private char[] vertices;        public Graph()        {        }        public char[] Vertices { get { return vertices; } }        public char[][] AdjecencyMatrix { get { return adjecencyMatrix;  } }        public void initGraph(char[][] edges)        {            vertices = edges.SelectMany(x => x).Distinct().OrderBy(x => x).ToArray();            adjecencyMatrix = new char[vertices.Length][];            for (int j = 0; j < vertices.Length; j++)            {                var adjecents = new List<char>();                foreach(var row in edges)                {                    if (row.Contains(vertices[j]))                        adjecents.Add(row.First(x => x != vertices[j]));                }                adjecencyMatrix[j] = adjecents.OrderBy(x => x).ToArray();            }        }        public char[] getAdjecents(char c)        {            if (Array.IndexOf(vertices, c) < 0)                throw new InvalidOperationException(Invalid vertex);            return adjecencyMatrix[Array.IndexOf(vertices, c)];        }        //DFS algorithm        public char[] Traverse()        {            var stack = new Stack<char>();            var result = new List<char>();            var c = Vertices[0];            result.Add(c);            stack.Push(c);            while(stack.Count > 0)            {                var adjecents = getAdjecents(stack.Peek());                if (adjecents.Any(x => !result.Contains(x)))                {                    c = adjecents.Where(x => !result.Contains(x)).ElementAt(0);                    result.Add(c);                    stack.Push(c);                }                else                    stack.Pop();            }            return result.ToArray();        }    }}
Undirected graph implementation
c#;unit testing;graph
public class GraphIs there any reason not to make it Graph<TVertex>?    private char[][] adjecencyMatrix;    private char[] vertices;    ...    public char[] Vertices { get { return vertices; } }    public char[][] AdjecencyMatrix { get { return adjecencyMatrix;  } }I have three related questions:Why use arrays internally? An IDictionary<TVertex, ISet<TVertex>> captures the essence of a graph and gives you straightforward lookups.Even if you are using arrays internally, why expose arrays? A public getter which returns an array is implicitly also a public setter, because the code which calls it can mutate your internal state.Why is AdjecencyMatrix exposed at all?    public Graph()    {    }    public void initGraph(char[][] edges)This is an anti-pattern. The constructor should give a fully initialised object, and if that's not possible then it should be hidden and public access should be via a builder or other factory.With a graph I would be tempted to make the constructor private and have static factory methods to build from a set of edges (as here), from adjacency lists, and from an adjacency matrix.    {        vertices = edges.SelectMany(x => x).Distinct().OrderBy(x => x).ToArray();        adjecencyMatrix = new char[vertices.Length][];        for (int j = 0; j < vertices.Length; j++)        {            var adjecents = new List<char>();            foreach(var row in edges)            {                if (row.Contains(vertices[j]))                    adjecents.Add(row.First(x => x != vertices[j]));            }            adjecencyMatrix[j] = adjecents.OrderBy(x => x).ToArray();        }    }Naming. adjacency has two as. And what you have here isn't an adjacency matrix: that's indexed by two vertices and contains bools. This is the adjacency lists representation of a graph.See earlier comments about use of dictionary and set rather than array.    public char[] getAdjecents(char c)    {        if (Array.IndexOf(vertices, c) < 0)            throw new InvalidOperationException(Invalid vertex);        return adjecencyMatrix[Array.IndexOf(vertices, c)];    }In addition to earlier comments, have you considered making the neighbours of a vertex be an indexed property? I think that would be quite a natural notation.    //DFS algorithm    public char[] Traverse()    {        var stack = new Stack<char>();        var result = new List<char>();        var c = Vertices[0];        result.Add(c);        stack.Push(c);        while(stack.Count > 0)        {            var adjecents = getAdjecents(stack.Peek());            if (adjecents.Any(x => !result.Contains(x)))            {                c = adjecents.Where(x => !result.Contains(x)).ElementAt(0);                result.Add(c);                stack.Push(c);            }            else                stack.Pop();        }        return result.ToArray();    }I personally don't find Traverse a very descriptive name. DFS would tell me immediately what it's doing. I'm not sure, though, how useful a DFS is which just returns a list of vertices. Most of the time DFS is used as a building block for other algorithms, and they require additional data.            if (adjecents.Any(x => !result.Contains(x)))            {                c = adjecents.Where(x => !result.Contains(x)).ElementAt(0);I'd always use First() rather than ElementAt(0), and to save doing the search twice I'd rework to            c = adjecents.Where(x => !result.Contains(x)).FirstOrDefault();            if (c != default(TElement))            {result.Contains(x) does a linear search. For reasonable performance you should use an ISet implementation in parallel to result.Looking at the DFS implementation, I can spot a missing test case. Consider    public static char[][] graph4 = new char[][]    {        new char [] {'A', 'B'},        new char [] {'C', 'D'},    };