DFS

​
一般步骤
（1） 把初始状态放入数组中，设为当前状态；
（2） 扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态；
（3） 判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态；
（4） 判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。
（5） 如果数组为空，说明无解。

#include<stdio.h>
#include<stdlib.h>
#define MAX_VALUE 100
int visit[MAX_VALUE];
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode*nextarc;
}ArcNode;
typedef struct VNode
{
    int data;
    ArcNode*firstarc;
}VNode,AdjList[MAX_VALUE];
typedef struct
{
    AdjList vertices;
    int vexnum, arcnum;
}ALGraph;
int LocateVex(ALGraph G, int v)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        if (G.vertices[i].data == v)
        {
            return i;
        }
    }
}
void CreatUDG(ALGraph *G)
{
    ArcNode*p, *q;
    int i, j,v1, v2;
    printf("分别输入顶点个数和边的个数：\n");
    scanf("%d%d", &(G->vexnum), &(G->arcnum));
    printf("请输入各个顶点的值：\n");
    for (int i = 0; i < G->vexnum; i++)
    {
        scanf("%d", &(G->vertices[i].data));
        G->vertices[i].firstarc = NULL;
    }
    printf("分别输入各条边的两个顶点：\n");
    for (int k = 0; k < G->arcnum; k++)
    {
        scanf("%d%d", &v1, &v2);
        i = LocateVex(*G, v1);
        j = LocateVex(*G, v2);
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = NULL;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
        q = (ArcNode*)malloc(sizeof(ArcNode));
        q->adjvex = i;
        q->nextarc = NULL;
        q->nextarc = G->vertices[j].firstarc;
        G->vertices[j].firstarc = q;
    }
}
void PrintUDG(ALGraph G)
{
    ArcNode*p = NULL;
    for (int i = 0; i < G.vexnum; i++)
    {
        printf("第%d条边\n", i + 1);
        p = G.vertices[i].firstarc;
        while (p != NULL)
        {
            printf("%d  ", (p->adjvex)+1);
            p = p->nextarc;
        }
        printf("\n");
    }
}
void DFS(ALGraph G, int v)
{
    ArcNode*p;
    visit[v] = 1;
    printf("%d  ", G.vertices[v].data);
    p = G.vertices[v].firstarc;
    while (p != NULL)
    {
        if (!visit[p->adjvex] )
        {
            DFS(G, p->adjvex);
        }
        //当递归找到出口时 此时就会运行到下面的语句 即一个结点的遍历走到了头  
        //此时 再向后走  例如 第一条边的邻接表为 1 2 3  那么当2找到递归出口后
        //我们还要进行3的遍历  所以要有语句p=p->nextarc
        p = p->nextarc;
    }
}
void DFST(ALGraph G)//该函数用于不是连通图的时候 可以用for循环进行深度优先遍历
{
    for (int i = 0; i < G.vexnum; i++)
    {
        visit[i] = 0;
    }
    for (int i = 0; i < G.vexnum; i++)
    {
        if (!visit[i])
        {
            printf("\n第%d次调用\n", i);
            DFS(G, i);
        }
    }
}
int main()
{
    ALGraph G;
    CreatUDG(&G);
    PrintUDG(G);
    DFST(G);
    return 0;
}