DFS深度优先搜索

深度优先搜索（Depth - First - Search）是一种用于遍历或搜索图（包括树，树是一种特殊的图）的算法。

它的基本思想是从起始顶点开始，沿着一条路径尽可能深地探索，直到无法继续或者达到目标，然后回溯到前一步，继续探索其他分支。这种搜索策略就像走迷宫一样，一直沿着一条路走，直到碰壁，然后回头尝试其他的路。

深度优先搜索在树中的应用（以二叉树为例）

二叉树，深度优先搜索也很常见。以下是一个简单的二叉树节点类和深度优先搜索方法的定义

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _12_7DFS
{
    internal class Program
    {
        static void Main(string[] args)
        {
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(2);
            root.right = new TreeNode(3);
            root.left.left = new TreeNode(4);
            root.left.right = new TreeNode(5);
            BinaryTree bt = new BinaryTree();
            Console.WriteLine("二叉树深度优先搜索结果：");
            bt.DFS(root);
        }
    }
    class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
        {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class BinaryTree
    {
        public void DFS(TreeNode root)
        {
            if (root == null)
            {
                return;
            }
            Console.Write(root.val + " ");
            DFS(root.left);
            DFS(root.right);
        }
    }
}

深度优先搜索在树中的应用（以图的邻接矩阵表示为例）

假设我们有一个简单的无向图，用邻接矩阵来表示。以下是一个定义图的类，其中包含了深度优先搜索的方法

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


namespace 实例二
{
    internal class Program
    {
        static void Main(string[] args)
        {
            Graph g = new Graph(4);
            g.AddEdge(0, 1);
            g.AddEdge(0, 2);
            g.AddEdge(1, 2);
            g.AddEdge(2, 3);
            Console.WriteLine("深度优先搜索结果（从顶点0开始）：");
            g.DFS(0);
        }
    }
    class Graph
    {
        private int[,] adjacencyMatrix;
        private int numVertices;
        public Graph(int numVertices)
        {
            this.numVertices = numVertices;
            adjacencyMatrix = new int[numVertices, numVertices];
        }
        public void AddEdge(int v1, int v2)
        {
            adjacencyMatrix[v1, v2] = 1;
            adjacencyMatrix[v2, v1] = 1;
        }
        private void DFSUtil(int vertex, bool[] visited)
        {
            visited[vertex] = true;
            Console.Write(vertex + " ");
            for (int i = 0; i < numVertices; i++)
            {
                if (adjacencyMatrix[vertex, i] == 1 && !visited[i])
                {
                    DFSUtil(i, visited);
                }
            }
        }
        public void DFS(int startVertex)
        {
            bool[] visited = new bool[numVertices];
            DFSUtil(startVertex, visited);
        }
    }
}