dfs函数c语言 DFS函数

求解释一个C语言程序

#include stdio.h

成都创新互联公司是一家专业提供雨湖企业网站建设,专注与成都网站建设、成都网站设计、成都h5网站建设、小程序制作等业务。10年已为雨湖众多企业、政府机构等服务。创新互联专业网络公司优惠进行中。

#include string.h

int ans[10];

int m, n;

void DFS(int d, int p) // 需要第d个数，按顺序 从 p + 1 到 m 中选择

{

int i;

if (d == n) { // 如果已选出 n 个数，就输出

for (i = 0; i  n; i++)

printf("%d ", ans[i]);

printf("\n");

return;

}

for (i = p + 1; i = m; i++) {

ans[d] = i; // 选择 第 d 个数为 p +1 到 m ， 假设选择了 x 

DFS(d + 1, i); // 继续选择 第 d + 1 个数, 则选择范围是 x + 1 到 m

}

}

int main()

{

scanf("%d %d", m, n);  // 输入两个数 m, n

DFS(0, 0); // 第一个是 选出个数， 

return 0;

}

解释下哦：

比如 m = 3, n = 2;

首先调用  DFS(0, 0) 需要第 0 个数，选择范围从 0 + 1 到 m(3),

然后进入 for 循环 i = 0 + 1, 因此第一个数选择1，

继续 调用 DFS(1, 1) 需要第 1 个数，选择范围从 1 + 1 到 m(3),

然后进入新函数的循环 i = 1+1,因此第二个数选择 2 ,

继续 调用 DFS(2, 2) 需要第 2 个数，由于 2 等于n, 表明选择完成，输出 （ 1， 2）

退出函数DFS(2,2) 退回到 DFS(1, 1) 的下一个 for 循环：

循环 i = 2+1,因此第二个数选择 3 ,

继续 调用 DFS(2, 3) 需要第 2 个数，由于 2 等于n, 表明选择完成，输出 （ 1，3）

退出函数DFS(2,3) 退回到 DFS(1, 1) 的下一个 for 循换，循环条件不满足，DFS(1, 1) 执行结束返回到  DFS(0, 0) 继续执行 循环：

i = 1 + 1, 因此第一个数选择2，

继续 调用 DFS(1, 2) 需要第 1 个数，选择范围从 2 + 1 到 m(3),

然后进入新函数的循环 i = 2+1,因此第二个数选择 3 ,

继续 调用 DFS(2, 3) 需要第 2 个数，由于 2 等于n, 表明选择完成，输出 （ 2， 3）

退出函数DFS(2,3) 退回到 DFS(1, 2) 的下一个 for 循环： 循环条件不满足，DFS(1, 1) 执行结束返回到  DFS(0, 0) 继续执行

i = 2 + 1因此第一个数选择3，

继续 调用 DFS(1, 3) 需要第 1 个数，选择范围从 3 + 1 到 m(3),  很明显这里的循环将不能执行，因为循环条件是假的，因此退出 DFS(1, 3) 返回到 DFS(0, 0) 继续执行 循环：循环条件不满足。返回到 主程序 main

执行结束。

C语言编写深度优先搜索(DFS)是否需要回溯

我就是从pascal转到c多年的，这些算法和语言无关的，只是一种思想。都是怎样方便就怎样的，深搜我个人就喜欢直接写递归解决

求大神帮写一个c语言图的深度优先遍历，和广度优先遍历??

/*深度优先*/

#includestdio.h

#includestdlib.h

struct node/*图的顶点结构*/

{

int vertex;

int flag;

struct node *nextnode;

};

typedef struct node *graph;

struct node vertex_node[10];

void creat_graph(int *node,int n)

{

graph newnode,p;/*定义一个新结点及指针*/

int start,end,i;

for(i=0;in;i++)

{

start=node[i*2];/*边的起点*/

end=node[i*2+1];/*边的终点*/

newnode=(graph)malloc(sizeof(struct node));

newnode-vertex=end;/*新结点的内容为边终点处顶点的内容*/

newnode-nextnode=NULL;

p=(vertex_node);/*设置指针位置*/

while(p-nextnode!=NULL)

p=p-nextnode;/*寻找链尾*/

p-nextnode=newnode;/*在链尾处插入新结点*/

}

}

void dfs(int k)

