寫出圖的深度優先遍歷演算法

1. 用鄰接表表示圖進行深度優先遍歷時，通常採用（）來實現演算法

使用棧來實現演算法。

用鄰接表表示圖進行深度優先遍歷時，通常採用棧來實現演算法，廣度遍歷使用隊列。

擴展材料：

深度優先遍歷：類似與樹的前序遍歷。從圖中的某個頂點v出發，訪問此頂點，然後從v的未被訪問到的鄰接點進行遍歷，直到圖中所有和v有路徑相通的頂點都被訪問到

註：優先訪問外層節點，訪問到無新頂點時，會進行回退，訪問未被訪問過的分支頂點。

廣度優先遍歷：類似於樹的層序遍歷。從圖中的某個頂點w出發，讓頂點w入隊，然後頂點w再出隊，並讓所有和頂點w相連的頂點入隊，然後再出隊一個頂點t，並讓所有和t相連但未被訪問過的頂點入隊……由此循環，指定圖中所有元素都出隊。

參考資料來源：

知網論文-數據結構中圖的遍歷演算法研究

2. 求圖的深度優先遍歷程序 c語言版

鄰接表表示的圖：#include"stdio.h"
#include"stdlib.h"#define MaxVertexNum 50 //定義最大頂點數typedef struct node{ //邊表結點
int adjvex; //鄰接點域
struct node *next; //鏈域
}EdgeNode;
typedef struct vnode{ //頂點表結點
char vertex; //頂點域
EdgeNode *firstedge; //邊表頭指針
}VertexNode;
typedef VertexNode AdjList[MaxVertexNum]; //AdjList是鄰接表類型
typedef struct {
AdjList adjlist; //鄰接表
int n,e; //圖中當前頂點數和邊數
} ALGraph; //圖類型//=========建立圖的鄰接表=======
void CreatALGraph(ALGraph *G)
{
int i,j,k;
char a;
EdgeNode *s; //定義邊表結點
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //讀入頂點數和邊數
fflush(stdin); //清空內存緩沖
printf("Input Vertex string:");
for(i=0;i<G->n;i++) //建立邊表
{
scanf("%c",&a);
G->adjlist[i].vertex=a; //讀入頂點信息
G->adjlist[i].firstedge=NULL; //邊表置為空表
}
printf("Input edges,Creat Adjacency List\n");
for(k=0;k<G->e;k++) { //建立邊表
scanf("%d%d",&i,&j); //讀入邊（Vi，Vj）的頂點對序號
s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成邊表結點
s->adjvex=j; //鄰接點序號為j
s->next=G->adjlist[i].firstedge;
G->adjlist[i].firstedge=s; //將新結點*S插入頂點Vi的邊表頭部
s=(EdgeNode *)malloc(sizeof(EdgeNode));
s->adjvex=i; //鄰接點序號為i
s->next=G->adjlist[j].firstedge;
G->adjlist[j].firstedge=s; //將新結點*S插入頂點Vj的邊表頭部
}
}
//=========定義標志向量，為全局變數=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度優先遍歷的遞歸演算法======
void DFSM(ALGraph *G,int i)
{//以Vi為出發點對鄰接鏈表表示的圖G進行DFS搜索
EdgeNode *p;
printf("%c",G->adjlist[i].vertex); //訪問頂點Vi
visited[i]=TRUE; //標記Vi已訪問
p=G->adjlist[i].firstedge; //取Vi邊表的頭指針
while(p) { //依次搜索Vi的鄰接點Vj，這里j=p->adjvex
if(! visited[p->adjvex]) //若Vj尚未被訪問
DFSM(G,p->adjvex); //則以Vj為出發點向縱深搜索
p=p->next; //找Vi的下一個鄰接點
}
}
void DFS(ALGraph *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<G->n;i++)
if(!visited[i]) //Vi未訪問過
DFSM(G,i); //以Vi為源點開始DFS搜索
} //==========BFS：廣度優先遍歷=========
void BFS(ALGraph *G,int k)
{ //以Vk為源點對用鄰接鏈表表示的圖G進行廣度優先搜索
int i,f=0,r=0; EdgeNode *p;
int cq[MaxVertexNum]; //定義FIFO隊列
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<=G->n;i++)
cq[i]=-1; //初始化標志向量
printf("%c",G->adjlist[k].vertex); //訪問源點Vk
visited[k]=TRUE;
cq[r]=k; //Vk已訪問，將其入隊。注意，實際上是將其序號入隊
while(cq[f]!=-1) { // 隊列非空則執行
i=cq[f]; f=f+1; //Vi出隊
p=G->adjlist[i].firstedge; //取Vi的邊表頭指針
while(p) { //依次搜索Vi的鄰接點Vj（令p->adjvex=j）
if(!visited[p->adjvex]) { //若Vj未訪問過
printf("%c",G->adjlist[p->adjvex].vertex); //訪問Vj
visited[p->adjvex]=TRUE;
r=r+1; cq[r]=p->adjvex; //訪問過的Vj入隊
}
p=p->next; //找Vi的下一個鄰接點
}
}//endwhile
}
//==========主函數===========
void main()
{
//int i;
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph));
CreatALGraph(G);
printf("Print Graph DFS: ");
DFS(G);
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3);
printf("\n");
}鄰接矩陣表示的圖：
#include"stdio.h"
#include"stdlib.h"
#define MaxVertexNum 100 //定義最大頂點數
typedef struct{
char vexs[MaxVertexNum]; //頂點表
int edges[MaxVertexNum][MaxVertexNum]; //鄰接矩陣，可看作邊表
int n,e; //圖中的頂點數n和邊數e
}MGraph; //用鄰接矩陣表示的圖的類型
//=========建立鄰接矩陣=======
void CreatMGraph(MGraph *G)
{
int i,j,k;
char a;
printf("Input VertexNum(n) and EdgesNum(e): ");
scanf("%d,%d",&G->n,&G->e); //輸入頂點數和邊數
scanf("%c",&a);
printf("Input Vertex string:");
for(i=0;i<G->n;i++)
{
scanf("%c",&a);
G->vexs[i]=a; //讀入頂點信息，建立頂點表
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=0; //初始化鄰接矩陣
printf("Input edges,Creat Adjacency Matrix\n");
for(k=0;k<G->e;k++) { //讀入e條邊，建立鄰接矩陣
scanf("%d%d",&i,&j); //輸入邊（Vi，Vj）的頂點序號
G->edges[i][j]=1;
G->edges[j][i]=1; //若為無向圖，矩陣為對稱矩陣；若建立有向圖，去掉該條語句
}
}
//=========定義標志向量，為全局變數=======
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MaxVertexNum];
//========DFS：深度優先遍歷的遞歸演算法======
void DFSM(MGraph *G,int i)
{ //以Vi為出發點對鄰接矩陣表示的圖G進行DFS搜索，鄰接矩陣是0，1矩陣
int j;
printf("%c",G->vexs[i]); //訪問頂點Vi
visited[i]=TRUE; //置已訪問標志
for(j=0;j<G->n;j++) //依次搜索Vi的鄰接點
if(G->edges[i][j]==1 && ! visited[j])
DFSM(G,j); //（Vi，Vj）∈E，且Vj未訪問過，故Vj為新出發點
}
void DFS(MGraph *G)
{
int i;
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<G->n;i++)
if(!visited[i]) //Vi未訪問過
DFSM(G,i); //以Vi為源點開始DFS搜索
}
//===========BFS：廣度優先遍歷=======
void BFS(MGraph *G,int k)
{ //以Vk為源點對用鄰接矩陣表示的圖G進行廣度優先搜索
int i,j,f=0,r=0;
int cq[MaxVertexNum]; //定義隊列
for(i=0;i<G->n;i++)
visited[i]=FALSE; //標志向量初始化
for(i=0;i<G->n;i++)
cq[i]=-1; //隊列初始化
printf("%c",G->vexs[k]); //訪問源點Vk
visited[k]=TRUE;
cq[r]=k; //Vk已訪問，將其入隊。注意，實際上是將其序號入隊
while(cq[f]!=-1) { //隊非空則執行
i=cq[f]; f=f+1; //Vf出隊
for(j=0;j<G->n;j++) //依次Vi的鄰接點Vj
if(!visited[j] && G->edges[i][j]==1) { //Vj未訪問
printf("%c",G->vexs[j]); //訪問Vj
visited[j]=TRUE;
r=r+1; cq[r]=j; //訪問過Vj入隊
}
}
}
//==========main=====
void main()
{
//int i;
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)); //為圖G申請內存空間
CreatMGraph(G); //建立鄰接矩陣
printf("Print Graph DFS: ");
DFS(G); //深度優先遍歷
printf("\n");
printf("Print Graph BFS: ");
BFS(G,3); //以序號為3的頂點開始廣度優先遍歷
printf("\n");
}

