#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
执行结束。
我就是从pascal转到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");
}
#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非递归算法
望采纳~