{

graph p;

vertex_node[k].flag=1;/*将标志位置1，证明该结点已访问过*/

printf("vertex[%d]",k);

p=vertex_node[k].nextnode;/*指针指向下个结点*/

while(p!=NULL)

{

if(vertex_node[p-vertex].flag==0)/*判断该结点的标志位是否为0*/

dfs(p-vertex);/*继续遍历下个结点*/

p=p-nextnode;/*若已遍历过p指向下一个结点*/

}

}

main()

{

graph p;

int node[100],i,sn,vn;

printf("please input the number of sides:\n");

scanf("%d",sn);/*输入无向图的边数*/

printf("please input the number of vertexes\n");

scanf("%d",vn);

printf("please input the vertexes which connected by the sides:\n");

for(i=0;i4*sn;i++)

scanf("%d",node[i]);/*输入每个边所连接的两个顶点，起始及结束位置不同，每边输两次*/

for(i=1;i=vn;i++)

{

vertex_node[i].vertex=i;/*将每个顶点的信息存入数组中*/

vertex_node[i].nextnode=NULL;

}

creat_graph(node,2*sn);/*调用函数创建邻接表*/

printf("the result is:\n");

for(i=1;i=vn;i++)/*将邻接表内容输出*/

{

printf("vertex%d:",vertex_node[i].vertex);/*输出顶点内容*/

p=vertex_node[i].nextnode;

while(p!=NULL)

{

printf("-%3d",p-vertex);/*输出邻接顶点的内容*/

p=p-nextnode;/*指针指向下个邻接顶点*/

}

printf("\n");

}

printf("the result of depth-first search is:\n");

dfs(1);/*调用函数进行深度优先遍历*/

printf("\n");

}

/***************************广度优先*******************************/

#include stdio.h

#include stdlib.h

struct node

{

int vertex;

struct node *nextnode;

};

typedef struct node *graph;

struct node vertex_node[10];

#define MAXQUEUE 100

int queue[MAXQUEUE];

int front = - 1;

int rear = - 1;

int visited[10];

void creat_graph(int *node, int n)

{

graph newnode, p; /*定义一个新结点及指针*/

int start, end, i;

for (i = 0; i n; i++)

{

start = node[i *2]; /*边的起点*/

end = node[i *2+1]; /*边的终点*/

newnode = (graph)malloc(sizeof(struct node));

newnode-vertex = end; /*新结点的内容为边终点处顶点的内容*/

newnode-nextnode = NULL;

p = (vertex_node); /*设置指针位置*/

while (p-nextnode != NULL)

p = p-nextnode;

/*寻找链尾*/

p-nextnode = newnode; /*在链尾处插入新结点*/

}

}

int enqueue(int value) /*元素入队列*/

{

if (rear = MAXQUEUE)

return - 1;

rear++; /*移动队尾指针*/

queue[rear] = value;

}

int dequeue() /*元素出队列*/

{

if (front == rear)

return - 1;

front++; /*移动队头指针*/

return queue[front];

}

void bfs(int k) /*广度优先搜索*/

{

graph p;

enqueue(k); /*元素入队*/

visited[k] = 1;

printf("vertex[%d]", k);

while (front != rear)

/*判断是否对空*/

{

k = dequeue(); /*元素出队*/

p = vertex_node[k].nextnode;

while (p != NULL)

{

if (visited[p-vertex] == 0)

/*判断其是否被访问过*/

{

enqueue(p-vertex);

visited[p-vertex] = 1; /*访问过的元素置1*/

printf("vertex[%d]", p-vertex);

}

p = p-nextnode; /*访问下一个元素*/

}

}

}

main()

{

graph p;

int node[100], i, sn, vn;

printf("please input the number of sides:\n");

scanf("%d", sn); /*输入无向图的边数*/

printf("please input the number of vertexes\n");

scanf("%d", vn);

printf("please input the vertexes which connected by the sides:\n");

for (i = 0; i 4 *sn; i++)

scanf("%d", node[i]);

/*输入每个边所连接的两个顶点，起始及结束位置不同，每边输两次*/

for (i = 1; i = vn; i++)

{

vertex_node[i].vertex = i; /*将每个顶点的信息存入数组中*/

vertex_node[i].nextnode = NULL;

}

creat_graph(node, 2 *sn); /*调用函数创建邻接表*/

printf("the result is:\n");

for (i = 1; i = vn; i++)

/*将邻接表内容输出*/

{

printf("vertex%d:", vertex_node[i].vertex); /*输出顶点内容*/

p = vertex_node[i].nextnode;

while (p != NULL)

{

printf("-%3d", p-vertex); /*输出邻接顶点的内容*/

p = p-nextnode; /*指针指向下个邻接顶点*/

}

printf("\n");

}

printf("the result of breadth-first search is:\n");

bfs(1); /*调用函数进行深度优先遍历*/

printf("\n");

}

