Find all paths from start node to the end node in a graph
<p>Here is my question.</p>

<p>I am trying to resolve this problem. </p>

<blockquote>
  <p>Given the start point and the end point, find all paths from start
  corner to the end corner. Include only routes which do not pass
  through any corner more than once.</p>
</blockquote>

<p>For example: 1 is the start node, 6 is the end point. I have the the data as</p>

<pre><code>1 2
1 3
3 4
3 5
4 6
5 6
2 3
2 4
</code></pre>

<p>The pairs of positive integers separated by blanks which are connected.
So the output should be.</p>

<pre><code>1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
</code></pre>

<p>There are 7 routes from 1 to 6.</p>

<p>Now I use the graph search algorithm, I can only find one. And also I can't find the one given the final destination. I mean that I can only traversal the graph.</p>

<p>What I did was that I created the adjacency matrix of the graph then did a depth first search. </p>

<p>First I defined a class <code>Node</code>.</p>

<pre><code>public class Node
{
    public string NodeId;
    public bool IsVisited;
    public Node(string nodeId)
    {
        NodeId = nodeId;
    }
}
</code></pre>

<p>Then the <code>Graph</code> class,</p>

<pre><code> public class Graph
{
    private Node[] _nodes;
    private int[][] _adjacencyMatrix;
    public int _numberOfTotalNodes;
    public Graph(int[][] adjacencyMatrix, int numberOfTotalNodes)
    {
        _adjacencyMatrix = adjacencyMatrix;
        _numberOfTotalNodes = numberOfTotalNodes;
        _nodes = new Node[_numberOfTotalNodes];
        for (int i = 0; i &lt; _numberOfTotalNodes; i++)
        {
            _nodes[i] = new Node((i + 1).ToString());
        }
    }

    public void DepthFirstSearch()
    {
        Stack s = new Stack();
        _nodes[0].IsVisited = true;
        DisplayNodeId(0);
        s.Push(0);
        int v;
        while (s.Count &gt; 0)
        {
            v = GetAdjUnvisitedNode((int)s.Peek());
            if (v == -1 || _nodes[v].IsVisited)
            {
                s.Pop();
            }
            else
            {
                _nodes[v].IsVisited = true;
                DisplayNodeId(v);
                s.Push(v);
            }
        }
        for (int u = 0; u &lt; _numberOfTotalNodes; u++)
        {
            _nodes[u].IsVisited = false;
        }
    }

    public void DisplayNodeId(int nodePosition)
    {
        Console.Write(_nodes[nodePosition].NodeId + " ");
    }

    public int GetAdjUnvisitedNode(int v)
    {
        for (int j = 0; j &lt; _numberOfTotalNodes; j++)
        {
            if (_adjacencyMatrix[v][j] == 1 &amp;&amp; _nodes[j].IsVisited == false)
            {
                return j;
            }
        }
        return -1;
    }
}
</code></pre>

<p>To call it, just use the code.</p>

<pre><code>var graph = new Graph(adjacenyMatrix, adjacenyMatrix.GetLength(0));
graph.DepthFirstSearch();
</code></pre>

<p>Please point it out the flaws of my algorithm. </p>

<p>Base on the comment, there is a <a href="https://stackoverflow.com/questions/58306/graph-algorithm-to-find-all-connections-between-two-arbitrary-vertices">solution</a> there, I would like C# code. However it is not completed. It lacks of the method <code>AdjacentNodes(T current)</code>.</p>