title: Graph Adjacency List Implementation
body: <p>I am trying to represent a Graph in <code>Adjacency List</code> using C#, like the code bellow.
  <strong>But I would like to know where I can find a better implementation in C#.
  Like this website for Java: <a href="http://algs4.cs.princeton.edu/41undirected/Graph.java.html" rel="nofollow">http://algs4.cs.princeton.edu/41undirected/Graph.java.html</a></strong></p>
  
  <p>In order to improve this implementation I have some question:</p>
  
  <ol>
  <li>Is there another simple data structure to use, and that you able to make operations like <code>DFS</code>,<code>BFS</code>, <code>Find the Shortest-path</code> easier ? Or the data structure vary too much according to the problem to be solved ? </li>
  </ol>
  
  <p><strong>=== EDITED ===</strong></p>
  
  <p>I've tried to implement the data structure as bellow.</p>
  
  <p><strong>OBS</strong>: This approach seems simple, but I realize later that is not very suitable for a DFS, for example, since you need to keep track of the first element of the <code>LinkedList</code> all the time.In my solution Seems that is better to use a custom created Linked List, instead of
      <code>LinkedList&lt;Vertex&gt;</code>.</p>
  
  <p>Considering the comments bellow and to maintain simplicity I made some changes. But I don't know if that changes would affect further operations, like a <code>BFS</code>.
  To be able to have direct and indirect Graph I think is better to use an interface than a property.</p>
  
  <pre><code> public interface IGraph
      {
          void InsertEdge(int edgeAKey, int edgeBKey);
          void IsertNewVertex(int vertexKey);
          LinkedList&lt;Vertex&gt; FindByKey(int vertexKey);
          bool ExistKey(int vertexKey);
      }
  </code></pre>
  
  <p>To make it as simple as possible we can use already implemented data structures like <code>Dictionary</code> and <code>LinkedList</code>. And instead of using an <code>object</code> as <code>Dictionary key</code>, to make it simple we can create in <code>Vertex</code> a <code>key</code> (or <code>label</code>) and a <code>value</code>, if you would like to add a value that already exist in another <code>Vertex</code>.</p>
  
  <pre><code>public class GraphDirect : IGraph
      {
          private Dictionary&lt;int,LinkedList&lt;Vertex&gt;&gt; Vertexes { get; set; }
  
          public GraphDirect()
          {
              Vertexes = new Dictionary&lt;int, LinkedList&lt;Vertex&gt;&gt;();
          }
  
          public bool ExistKey(int vertexKey)
          {
              if (this.FindByKey(vertexKey) == null)
                  return false;
              else
                  return true;
          }
  
          public void IsertNewVertex(int vertexKey)
          {
              if (!this.ExistKey(vertexKey))
              {
                  Vertex vertex = new Vertex(vertexKey);
                  LinkedList&lt;Vertex&gt; listVertexes = new LinkedList&lt;Vertex&gt;();
                  listVertexes.AddFirst(vertex);
                  this.Vertexes.Add(vertexKey, listVertexes);
              }
          }
  
          public void InsertEdge(int vertexAKey, int vertexBKey)
          {
              //Create the vertex A, if it doesn't exist            
              if (!this.ExistKey(vertexAKey))
              {
                  this.IsertNewVertex(vertexAKey);
              } 
              //Will always insert the vertex B on this edge
              this.FindByKey(vertexAKey).AddLast(new Vertex(vertexBKey));
              //Create the vertex B, if doesn't exist
              if (!this.ExistKey(vertexBKey))
              {
                  this.IsertNewVertex(vertexBKey);
              }
          }
  
          public LinkedList&lt;Vertex&gt; FindByKey(int vertexKey)
          {
              if (this.Vertexes.ContainsKey(vertexKey))
                  return this.Vertexes[vertexKey];
  
              return null;
          }
  
      }
  </code></pre>
  
  <p>The Vertex class doesn't need any other pointer, just keep the <code>key</code> and a <code>value</code>, if necessary.</p>
  
  <pre><code>public enum State { Visited = 0, UnVisited = 1, Processed = 2 }
  
  public class Vertex
  {
      public int Key;
      public int Value;
      public State Status = State.UnVisited;
  
      public Vertex(int key)
      {
          this.Key = key;
          this.Value = 0;
      }
  
      public Vertex(int key, int value)
      {
          this.Key = key;
          this.Value = value;
      }
  }
  
  public class Start
  {
       public static void Main(){
           GraphDirect gDirect = new GraphDirect();
           gDirect.InsertEdge(2, 3);
           gDirect.InsertEdge(2, 8);
           gDirect.InsertEdge(5, 6);
       }
  }
  </code></pre>