3. 已知一個有向圖如圖，請分別寫出從頂點a出發進行深度優先遍歷和廣度優先遍歷所得到的頂點序列及生成樹。

一、深度生成樹：abdcefigh，如下圖所示：

相關特點：

（1）生成樹協議提供一種控制環路的方法。採用這種方法，在連接發生問題的時候，你控制的乙太網能夠繞過出現故障的連接。

（2）生成樹中的根橋是一個邏輯的中心，並且監視整個網路的通信。最好不要依靠設備的自動選擇去挑選哪一個網橋會成為根橋。

（3）生成樹協議重新計算是繁冗的。恰當地設置主機連接埠(這樣就不會引起重新計算)，推薦使用快速生成樹協議。

（4）生成樹協議可以有效的抑制廣播風暴。開啟生成樹協議後抑制廣播風暴，網路將會更加穩定，可靠性、安全性會大大增強。

4. 無向有權的圖的深度、廣度優先遍歷怎麼做的啊，他的遍歷序列怎麼求呢

總結深度優先與廣度優先的區別
1、區別

1） 二叉樹的深度優先遍歷的非遞歸的通用做法是採用棧，廣度優先遍歷的非遞歸的通用做法是採用隊列。

2） 深度優先遍歷：對每一個可能的分支路徑深入到不能再深入為止，而且每個結點只能訪問一次。要特別注意的是，二叉樹的深度優先遍歷比較特殊，可以細分為先序遍歷、中序遍歷、後序遍歷。具體說明如下：

