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

你还在原价购买阿里云、腾讯云、华为云、天翼云产品？那就亏大啦！现在申请成为四大品牌云厂商VIP用户，可以3折优惠价购买云服务器等云产品，并且可享四大云服务商产品终身VIP优惠价，还等什么？赶紧点击下面对应链接免费申请VIP客户吧：

1、点击这里立即申请成为腾讯云VIP客户

2、点击这里立即注册成为天翼云VIP客户

3、点击这里立即申请成为华为云VIP客户

4、点击这里立享阿里云产品终身VIP优惠价

喜欢 (0)赏

[[email protected]]

分享 (0)