c语言深度优先搜索
‘壹’ 数据结构（c语言版） 第七章 图 图的深度优先搜索算法实现 能告诉我吗。
void DFS(ALGraph *G,int v) //邻接表存储的图和顶点编号，深度遍历递归算法
{
ArcNode *p; //弧结构指针
visited[v]=1; //记录当前访问的节点，表示此节点已访问过
printf("%d",v); //输出节点编号
p=G->adjlist[v].firstarc; //弧指针指向与该节点相邻的另一条弧
while(p!=NULL) //只要该节点还有弧没有访问完就循环
{
if(visited[p->adjvex]==0) //若该弧所指向的那个节点没有访问过
DFS(G,p->adjvex); //则以该弧指向的下一个节点为顶点深度遍历
p=p->nextarc; //否则指针转向另一条弧看是否有被访问过
}
}
‘贰’ 急！！如何用C语言建立一个图和图的深度优先搜索遍历，举个例子就行，要代码！！谢谢！！
/* ======================================== */
/* 图形的深度优先搜寻法 */
/* ======================================== */
#include <stdlib.h>
struct node /* 图形顶点结构宣告 */
{
int vertex; /* 顶点资料 */
struct node *nextnode; /* 指下一顶点的指标 */
};
typedef struct node *graph; /* 图形的结构新型态 */
struct node head[9]; /* 图形顶点结构数组 */
int visited[9]; /* 遍历记录数组 */
/* ---------------------------------------- */
/* 建立图形 */
/* ---------------------------------------- */
void creategraph(int *node,int num)
{
graph newnode; /* 新顶点指标 */
graph ptr;
int from; /* 边线的起点 */
int to; /* 边线的终点 */
int i;
for ( i = 0; i < num; i++ ) /* 读取边线的回路 */
{
from = node[i*2]; /* 边线的起点 */
to = node[i*2+1]; /* 边线的终点 */
/* 建立新顶点记忆体 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 建立顶点内容 */
newnode->nextnode = NULL; /* 设定指标初值 */
ptr = &(head[from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入结尾 */
}
}
/* ---------------------------------------- */
/* 图形的深度优先搜寻法 */
/* ---------------------------------------- */
void dfs(int current)
{
graph ptr;
visited[current] = 1; /* 记录已遍历过 */
printf("顶点[%d] ",current); /* 印出遍历顶点值 */
ptr = head[current].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如过没遍历过 */
dfs(ptr->vertex); /* 递回遍历呼叫 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
}
/* ---------------------------------------- */
/* 主程式: 建立图形后,将遍历内容印出. */
/* ---------------------------------------- */
void main()
{
graph ptr;
int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 */
{1, 3}, {3, 1},
{2, 4}, {4, 2},
{2, 5}, {5, 2},
{3, 6}, {6, 3},
{3, 7}, {7, 3},
{4, 8}, {8, 4},
{5, 8}, {8, 5},
{6, 8}, {8, 6},
{7, 8}, {8, 7} };
int i;
for ( i = 1; i <= 8; i++ )
{
head[i].vertex = i; /* 设定顶点值 */
head[i].nextnode = NULL; /* 清除图形指标 */
visited[i] = 0; /* 设定遍历初值 */
}
creategraph(node,20); /* 建立图形 */
printf("图形的邻接链表内容:\n");
for ( i = 1; i <= 8; i++ )
{
printf("顶点%d =>",head[i].vertex); /* 顶点值 */
ptr = head[i].nextnode; /* 顶点位置 */
while ( ptr != NULL ) /* 遍历至链表尾 */
{
printf(" %d ",ptr->vertex); /* 印出顶点内容 */
ptr = ptr->nextnode; /* 下一个顶点 */
}
printf("\n"); /* 换行 */
}
printf("图形的深度优先遍历内容:\n");
dfs(1); /* 印出遍历过程 */
printf("\n"); /* 换行 */
}
‘叁’ c语言深度优先搜索。代码
#include<stdlib.h>
#include<stdio.h>
structnode/*图顶点结构定义*/
{
intvertex;/*顶点数据信息*/
structnode*nextnode;/*指下一顶点的指标*/
};
typedefstructnode*graph;/*图形的结构新型态*/
structnodehead[9];/*图形顶点数组*/
intvisited[9];/*遍历标记数组*/
/********************根据已有的信息建立邻接表********************/
voidcreategraph(intnode[20][2],intnum)/*num指的是图的边数*/
{
graphnewnode;/*指向新节点的指针定义*/
graphptr;
intfrom;/*边的起点*/
intto;/*边的终点*/
inti;
for(i=0;i<num;i++)/*读取边线信息，插入邻接表*/
{
from=node[i][0];/*边线的起点*/
to=node[i][1];/*边线的终点*/
/*建立新顶点*/
newnode=(graph)malloc(sizeof(structnode));
newnode->vertex=to;/*建立顶点内容*/
newnode->nextnode=NULL;/*设定指标初值*/
ptr=&(head[from]);/*顶点位置*/
while(ptr->nextnode!=NULL)/*遍历至链表尾*/
ptr=ptr->nextnode;/*下一个顶点*/
ptr->nextnode=newnode;/*插入节点*/
}
}
/**********************图的深度优先搜寻法********************/
voiddfs(intcurrent)
{
graphptr;
visited[current]=1;/*记录已遍历过*/
printf("vertex[%d] ",current);/*输出遍历顶点值*/
ptr=head[current].nextnode;/*顶点位置*/
while(ptr!=NULL)/*遍历至链表尾*/
{
if(visited[ptr->vertex]==0)/*如过没遍历过*/
dfs(ptr->vertex);/*递回遍历呼叫*/
ptr=ptr->nextnode;/*下一个顶点*/
}
}
/******************************主程序******************************/
intmain()
{
graphptr;
intnode[20][2]={{1,2},{2,1},/*边线数组*/
{1,3},{3,1},
{1,4},{4,1},
{2,5},{5,2},
{2,6},{6,2},
{3,7},{7,3},
{4,7},{4,4},
{5,8},{8,5},
{6,7},{7,6},
{7,8},{8,7}};
inti;
//clrscr();
for(i=1;i<=8;i++)/*顶点数组初始化*/
{
head[i].vertex=i;/*设定顶点值*/
head[i].nextnode=NULL;/*指针为空*/
visited[i]=0;/*设定遍历初始标志*/
}
creategraph(node,20);/*建立邻接表*/
printf("Contentofthegragh'sADlistis: ");
for(i=1;i<=8;i++)
{
printf("vertex%d->",head[i].vertex);/*顶点值*/
ptr=head[i].nextnode;/*顶点位置*/
while(ptr!=NULL)/*遍历至链表尾*/
{
printf("%d",ptr->vertex);/*印出顶点内容*/
ptr=ptr->nextnode;/*下一个顶点*/
}
printf(" ");/*换行*/
}
printf(" Theendofthedfsare: ");
dfs(1);/*打印输出遍历过程*/
printf(" ");/*换行*/
puts("Pressanykeytoquit...");
//getch();
}
‘肆’ 从键盘输入的数据创建图（图的存储结构采用邻接表）进行深度优先搜索和广度优先搜 求一条C语言编的程序
数据结构这个东西，你的定义不同写出来的东西也就不同了,好吧，这是我写的一个东西，写的有点仓促有点丑哈····
#define MAXSIZE 100
typedef char elemtype;
typedef struct arc
{
int index;
arc *nextarc;
}ARCNODE,*ARC;
typedef struct VER
{
elemtype data;
ARC firstarc;
}VERNODE;
typedef struct
{
VERNODE vertex[MAXSIZE];
int numVer;
int numArc;
}ADJGRAPH;
//递归实现深度优先
void dfs(ADJGRAPH *g,int pos,int *visit,void (*pf)(elemtype))
{
ARCNODE *p = g->vertex[pos].firstarc;
visit[pos] = 1;
pf(g->vertex[pos].data);
while(p)
{
if (!visit[p->index])
{
dfs(g,p->index,visit);
}
p = p->nextarc;
}
}
void dfs_traverse(ADJGRAPH *g,int pos)
{
int *visit = (int *)malloc(sizeof(int)*(g->numVer));
for (int i = 0;i<g->numVer;i++)
{
visit[i] = 0;
}
dfs(g,pos,visit);
for (int i = 0;i<g->numVer;i++)
{
if (!visit[i])
{
dfs(g,i,visit);
}
}
}
//栈实现深度优先
void dfs_traverse_inrecursion(ADJGRAPH *g,void (*pf)(elemtype))
{
ARCNODE *p;
ARCNODE *stack[MAXSIZE];//链栈更好
int visit[MAXSIZE] = {0};
int top = 0;
for (int pos = 0;pos < g->numVer;pos++)
{
if (!visit[pos])
{
p = g->vertex[pos].firstarc;
pf(g->vertex[pos].data);
visit[pos] = 1;
while (p||top)
{
while (p&&!visit[p->index])
{
pf(g->vertex[p->index].data);
visit[p->index] = 1;
stack[top++] = p;
p = g->vertex[p->index].firstarc;
}
if(top)
p = stack[--top]->nextarc;
else
p = p->nextarc;
}
}
}
}
//广度优先
void bfs_traverse(ADJGRAPH *g,void (*pf)(elemtype))
{
ARCNODE *queue[MAXSIZE];//链队列更好
ARCNODE *p;
int rear = 0,front = 0;
int visit[MAXSIZE] = {0};
for(int pos = 0;pos<g->numVer;pos++)
{
p = g->vertex[pos].firstarc;
if(!visit[pos])
{
pf(g->vertex[pos].data);
visit[pos] = 1;
}
while(p||rear != front)
{
while(p)
{
queue[front++] = p;
p = p->nextarc;
}
if(rear != front)
{
p = queue[rear++];
if(!visit[p->index])
{
pf(g->vertex[p->index].data);
visit[p->index] = 1;
}
p = g->vertex[p->index].firstarc;
}
else
p = g->vertex[p->index].firstarc;
}
}
}
‘伍’ C语言数据结构（有向图的深度优先遍历）
对的
深度优先顾名思义就是先向深的地方遍历
按照你上面的图来说，就是这样的
广度优先的话就是先搜索相邻节点
顺序是a b c d--这个是广度优先
深度优先的图最好不要存在环...那样会出现问题
‘陆’ 求c语言图的深度优先遍历算法
#define MaxVerNum 100 /* 最大顶点数为*/
typedef enum {False,True} boolean;
#include "stdio.h"
#include "stdlib.h"
boolean visited[MaxVerNum];
typedef struct node /* 表结点*/
{
int adjvex;/* 邻接点域,一般是放顶点对应的序号或在表头向量中的下标*/
char Info; /*与边(或弧)相关的信息*/
struct node * next; /* 指向下一个邻接点的指针域*/
} EdgeNode;
typedef struct vnode /* 顶点结点*/
{
char vertex; /* 顶点域*/
EdgeNode * firstedge; /* 边表头指针*/
} VertexNode;
typedef struct
{
VertexNode adjlist[MaxVerNum]; /* 邻接表*/
int n,e; /* 顶点数和边数*/
} ALGraph; /* ALGraph是以邻接表方式存储的图类型*/
//建立一个无向图的邻接表存储的算法如下：
void CreateALGraph(ALGraph *G)/* 建立有向图的邻接表存储*/
{
int i,j,k;
int N,E;
EdgeNode *p;
printf("请输入顶点数和边数：");
scanf("%d %d",&G->n,&G->e);
printf("n=%d,e=%d\n\n",G->n,G->e);
getchar();
for(i=0;i<G->n;i++) /* 建立有n个顶点的顶点表*/
{
printf("请输入第%d个顶点字符信息(共%d个)：",i+1,G->n);
scanf("%c",&(G->adjlist[i].vertex)); /* 读入顶点信息*/
getchar();
G->adjlist[i].firstedge=NULL; /* 顶点的边表头指针设为空*/
}
for(k=0;k<2*G->e;k++) /* 建立边表*/
{
printf("请输入边<Vi,Vj>对应的顶点序号(共%d个)：",2*G->e);
scanf("%d %d",&i,&j);/* 读入边<Vi,Vj>的顶点对应序号*/
p=(EdgeNode *)malloc(sizeof(EdgeNode)); // 生成新边表结点p
p->adjvex=j; /* 邻接点序号为j */
p->next=G->adjlist[i].firstedge;/* 将结点p插入到顶点Vi的链表头部*/
G->adjlist[i].firstedge=p;
}
printf("\n图已成功创建!对应的邻接表如下：\n");
for(i=0;i<G->n;i++)
{
p=G->adjlist[i].firstedge;
printf("%c->",G->adjlist[i].vertex);
while(p!=NULL)
{
printf("[ %c ]",G->adjlist[p->adjvex].vertex);
p=p->next;
}
printf("\n");
}
printf("\n");
} /*CreateALGraph*/
int FirstAdjVertex(ALGraph *g,int v)//找图g中与顶点v相邻的第一个顶点
{
if(g->adjlist[v].firstedge!=NULL) return (g->adjlist[v].firstedge)->adjvex;
else return 0;
}
int NextAdjVertex(ALGraph *g ,int vi,int vj )//找图g中与vi相邻的，相对相邻顶点vj的下一个相邻顶点
{
EdgeNode *p;
p=g->adjlist[vi].firstedge;
while( p!=NULL && p->adjvex!=vj) p=p->next;
if(p!=NULL && p->next!=NULL) return p->next->adjvex;
else return 0;
}
void DFS(ALGraph *G,int v) /* 从第v个顶点出发深度优先遍历图G */
{
int w;
printf("%c ",G->adjlist[v].vertex);
visited[v]=True; /* 访问第v个顶点，并把访问标志置True */
for(w=FirstAdjVertex(G,v);w;w=NextAdjVertex(G,v,w))
if (!visited[w]) DFS(G,w); /* 对v尚未访问的邻接顶点w递归调用DFS */
}
void DFStraverse(ALGraph *G)
/*深度优先遍历以邻接表表示的图G，而以邻接矩阵表示时，算法完全相同*/
{ int i,v;
for(v=0;v<G->n;v++)
visited[v]=False;/*标志向量初始化*/
//for(i=0;i<G->n;i++)
if(!visited[0]) DFS(G,0);
}/*DFS*/
void main()
{
ALGraph G;
CreateALGraph(&G);
printf("该无向图的深度优先搜索序列为：");
DFStraverse(&G);
printf("\nSuccess!\n");
}
‘柒’ C语言 图 邻接矩阵 深度优先遍历 DFS搜索
DFS(g,j);
DFSL(ga,p->adjvex);
除了上面两句话，其他没什么问题，首先如果图不连通，当你用从某一点遍历的方法，本身就没办法遍历整个图
‘捌’ 求一个C语言编程，图的遍历，深度优先和广度优先搜索的程序。要浅显易懂的~~~~
给你一个作为参考吧
#include <iostream>
#define INFINITY 32767
#define MAX_VEX 20 //最大顶点个数
#define QUEUE_SIZE (MAX_VEX+1) //队列长度
using namespace std;
bool *visited; //访问标志数组
//图的邻接矩阵存储结构
typedef struct{
char *vexs; //顶点向量
int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
}Graph;
//队列类
class Queue{
public:
void InitQueue(){
base=(int *)malloc(QUEUE_SIZE*sizeof(int));
front=rear=0;
}
void EnQueue(int e){
base[rear]=e;
rear=(rear+1)%QUEUE_SIZE;
}
void DeQueue(int &e){
e=base[front];
front=(front+1)%QUEUE_SIZE;
}
public:
int *base;
int front;
int rear;
};
//图G中查找元素c的位置
int Locate(Graph G,char c){
for(int i=0;i<G.vexnum;i++)
if(G.vexs[i]==c) return i;
return -1;
}
//创建无向网
void CreateUDN(Graph &G){
int i,j,w,s1,s2;
char a,b,temp;
printf("输入顶点数和弧数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
temp=getchar(); //接收回车
G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
printf("输入%d个顶点.\n",G.vexnum);
for(i=0;i<G.vexnum;i++){ //初始化顶点
printf("输入顶点%d:",i);
scanf("%c",&G.vexs[i]);
temp=getchar(); //接收回车
}
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("输入%d条弧.\n",G.arcnum);
for(i=0;i<G.arcnum;i++){ //初始化弧
printf("输入弧%d:",i);
scanf("%c %c %d",&a,&b,&w); //输入一条边依附的顶点和权值
temp=getchar(); //接收回车
s1=Locate(G,a);
s2=Locate(G,b);
G.arcs[s1][s2]=G.arcs[s2][s1]=w;
}
}
//图G中顶点k的第一个邻接顶点
int FirstVex(Graph G,int k){
if(k>=0 && k<G.vexnum){ //k合理
for(int i=0;i<G.vexnum;i++)
if(G.arcs[k][i]!=INFINITY) return i;
}
return -1;
}
//图G中顶点i的第j个邻接顶点的下一个邻接顶点
int NextVex(Graph G,int i,int j){
if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ //i,j合理
for(int k=j+1;k<G.vexnum;k++)
if(G.arcs[i][k]!=INFINITY) return k;
}
return -1;
}
//深度优先遍历
void DFS(Graph G,int k){
int i;
if(k==-1){ //第一次执行DFS时,k为-1
for(i=0;i<G.vexnum;i++)
if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS
}
else{
visited[k]=true;
printf("%c ",G.vexs[k]); //访问第k个顶点
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS
}
}
//广度优先遍历
void BFS(Graph G){
int k;
Queue Q; //辅助队列Q
Q.InitQueue();
for(int i=0;i<G.vexnum;i++)
if(!visited[i]){ //i尚未访问
visited[i]=true;
printf("%c ",G.vexs[i]);
Q.EnQueue(i); //i入列
while(Q.front!=Q.rear){
Q.DeQueue(k); //队头元素出列并置为k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]){ //w为k的尚未访问的邻接顶点
visited[w]=true;
printf("%c ",G.vexs[w]);
Q.EnQueue(w);
}
}
}
}
//主函数
void main(){
int i;
Graph G;
CreateUDN(G);
visited=(bool *)malloc(G.vexnum*sizeof(bool));
printf("\n广度优先遍历: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
DFS(G,-1);
printf("\n深度优先遍历: ");
for(i=0;i<G.vexnum;i++)
visited[i]=false;
BFS(G);
printf("\n程序结束.\n");
}
‘玖’ （c语言）有关acm深度优先搜索的问题 help！
intmain()
{
intlike[5][5];
inti,j;
setstackopen;
bookdistypeclosed[maxsize],book,newbook;
intcount=0,sum=0;
// freopen("book.in","r",stdin);
// freopen("book.out","w",stdout);
for(i=0;i<5;i++)
for(j=0;j<5;j++)
scanf("%d",&like[i][j]);
for(i=0;i<5;i++)
book.a[i]=0;
book.k=0;
//*************
setnull(open);
push(open,book);
//open这个stack还没空的话
while(empty(open)!=1){
//取出stack最上面的那个book
book=pop(open);
//这2行意义不明
closed[count]=book;
count++;
//i是book的dfs深度
i=book.k;
//如果深度是5（即每个人都挑完了自己的书），并且每一本书都被选择了（我认为这个检查是多余的，只要检查深度是5即可），那么统计数+1
if((i==5)&&book.a[0]==1&&book.a[1]==1&&book.a[2]==1&&book.a[3]==1&&book.a[4]==1)sum++;
//对于每一本书
for(j=4;j>=0;j--){
//复制当前book到newbook
newbook=book;
//如果第i个人喜欢第j本书，并且第j本书没有被人拿走
if((like[i][j]==1)&&(newbook.a[j]==0)){
//在newbook中标记第j本书已经被读了
newbook.a[j]=1;
//newbook的搜索深度+1
newbook.k=i+1;
//把newbook放进stack等待dfs
push(open,newbook);
}
}
}
//*******
printf("%d",sum);
return0;
}
‘拾’ C语言编写深度优先搜索(DFS)是否需要回溯
我就是从pascal转到c多年的，这些算法和语言无关的，只是一种思想。都是怎样方便就怎样的，深搜我个人就喜欢直接写递归解决