简例浅析深度优先搜索（Depth-First-Search）

深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次 。

需要注意的关键词：一条路走到黑、回溯、邻接矩阵、辅助数组。

深度优先搜索的内容体现在遍历上，下面是最基础最简单的无向图的遍历方法。

图如下：

代码如下（含注释）：

#include <iostream>
#include <algorithm>
using namespace std;

 void dfs(int v,int visit[],int neigh[][7])
{
    cout << v;
    visit[v] = 1;//标记已到达
    for(int i=0;i<7;i++)
    {
        if(neigh[v][i]!=0&&visit[i]!=1)//顺序查找没去过的相邻接点
        {
            dfs(i,visit,neigh);//递归
        }
    }
}

int main()
{
    int neighbor[7][7] = {{0,1,1,0,0,0,0},{1,0,0,1,1,0,0},{1,0,0,0,0,1,1},{0,1,0,0,0,0,0},{0,1,0,0,0,1,0},{0,0,1,0,1,0,0},{0,0,1,0,0,0,0}};//建立邻接矩阵
    int visited[7] = {0,0,0,0,0,0,0};//建立辅助数组
    dfs(0,visited,neighbor);
    return 0;
}

使用邻接表遍历：

#include <iostream>
#include <algorithm>
using namespace std;

typedef struct ListNode
{
    int nei;
    struct ListNode * next;
}Nei;

Nei* Creat(int n)
{
    Nei * head = new Nei; //建立头链表
    Nei * pre = head; //存储上一链表
    for(int i = 0; i < n; i++)
    {
        Nei * p = new Nei;
        cin >> p->nei;
        pre->next = p;
        pre = p;
        p->next = NULL;
    }
    return head;
}

 void dfs(int v,int visit[],Nei* neilist[])
{
    cout << v;
    visit[v] = 1;//标记已到达
    Nei* p = neilist[v];
    while(p->next!=NULL)//仍有下一个邻接点
    {
        if(visit[p->nei]!=1)//没访问，访问
        {
            dfs(p->nei,visit,neilist);
        }
        else//访问了，下一个
        {
            p = p->next;
        }
    }
        if(visit[p->nei]!=1)//最后一个邻接点的处理
    {
        dfs(p->nei,visit,neilist);
    }
}

int main()
{
    int visited[7] = {0,0,0,0,0,0,0};//建立辅助数组
    int neinum[7] = {2,3,3,1,2,2,1};//邻接点数
    Nei* neilist[7];//建立邻接表
    for (int i = 0;i < 7;i++)
    {
        cout << "创建第" << i << "个节点的链表" << endl;
        neilist[i] = Creat(neinum[i])->next;//存入1节点
    }

    dfs(0,visited,neilist);
    return 0;
}

输出：0134526

非递归做法介绍：

void bfs()
{
    stack<int> s;
    s.push(head);
    visit[v]=true;
    while(!s.empty())
    {
        v=s.top();
        if(该节点邻接表不为空)
        {
            s.push(arr[0]);
            visit[arr[0]]=true;
        }else
        {
            pop(v)
        }
    }
}