先序遍歷：對任一子樹，先訪問根，然後遍歷其左子樹，最後遍歷其右子樹。
中序遍歷：對任一子樹，先遍歷其左子樹，然後訪問根，最後遍歷其右子樹。
後序遍歷：對任一子樹，先遍歷其左子樹，然後遍歷其右子樹，最後訪問根。
廣度優先遍歷：又叫層次遍歷，從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。

3）深度優先搜素演算法：不全部保留結點，佔用空間少；有回溯操作(即有入棧、出棧操作)，運行速度慢。

廣度優先搜索演算法：保留全部結點，佔用空間大； 無回溯操作(即無入棧、出棧操作)，運行速度快。

5. 簡述深度優先搜索遍歷的方法。

簡述深度優先搜索遍歷的方法？深度優先搜索演算法(Depth-First-Search, DFS)，最初是一種用於遍歷或搜索樹和圖的演算法，在LeetCode中很常見，雖然感覺不難，但是理解起來還是有點難度的。

簡要概括，深度優先的主要思想就是「不撞南牆不回頭」，「一條路走到黑」，如果遇到「牆」或者「無路可走」時再去走下一條路。

思路
假如對樹進行遍歷，沿著樹的深度遍歷樹的節點，盡可能深的搜索樹的分支，當達到邊際時回溯上一個節點再進行搜索。如下圖的一個二叉樹。


首先給出這個二叉樹的深度優先遍歷的結果(假定先走左子樹)：1->2->4->5->3->6->7

那是怎樣得到這樣的結果呢？
根據深度優先遍歷的概念：沿著這樹的某一分支向下遍歷到不能再深入為止，之後進行回溯再選定新的分支。

定義節點

class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
遞歸的方式

分別對左右子樹進行遞歸，一直到底才進行回溯。如果不了解遞歸可以參考我的博客你真的懂遞歸嗎？。

class Solution{
public void (TreeNode root){
if(root == null){
return;
}
System.out.print(root.val +"->");
(root.left);
(root.right);
}
}
迭代的方式

上面實現了遞歸方式的深度優先遍歷，也可以利用棧把遞歸轉換為迭代的方式。

但是為了保證出棧的順序，需要先壓入右節點，再壓左節點。

