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;
}