数据结构C语言版 图的遍历 DFS和BFS算法，用邻接矩阵储存 急阿在线等 求大神指点

#include iostream

#includestring.h

#includestack

#includequeue

const int Max=100;

const int VISITED=101010;

const int UNVISITED=111111;

const int AFFINITY=101010;

const int INFINITY=111111;

using namespace std;

class Edge

{

public:

int start;

int end;

int weight;

Edge(int st=0,int en=0,int w=0):start(st),end(en),weight(w){}

bool operator(Edge oneEdge){return weightoneEdge.weight?true:false;}

bool operator(Edge oneEdge){return weightoneEdge.weight?true:false;}

bool operator!=(Edge oneEdge)

{

if(weight!=oneEdge.weight||start!=oneEdge.start||end!=oneEdge.end)

return true;

return false;

}

};

class AdjGraf

{

private:

int verticesNum;

int edgeNum;

int **matrix;

int *Mark;

public:

AdjGraf(int vert)

{

int i=0,j=0;

verticesNum=vert;

matrix=(int**)new int*[vert];

for(i=0;ivert;i++)

matrix[i]=new int[vert];

Mark=new int[vert];

for(i=0;ivert;i++)

for(j=0;jvert;j++)

{

matrix[i][j]=0;

}

for( int m=0;mverticesNum;m++)

Mark[m]=UNVISITED;

}

~AdjGraf();

//返回与顶点oneVertex相关联的第一条边

Edge FirstEdge(int oneVertex);

//返回与边PreEdge有相同关联顶点oneVertex的下一条边

Edge NextEdge( Edge preEdge);

//添加一条边

void setEdge(int fromVertex,int toVertex,int weight);

//删一条边

void delEdge(int fromVertex,int toVertex);

//如果oneEdge是边则返回TRUE，否则返回FALSE

bool IsEdge( Edge oneEdge)

{

if(oneEdge.start=0oneEdge.startverticesNum

oneEdge.end=0oneEdge.endverticesNum)

return true;

else return false;

}

//返回边oneEdge的始点

int FromVertex(Edge oneEdge){return oneEdge.start;}

//返回边oneEdge的终点

int ToVertex(Edge oneEdge){return oneEdge.end;}

//返回边oneEdge的权

int Weight(Edge oneEdge){return oneEdge.weight;}

void visit(int i){couti+1" ";}

void BFS(int i=1);

void DFS(int i);

void DFSTraverse(int v);

void DFSNoReverse(int f=1);

Edge UNVISITEDEdge(int f);

};

AdjGraf::~AdjGraf()

{

for(int i=0;iverticesNum;i++)

delete[]matrix[i];

delete[]matrix;

}

Edge AdjGraf::FirstEdge(int oneVertex)

{ int i;

Edge tempEdge;

tempEdge.start=oneVertex;

for( i=0;iverticesNum;i++)

if(matrix[oneVertex][i]!=0)

break;

tempEdge.end=i;

tempEdge.weight=matrix[oneVertex][i];

return tempEdge;

}

Edge AdjGraf ::NextEdge( Edge preEdge)

{

Edge tempEdge;

tempEdge.start=preEdge.start;

int i=0;

for(i=preEdge.end+1;iverticesNum;i++)

if(matrix[preEdge.start][i]!=0)

break;

tempEdge.end=i;

tempEdge.weight=matrix[preEdge.start][i];

return tempEdge;

}

void AdjGraf::setEdge(int fromVertex,int toVertex,int weight)

{

if(matrix[fromVertex-1][toVertex-1]==0)

edgeNum++;

matrix[fromVertex-1][toVertex-1]=weight;

}

void AdjGraf::delEdge(int fromVertex,int toVertex)

