深度優先遍歷演算法

① 圖的深度優先遍歷演算法屬於_ A.窮舉法 B.回溯法 C.遞歸 D.分治法

圖的深度優先遍歷演算法屬於_ A.窮舉法 B.回溯法 C.遞歸 D.分治法

B 回溯

② 下面是圖的深度優先遍歷演算法,請完成。

不明白，遞歸函數，自己寫吧

③ 深度優先遍歷與廣度優先遍歷的區別

一、指代不同

1、深度優先遍歷：是對每一個可能的分支路徑深入到不能再深入為止，而且每個節點只能訪問一次。

2、廣度優先遍歷：系統地展開並檢查圖中的所有節點，以找尋結果。

二、特點不同

1、深度優先遍歷：所有的搜索演算法從其最終的演算法實現上來看，都可以劃分成兩個部分──控制結構和產生系統。正如前面所說的，搜索演算法簡而言之就是窮舉所有可能情況並找到合適的答案，所以最基本的問題就是羅列出所有可能的情況，這其實就是一種產生式系統。

2、廣度優先遍歷：並不考慮結果的可能位置，徹底地搜索整張圖，直到找到結果為止。

三、演算法不同

1、深度優先遍歷：把根節點壓入棧中。每次從棧中彈出一個元素，搜索所有在它下一級的元素，把這些元素壓入棧中。並把這個元素記為它下一級元素的前驅。找到所要找的元素時結束程序。如果遍歷整個樹還沒有找到，結束程序。

2、廣度優先遍歷：把根節點放到隊列的末尾。每次從隊列的頭部取出一個元素，查看這個元素所有的下一級元素，把它們放到隊列的末尾。並把這個元素記為它下一級元素的前驅。找到所要找的元素時結束程序。如果遍歷整個樹還沒有找到，結束程序。

④ 深度優先和廣度優先遍歷演算法類似於二叉樹的什麼遍歷

類似於二叉樹的先序遍歷

⑤ 深度優先演算法的圖的遍歷

方法步驟
假設初始狀態是圖中所有頂點都未被訪問，則深度優先搜索方法的步驟是：
1）選取圖中某一頂點Vi為出發點，訪問並標記該頂點；
2）以Vi為當前頂點，依次搜索Vi的每個鄰接點Vj，若Vj未被訪問過，則訪問和標記鄰接點Vj，若Vj已被訪問過，則搜索Vi的下一個鄰接點；
3）以Vj為當前頂點，重復步驟2），直到圖中和Vi有路徑相通的頂點都被訪問為止；
4）若圖中尚有頂點未被訪問過（非連通的情況下），則可任取圖中的一個未被訪問的頂點作為出發點，重復上述過程，直至圖中所有頂點都被訪問。

⑥ 深度優先遍歷的演算法幫我解釋一下

建議看"數據結構",嚴蔚敏,清華大學出版社中的相關內容,其實很簡單

⑦ 深度優先遍歷演算法的問題

你好，c的話是a e b... ,深度優先的話，e後面還可以訪問d，d可以訪問f，f可以訪問c。
圖的深度優先遍歷類似於樹的前序遍歷。採用的搜索方法的特點是盡可能先對縱深方向進行搜索。這種搜索方法稱為深度優先搜索(Depth-First Search)。相應地，用此方法遍歷圖就很自然地稱之為圖的深度優先遍歷。

⑧ 連通圖的深度優先遍歷演算法

這個第一個點是隨機的。只是看你怎麼儲存的。如果你把v的鄰接頂點用數組保存，那麼它在數組的最前邊。用指針的話，就指向下一個緊接的位置。

⑨ 求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");
}

⑩ 採用鄰接表存儲的圖的深度優先遍歷演算法類似於二叉樹的先序遍歷，為什麼是先序呢

這是因為圖的深度優先遍歷演算法先訪問所在結點，再訪問它的鄰接點。與二叉樹的先序遍歷先訪問子樹的根結點，再訪問它的孩子結點（鄰接點）類似。圖的廣度優先遍歷演算法類似於二叉樹的按層次遍歷。

先序遍歷也叫做先根遍歷、前序遍歷，可記做根左右（二叉樹父結點向下先左後右）。

首先訪問根結點然後遍歷左子樹，最後遍歷右子樹。在遍歷左、右子樹時，仍然先訪問根結點，然後遍歷左子樹，最後遍歷右子樹，如果二叉樹為空則返回。

例如，下圖所示二叉樹的遍歷結果是：ABDECF。

(10)深度優先遍歷演算法擴展閱讀：

遍歷種類：

一、NLR：前序遍歷(Preorder Traversal 亦稱（先序遍歷）），訪問根結點的操作發生在遍歷其左右子樹之前。

二、LNR：中序遍歷(Inorder Traversal)，訪問根結點的操作發生在遍歷其左右子樹之中（間）。

三、LRN：後序遍歷(Postorder Traversal)，訪問根結點的操作發生在遍歷其左右子樹之後。

注意：

由於被訪問的結點必是某子樹的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解釋為根、根的左子樹和根的右子樹。NLR、LNR和LRN分別又稱為 先根遍歷、中根遍歷和後根遍歷。