class Solution{
public void (TreeNode root){
if(root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(!stack.isEmpty()){
TreeNode node = stack.pop();
System.out.print(node.val + "->");
if(node.right != null){
stack.push(node.right);
}
if(node.left != null){
stack.push(node.left);
}
}
}
}
接著再列舉個利用深度優先遍歷的方式的題目

掃雷
給定一個表示游戲板的二維字元矩陣，'M'表示一個未挖出的地雷，'E'表示一個未挖出的空方塊，'B' 代表沒有相鄰（上，下，左，右，和所有4個對角線）地雷的已挖出的空白方塊，數字（'1' 到 '8'）表示有多少地雷與這塊已挖出的方塊相鄰，'X' 則表示一個已挖出的地雷。

根據以下規則，返回相應位置被點擊後對應的面板：

如果一個地雷（'M'）被挖出，游戲就結束了- 把它改為'X'。
如果一個沒有相鄰地雷的空方塊（'E'）被挖出，修改它為（'B'），並且所有和其相鄰的方塊都應該被遞歸地揭露。
如果一個至少與一個地雷相鄰的空方塊（'E'）被挖出，修改它為數字（'1'到'8'），表示相鄰地雷的數量。
如果在此次點擊中，若無更多方塊可被揭露，則返回面板。
示例

輸入:

[['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'M', 'E', 'E'],
['E', 'E', 'E', 'E', 'E'],
['E', 'E', 'E', 'E', 'E']]

Click : [3,0]

輸出:

[['B', '1', 'E', '1', 'B'],
['B', '1', 'M', '1', 'B'],
['B', '1', '1', '1', 'B'],
['B', 'B', 'B', 'B', 'B']]
思路：根據給定的規則，當給定一個Click坐標，當不為雷的時候以此坐標為基點向四周8個方向進行深度遍歷，把空格E填充為B，並且把與地雷M相連的空方塊標記相鄰地雷的數量。

注意 ：



在這個題中可以沿著8個方向遞歸遍歷，所有要注意程序中，採用了兩個for循環可以實現向8個方向遞歸。

6. 圖遍歷的演算法

圖的遍歷方法目前有深度優先搜索法和廣度（寬度）優先搜索法兩種演算法。 深度優先搜索法是樹的先根遍歷的推廣，它的基本思想是：從圖G的某個頂點v0出發，訪問v0，然後選擇一個與v0相鄰且沒被訪問過的頂點vi訪問，再從vi出發選擇一個與vi相鄰且未被訪問的頂點vj進行訪問，依次繼續。如果當前被訪問過的頂點的所有鄰接頂點都已被訪問，則退回到已被訪問的頂點序列中最後一個擁有未被訪問的相鄰頂點的頂點w，從w出發按同樣的方法向前遍歷，直到圖中所有頂點都被訪問。其遞歸演算法如下：
Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組
Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數
void DFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //訪問標志數組初始化
for(v=0; v<G.vexnum; ++v)
if(!visited[v])
DFS(G, v); //對尚未訪問的頂點調用DFS
}
void DFS(Graph G, int v){ //從第v個頂點出發遞歸地深度優先遍歷圖G
visited[v]=TRUE; VisitFunc(v); //訪問第v個頂點
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一個鄰接頂點，若頂點在G中沒有鄰接頂點，則返回空（0）。
//若w是v的鄰接頂點，NextAdjVex返回v的（相對於w的）下一個鄰接頂點。
//若w是v的最後一個鄰接點，則返回空（0）。
if(!visited[w])
DFS(G, w); //對v的尚未訪問的鄰接頂點w調用DFS
} 圖的廣度優先搜索是樹的按層次遍歷的推廣，它的基本思想是：首先訪問初始點vi，並將其標記為已訪問過，接著訪問vi的所有未被訪問過的鄰接點vi1,vi2,…, vi t，並均標記已訪問過，然後再按照vi1,vi2,…, vi t的次序，訪問每一個頂點的所有未被訪問過的鄰接點，並均標記為已訪問過，依次類推，直到圖中所有和初始點vi有路徑相通的頂點都被訪問過為止。其非遞歸演算法如下：
Boolean visited[MAX_VERTEX_NUM]; //訪問標志數組
Status (*VisitFunc)(int v); //VisitFunc是訪問函數，對圖的每個頂點調用該函數
void BFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q); //置空輔助隊列Q
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
EnQueue(Q, v); //v入隊列
while(!QueueEmpty(Q)){
DeQueue(Q, u); //隊頭元素出隊並置為u
for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
if(!Visited[w]){ //w為u的尚未訪問的鄰接頂點
Visited[w]=TRUE; VisitFunc(w);
EnQueue(Q, w);
}
}
}
}