{

if(matrix[fromVertex][toVertex]==0)

edgeNum--;

matrix[fromVertex][toVertex]=0;

}

/*************递归实现深度优先****************/

void AdjGraf::DFS(int i)

{

visit(i);

Mark[i]=VISITED;

for(Edge e=FirstEdge(i);IsEdge(e);e=NextEdge(e))

if(Mark[ToVertex(e)] == UNVISITED)

DFS(ToVertex(e));

}

void AdjGraf::DFSTraverse(int v)

{

v--;

int i;

for(i=0;iverticesNum;i++)

Mark[i]=UNVISITED;

for(i=v;iv+verticesNum;i++)

if (Mark[i]== UNVISITED)

DFS(i);

}

Edge AdjGraf::UNVISITEDEdge(int f)

{ int i;

for( Edge e=FirstEdge(f);IsEdge(e);e=NextEdge(e))

if(Mark[e.end]==UNVISITED)

return e;

return Edge(verticesNum,verticesNum,0) ;

}

/*************非递归实现深度优先**************/

void AdjGraf::DFSNoReverse(int f)

{

f--;

int i,counter=0,j,flag;

stackintTemp;

for(i=0;iverticesNum;i++)

Mark[i]=UNVISITED;

flag=f;

while(counter12)

{

while(flag!=verticesNumIsEdge(UNVISITEDEdge(flag))||!Temp.empty())

{

// Edge tempEdge=UNVISITEDEdge(j);

while(flag!=verticesNumMark[flag]==UNVISITED)

{

visit(flag);

Mark[flag]=VISITED;

Temp.push(flag);

flag=UNVISITEDEdge(flag).end;

}

if(!Temp.empty())

{

flag=UNVISITEDEdge(Temp.top()).end;

Temp.pop();

}

}

if(Mark[counter]==UNVISITED) flag=counter;

else counter++;

}

}

/*************非递归实现广度优先**************/

void AdjGraf::BFS(int v)

{

int i;

v--;

for( i=0;iverticesNum;i++)

Mark[i]=UNVISITED;

queueinttempqueue;

i=0;

/*********v先从指定位置开始，然后从v=0,1,2......

依次检查是否有孤立结点*****************/

while(iverticesNum)

{

tempqueue.push(v);

while(!tempqueue.empty())

{

v=tempqueue.front();

tempqueue.pop();

if(Mark[v]==UNVISITED)

{

visit(v);

Mark[v]=VISITED;

for(Edge e=FirstEdge(v);IsEdge(e);e=NextEdge(e))

{

v=ToVertex(e);

tempqueue.push(v);

}

}

}

/***********防止出现孤立点****************/

if(Mark[i]==VISITED) i++;

else v=i;

}

}

int main()

{

AdjGraf Graph(12);

Graph.setEdge(1,2,1);

Graph.setEdge(2,1,1);

Graph.setEdge(1,3,5);

Graph.setEdge(3,1,5);/** V1 V12 V11 */

Graph.setEdge(2,4,3);/** / \ / \ */

Graph.setEdge(4,2,3);/** v2 v3 V10 V9 */

Graph.setEdge(2,5,7);/** / \ / \ */

Graph.setEdge(5,2,7);/** v4 v5 v6-v7 */

Graph.setEdge(4,8,4);/** \ / */

Graph.setEdge(8,4,4);/** v8 */

Graph.setEdge(5,8,3);

Graph.setEdge(8,5,3);

Graph.setEdge(3,6,2);

Graph.setEdge(6,3,2);

Graph.setEdge(3,7,1);

Graph.setEdge(7,3,1);

Graph.setEdge(6,7,6);

Graph.setEdge(7,6,6);

Graph.setEdge(12,9,6);

Graph.setEdge(9,12,6);

Graph.setEdge(12,10,6);

Graph.setEdge(10,12,6);

Graph.setEdge(11,11,6);

cout"DFSTraverse:"endl;

Graph.DFSTraverse(3);

coutendl;

cout"DFSNoReverse:"endl;

Graph.DFSNoReverse(3);

coutendl;

cout"BFS:"endl;

Graph.BFS(3);

coutendl;

return 0;

}

以上代码运行环境codeblocks 程序采用DFS递归算法 DFS非递归算法 BFS非递归算法

望采纳~