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多年的，這些演算法和語言無關的，只是一種思想。都是怎樣方便就怎樣的，深搜我個人就喜歡直接寫遞歸解決