图的遍历，即是对节点的访问。一个图有那么多个节点，如何遍历这些节点，需要特定的策略。
图的搜索有两种方式，一种是深度优先搜索（Depth-First-Search），另一种是广度优先搜索（Breadth-First-Search）

深度优先搜索的思想

1. 深度优先遍历，从初始访问节点出发，初始访问节点可能有多个邻接节点，深度优先搜索算法的策略就是首先访问第一个邻接节点，然后再以这个被访问的邻接节点作为初始节点，访问它的第一个邻接节点。就是说每次都在访问完当前节点后首先访问当前节点的第一个邻接节点。
2. 我们可以看到，这样的访问策略是优先往纵向进行挖掘深入，而不是对一个节点的所有邻接节点进行横向访问。

3. 显然，深度优先搜索算法是一个递归的过程

   深度优先搜索算法步骤

4. 访问初始节点v，并标记节点v为已访问。

5. 查找节点v的第一个邻接节点w
6. 若w存在，则继续执行4，如果w不存在，则回到第一步，将从v的下一个节点继续
7. 若w未被访问，对w进行深度优先搜索递归（即把w当做是另一个v，然后进行步骤123）
8. 如果这里w（当做初始节点v）被访问过了，查找w的下一个邻接节点，转到3

代码

using System;
using System.Collections.Generic;
using System.Text;
namespace ConsoleApp1
{
    public class Graph
    {
        public List<string> vertexList;//存储顶点集合
        public int[,] edges;//存储图对应的邻接矩阵
        public int numOfEdges;//表示边的数目
        public bool[] isVisited;//存放顶点是否被访问
        public Graph(int n)//n顶点的个数
        {
            //初始化矩阵和vertexList
            edges = new int[n, n];
            vertexList = new List<string>(n);
            isVisited = new bool[n];
        }
        //插入顶点
        public void insertVertex(string vertex)
        {
            vertexList.Add(vertex);
        }
        /// <summary>
        /// 添加边
        /// </summary>
        /// <param name="v1">第一个顶点的下标</param>
        /// <param name="v2">第二个顶点的下标</param>
        /// <param name="weight">权值</param>
        public void insertEdge(int v1,int v2,int weight)
        {
            //因为是无向表，所以v1-v2和v2-v1都需要标记
            edges[v1, v2] = weight;
            edges[v2, v1] = weight;
            numOfEdges++;//两点之间只有一条边
        }
        //显示图对应的矩阵
        public void showGraph()
        {
            for(int i = 0; i < edges.GetLength(0); i++)
            {
                for(int t = 0; t < edges.GetLength(1); t++)
                {
                    Console.Write(edges[i,t]+" ");
                }
                Console.WriteLine();
            }
        }
        #region 深度优先搜索
        //得到第一个邻接节点的下标w
        public int getFirstNeighbor(int index)
        {
            for(int j = 0; j < vertexList.Count; j++)
            {
                if (edges[index, j] > 0)
                    return j;
            }
            return -1;
        }
        //根据前一个邻接节点的下标，来获取下一个邻接节点
        public int getNextNeighbor(int v1,int v2)
        {
            for(int j = v2 + 1; j < vertexList.Count; j++)
            {
                if (edges[v1, j] > 0)
                    return j;
            }
            return -1;
        }
        //深度优先搜索算法
        //i第一次是0
        private void DFS(bool[] isVisited,int i)
        {
            //首先我们访问该节点，输出
            Console.Write(vertexList[i]+"->");
            //将这个节点设置为已经访问过
            isVisited[i] = true;
            //查找节点i的第一个邻接节点w
            int w = getFirstNeighbor(i);
            while (w != -1)//有节点
            {
                if (!isVisited[w])
                    DFS(isVisited, w);
                //如果w已经被访问了
                w = getNextNeighbor(i, w);
            }
        }
        public void DFS()
        {
            for(int i = 0; i < vertexList.Count; i++)
            {
                if (!isVisited[i])
                    DFS(isVisited, i);
            }
        }
        #endregion
    }
}