国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<span id="hxvu0"><ul id="hxvu0"><font id="hxvu0"></font></ul></span>

蠻力算法之深度優(yōu)先遍歷和廣度優(yōu)先遍歷——圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷，附帶案例：迷宮問題及矩陣中傳染性傳播問題

2年前作者：美人魚戰(zhàn)士與企鵝男孩合為一體分類：Toy博客閱讀(19)違法舉報

這篇具有很好參考價值的文章主要介紹了蠻力算法之深度優(yōu)先遍歷和廣度優(yōu)先遍歷——圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷，附帶案例：迷宮問題及矩陣中傳染性傳播問題。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

算法：圖的深度優(yōu)先搜索和廣度優(yōu)先搜索

這兩種搜索方法本質(zhì)上都是基于蠻力法思路

這兩種搜索方法對有向圖和無向圖都適用

1 圖的兩種定義方式

1.1 鄰接矩陣

constexpr auto MAXV = 1000; //定義最大頂點個數(shù)

//頂點信息
typedef struct
{
	int no;
	char data[MAXV];
}VertexType;

//矩陣信息
typedef struct
{
	int edges[MAXV][MAXV];
	int n, e;
	VertexType vexs[MAXV];
}MGraph;

鄰接矩陣示意圖：

蠻力算法之深度優(yōu)先遍歷和廣度優(yōu)先遍歷——圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷，附帶案例：迷宮問題及矩陣中傳染性傳播問題,深度優(yōu)先,算法,廣度優(yōu)先,c++,visualstudio,數(shù)據(jù)結(jié)構(gòu),圖搜索

1.2 鄰接表

注意：邊結(jié)點代表的是圖中的邊，而并非圖中的結(jié)點；頭結(jié)點才表示圖中的結(jié)點；頭結(jié)點身后所連接的為邊結(jié)點

//邊結(jié)點 
typedef struct ANode
{
	int adjvex;			//這條邊的終點
	int weight;			//這條邊的權(quán)重
	struct ANode* nextarc;  //指向下一條與該結(jié)點相鄰的邊
} ArcNode;


//頭結(jié)點
typedef struct VNode
{
	string date;		//頂點的其他信息
	ArcNode* firstarc;	//指向第一條邊
};


//鄰接表
typedef struct
{
	VNode adjList[MAXV];  //頭結(jié)點組成的數(shù)組
	int n, e;            //圖中的頂點數(shù)n和邊數(shù)e
}ALGraph;

鄰接表示意圖：（一般默認為出邊表）

蠻力算法之深度優(yōu)先遍歷和廣度優(yōu)先遍歷——圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷，附帶案例：迷宮問題及矩陣中傳染性傳播問題,深度優(yōu)先,算法,廣度優(yōu)先,c++,visualstudio,數(shù)據(jù)結(jié)構(gòu),圖搜索

2 圖的深度優(yōu)先遍歷

關(guān)鍵：

用**visited[]**數(shù)組記錄是否已訪問
這是一個遞歸的過程

鄰接矩陣的：

void DFS(MGraph g,int v)
{	int w;
	cout<<v<<" ";						//輸出被訪問頂點的編號
	visited[v]=1;						//置已訪問標記
	for (w=0;w<g.n;w++)					//找頂點v的所有相鄰點
		if (g.edges[v][w]!=0 && g.edges[v][w]!=INF && visited[w]==0)
			DFS(g,w);					//找頂點v的未訪問過的相鄰點w
}

鄰接表的：

void DFS(ALGraph *G,int v)
{	ArcNode *p;
	cout<<v<<" ";					//輸出被訪問頂點的編號
	visited[v]=1;						//置已訪問標記
	p=G->adjlist[v].firstarc;			//p指向頂點v的第一個鄰接點
	while (p!=NULL)
	{	if (visited[p->adjvex]==0)		//若p->adjvex頂點未訪問,遞歸訪問它
			DFS(G,p->adjvex);
		p=p->nextarc;					//p指向頂點v的下一個鄰接點
	}
}

3 圖的廣度優(yōu)先遍歷

關(guān)鍵：

使用數(shù)據(jù)結(jié)構(gòu) → 隊列來記錄未訪問的鄰接點
用**visited[]**數(shù)組記錄哪些點已經(jīng)訪問了，哪些還沒有
采用循環(huán)，循環(huán)終止條件為隊列空了

鄰接矩陣的：

void BFS(MGraph g,int v)					//鄰接矩陣的DFS算法
{
	queue<int> qu;							//定義一個隊列qu
	int visited[MAXV];						//定義存放結(jié)點的訪問標志的數(shù)組
	int w,i;
	memset(visited,0,sizeof(visited));		//訪問標志數(shù)組初始化

	cout<<v<<" ";						//輸出被訪問頂點的編號
	visited[v]=1;							//置已訪問標記
	qu.push(v);								//v進隊
	while (!qu.empty())						//隊列不空時循環(huán)
	{
		w=qu.front(); qu.pop();				//出隊頂點w
		for (i=0;i<g.n;i++)					//找與頂點w相鄰的頂點
			if (g.edges[w][i]!=0 && g.edges[w][i]!=INF && visited[i]==0)
			{	//若當前鄰接頂點i未被訪問
				cout<<i<<" ";			//訪問相鄰頂點
				visited[i]=1;				//置該頂點已被訪問的標志
				qu.push(i);					//該頂點進隊
			}
	}
	printf("\n");
}

鄰接表的：

void BFS(ALGraph *G,int v)					//鄰接表的DFS算法
{
	ArcNode *p;
	queue<int> qu;							//定義一個隊列qu
	int visited[MAXV];						//定義存放頂點的訪問標志的數(shù)組
	int w;
	memset(visited,0,sizeof(visited));		//訪問標志數(shù)組初始化
	cout<<v<<" ";						//輸出被訪問頂點的編號
	visited[v]=1; 							//置已訪問標記
	qu.push(v);								//v進隊
	while (!qu.empty())						//隊列不空時循環(huán)
	{
		w=qu.front(); qu.pop();				//出隊頂點w
		p=G->adjlist[w].firstarc;			//找頂點w的第一個鄰接點
		while (p!=NULL) 
		{	if (visited[p->adjvex]==0)		//若當前鄰接頂點未被訪問
			{	cout<<i<<" ";	//訪問相鄰頂點
				visited[p->adjvex]=1;		//置該頂點已被訪問的標志
				qu.push(p->adjvex);			//該頂點進隊
			}
			p=p->nextarc;					//找頂點w的下一個鄰接點
		}
	}
	printf("\n");
}

兩種遍歷方式都重點掌握鄰接表的。

案例

案例1：迷宮

【問題描述】有如下8*8的迷宮圖：

OXXXXXXX
OOOOOXXX
XOXXOOOX
XOXXOXXO
XOXXXXXX
XOXXOOOX
XOOOOXOO
XXXXXXXO

其中，O表示通路方塊，X表示障礙方塊。假設(shè)入口是位置（0，0），出口為右下角方塊位置（7，7）。設(shè)計一個程序采用遞歸方法求指定入口到出口的一條迷宮路徑。

深度優(yōu)先的解法：

關(guān)鍵：

用數(shù)組記錄垂直與水平偏移量，才能運用for循環(huán)遍歷來嘗試各種可能
采用遞歸，遞歸的終止條件為達到了終點
如何記錄過程（路徑）？在深度遍歷的過程中，將可行的點作上了記號，不可行的點保留了原貌；最后輸出矩陣即可

#include <stdio.h>
#define MAxN 10						//最大迷宮大小
//問題表示
int n=8;							//迷宮大小
char Maze[MAxN][MAxN]=
{	{'O','X','X','X','X','X','X','X'},
	{'O','O','O','O','O','X','X','X'},
	{'X','O','X','X','O','O','O','X'},
	{'X','O','X','X','O','X','X','O'},
	{'X','O','X','X','X','X','X','X'},
	{'X','O','X','X','O','O','O','X'},
	{'X','O','O','O','O','X','O','O'},
	{'X','X','X','X','X','X','X','O'}
};
int H[4] = {0, 1, 0, -1};			//水平偏移量,下標對應(yīng)方位號0～3
int V[4] = {-1, 0, 1, 0};			//垂直偏移量

void disppath()						//輸出一條迷宮路徑
{
	for (int i=0; i<n;i++)
	{
		printf("    ");
		for(int j=0; j<n;j++)
			printf("%c",Maze[i][j]);
		printf("\n");
	}
}
void DFS(int x,int y)			 //求從(x,y)出發(fā)的一條迷宮路徑
{
	if (x==n-1 && y==n-1) //找到一條路徑,輸出
	{
		Maze[n-1][n-1]=' ';
		disppath();
		return;
	}
	else
	{	for (int k=0;k<4;k++)				 //試探每一個方位
			if(x>=0 && y>=0 && x<n && y<n && Maze[x][y]=='O')
			{								//若(x,y)方塊的可走的
				Maze[x][y]=' ';				//將該方塊設(shè)置為空字符
				DFS(x+V[k],y+H[k]);			//查找(x,y)周圍的每一個相鄰方塊
				Maze[x][y]='O';				//若從該相鄰方塊出發(fā)沒有找到路徑,恢復(fù)(x,y)
			}
	}
}
void main()
{
	int x=0,y=0;		//指定入口,出口默認為(n-1,n-1)
	printf("一條迷宮路徑:\n");
	DFS(x,y);			//求(0,0)->(7,7)的一條迷宮路徑
}

廣度優(yōu)先的解法：

關(guān)鍵：

用數(shù)組記錄垂直與水平偏移量，才能運用for循環(huán)遍歷來嘗試各種可能
如何記錄路徑：采用隊列，對于可行的方塊，我們將其放入隊列尾部（方塊是用結(jié)構(gòu)體定義的）
不會記錄到多條路徑嗎？是的，隊列中除了結(jié)果路徑的點之外，還有廣度遍歷過程中其他路徑上的點，所以，我們要用結(jié)構(gòu)體來定義點，并賦予一個屬性pre，用來記錄這個點的前驅(qū)在隊列中的下標（用數(shù)組加上隊頭隊尾組成的隊列支持隨機訪問）
在將方塊添加到隊列之前，要將其修改為某個特定的值防止其被再次訪問到。例如A之后的B可行，接下來我們要以B為對象，判斷它周圍的方塊是否可行，A也是其周圍方塊之一，但是不用再訪問A了，因為之前已經(jīng)訪問過了

#include <stdio.h>
#define MAXQ 100					//隊列大小
#define MAxN 10						//最大迷宮大小
//問題表示
int n=8;							//迷宮大小
char Maze[MAxN][MAxN]=
{	{'O','X','X','X','X','X','X','X'},
	{'O','O','O','O','O','X','X','X'},
	{'X','O','X','X','O','O','O','X'},
	{'X','O','X','X','O','X','X','O'},
	{'X','O','X','X','X','X','X','X'},
	{'X','O','X','X','O','O','O','X'},
	{'X','O','O','O','O','X','O','O'},
	{'X','X','X','X','X','X','X','O'}
};
int H[4] = {0, 1, 0, -1};			//水平偏移量,下標對應(yīng)方位號0～3
int V[4] = {-1, 0, 1, 0};			//垂直偏移量
struct Position						//隊列元素類型
{
	int x,y;						//當前方塊位置
	int pre;						//前驅(qū)方塊的下標
};
Position qu[MAXQ];					//定義一個隊列qu
int front=-1,rear=-1;				//定義隊頭和隊尾

void disppath(int front)			//輸出一條迷宮路徑
{
	int i,j;
	for (i=0; i<n;i++)				//將所有'*'改為'O'
		for (j=0;j<n;j++)
			if (Maze[i][j]=='*')
				Maze[i][j]='O';
	int k=front;
	while (k!=-1)					//即路徑上的方塊改為' '
	{
		Maze[qu[k].x][qu[k].y]=' ';
		k=qu[k].pre;
	}
	for (i=0; i<n;i++)				//輸出迷宮路徑
	{	printf("    ");
		for(int j=0; j<n;j++)
			printf("%c",Maze[i][j]);
		printf("\n");
	}
}

void BFS(int x,int y)			 //求從(x,y)出發(fā)的一條迷宮路徑
{
	Position p,p1,p2;
	p.x=x; p.y=y; p.pre=-1;			//建立入口結(jié)點
	Maze[p.x][p.y]='*';				//改為'*'避免重復(fù)查找
	rear++; qu[rear]=p;				//入口方塊進隊
	while (front!=rear)				//隊不空循環(huán)
	{
		front++; p1=qu[front];		//出隊方塊p1;
		if (p1.x==n-1 && p1.y==n-1)	//找到出口
		{
			disppath(front);		//輸出路徑
			return;
		}
		for (int k=0;k<4;k++)		//試探p1的每個相鄰方位
		{
			p2.x=p1.x+V[k];			//找到p1的相鄰方塊p2
			p2.y=p1.y+H[k];
			if (p2.x>=0 && p2.y>=0 && p2.x<n && p2.y<n && Maze[p2.x][p2.y]=='O')
			{	//方塊p2有效并且可走
				Maze[p2.x][p2.y]='*';	//改為'*'避免重復(fù)查找
				p2.pre=front;
				rear++;	qu[rear]=p2;	//方塊p2進隊
			}
		}
	}
}
void main()
{
	int x=0,y=0;		//指定入口,出口默認為(n-1,n-1)
	printf("一條迷宮路徑:\n");
	BFS(x,y);			//求(0,0)->(7,7)的一條迷宮路徑
}

案例2：傳染

這個案例可以更好的理解廣度優(yōu)先遍歷

小藍有一個01矩陣。他打算將第一行第一列的 0 變?yōu)?2 。變化過程有傳染性，每次 2 的上下左右四個相鄰的位置中的 0 都會變成 2 。直到最后每個 2 的周圍都是 1 或 2 結(jié)束。
請問，最終矩陣中有多少個 2 ？
以下是小藍的矩陣，共 30 行 40 列。

0000100010000001101010101001001100000011
0101111001111101110111100000101010011111
1000010000011101010110000000001011010100
0110101010110000000101100100000101001001
0000011010100000111111001101100010101001
0110000110000000110100000000010010100011
0100110010000110000000100010000101110000
0010011010100110001111001101100110100010
1111000111101000001110010001001011101101
0011110100011000000001101001101110100001
0000000101011000010011111001010011011100
0000100000011001000100101000111011101100
0010110000001000001010100011000010100011
0110110000100011011010011010001101011011
0000100100000001010000101100000000000010
0011001000001000000010011001100101000110
1110101000011000000100011001001100111010
0000100100111000001101001000001010010001
0100010010000110100001100000110111110101
1000001001100010011001111101011001110001
0000000010100101000000111100110010101101
0010110101001100000100000010000010110011
0000011101001001000111011000100111010100
0010001100100000011000101011000000010101
1001111010010110011010101110000000101110
0110011101000010100001000101001001100010
1101000000010010011001000100110010000101
1001100010100010000100000101111111111100
1001011010101100001000000011000110110000
0011000100011000010111101000101110110001

思路：廣度優(yōu)先遍歷，當隊列為空時為循環(huán)終止條件，計算矩陣中2的個數(shù)

#include<iostream>
#define MAXQ 100					
#define MAxN 100						
using namespace std;

int Maze[MAxN][MAxN] =
{ 
  {0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1,1,0,1,0,1,0,1,0,1,0,0,1,0,0,1,1,0,0,0,0,0,0,1,1},
  {0,1,0,1,1,1,1,0,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,0,0,0,1,0,1,0,1,0,0,1,1,1,1,1},
  {0,1,0,1,1,1,1,0,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,0,0,0,1,0,1,0,1,0,0,1,1,1,1,1},
  {1,0,0,0,0,1,0,0,0,0,0,1,1,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,1,0,0},
  {0,1,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,0,1,1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,1},
  {0,0,0,0,0,1,1,0,1,0,1,0,0,0,0,0,1,1,1,1,1,1,0,0,1,1,0,1,1,0,0,0,1,0,1,0,1,0,0,1},
  {0,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,1},
  {0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,1,1,1,0,0,0,0},
  {0,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,0,0,1,1,1,1,0,0,1,1,0,1,1,0,0,1,1,0,1,0,0,0,1,0},
  {1,1,1,1,0,0,0,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,0,1,0,0,0,1,0,0,1,0,1,1,1,0,1,1,0,1},
  {0,0,1,1,1,1,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,1,1,0,1,1,1,0,1,0,0,0,0,1},
  {0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,0,0,1,0,0,1,1,1,1,1,0,0,1,0,1,0,0,1,1,0,1,1,1,0,0},
  {0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,1,1,0,1,1,1,0,1,1,0,0},
  {0,0,1,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,1,1},
  {0,1,1,0,1,1,0,0,0,0,1,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,1,0,0,0,1,1,0,1,0,1,1,0,1,1},
  {0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0},
  {0,0,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,1,0,0,1,1,0,0,1,0,1,0,0,0,1,1,0},
  {1,1,1,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,1,0,0,1,1,1,0,1,0},
  {0,0,0,0,1,0,0,1,0,0,1,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,1},
  {0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,0,0,0,0,1,1,0,0,0,0,0,1,1,0,1,1,1,1,1,0,1,0,1},
  {1,0,0,0,0,0,1,0,0,1,1,0,0,0,1,0,0,1,1,0,0,1,1,1,1,1,0,1,0,1,1,0,0,1,1,1,0,0,0,1},
  {0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,1,0,1,1,0,1},
  {0,0,1,0,1,1,0,1,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,1,0,0,1,1},
  {0,0,0,0,0,1,1,1,0,1,0,0,1,0,0,1,0,0,0,1,1,1,0,1,1,0,0,0,1,0,0,1,1,1,0,1,0,1,0,0},
  {0,0,1,0,0,0,1,1,0,0,1,0,0,0,0,0,0,1,1,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,0,1,0,1},
  {1,0,0,1,1,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,1,0,1,1,1,0,0,0,0,0,0,0,1,0,1,1,1,0},
  {0,1,1,0,0,1,1,1,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,1,0,1,0,0,1,0,0,1,1,0,0,0,1,0},
  {1,1,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,0,1,0,0,1,1,0,0,1,0,0,0,0,1,0,1},
  {1,0,0,1,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,0},
  {1,0,0,1,0,1,1,0,1,0,1,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,1,1,0,0,0,0},
  {0,0,1,1,0,0,0,1,0,0,0,1,1,0,0,0,0,1,0,1,1,1,1,0,1,0,0,0,1,0,1,1,1,0,1,1,0,0,0,1}
};


int H[4] = { 0, 1, 0, -1 };			//水平偏移量,下標對應(yīng)方位號0～3
int V[4] = { -1, 0, 1, 0 };			//垂直偏移量

struct Position						//隊列元素類型
{
	int x, y;						//當前方塊位置
};

Position qu[MAXQ];					//定義一個隊列qu
int front = -1, rear = -1;			//定義隊頭和隊尾


//輸出迷宮并輸出迷宮中的2的個數(shù)
void print_2()
{
	int count = 0;
	for (int i = 0; i < 30; i++)
	{
		for (int j = 0; j < 40; j++)
		{
			cout << Maze[i][j];
			if (Maze[i][j] == 2)
			{
				count++;
			}
		}
		cout << endl;
	}
	cout << "迷宮中2的個數(shù)為：" << count << endl;
}


void BFS(int x, int y)			 //求從(x,y)出發(fā)的一條迷宮路徑
{
	Position p, p1, p2;
	p.x = x; p.y = y; 		//建立入口結(jié)點
	Maze[p.x][p.y] = 2;				//改為2避免重復(fù)查找
	rear++; qu[rear] = p;				//入口方塊進隊
	while (front != rear)				//隊不空循環(huán)
	{
		front++; p1 = qu[front];		//出隊方塊p1;
		for (int k = 0; k < 4; k++)		//試探p1的每個相鄰方位
		{
			p2.x = p1.x + V[k];			//找到p1的相鄰方塊p2
			p2.y = p1.y + H[k];
			if (p2.x >= 0 && p2.y >= 0 && p2.x < 30 && p2.y < 40 && Maze[p2.x][p2.y] == 0)
			{	//方塊p2有效并且可走
				Maze[p2.x][p2.y] = 2;	//改為2避免重復(fù)查找
				rear++;	qu[rear] = p2;	//方塊p2進隊
			}
		}
	}
	print_2();
}

int main()
{
	int x = 0, y = 0;		
	BFS(x, y);
	return 0;
}

輸出結(jié)果：

蠻力算法之深度優(yōu)先遍歷和廣度優(yōu)先遍歷——圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷，附帶案例：迷宮問題及矩陣中傳染性傳播問題,深度優(yōu)先,算法,廣度優(yōu)先,c++,visualstudio,數(shù)據(jù)結(jié)構(gòu),圖搜索

案例3：跳動方格

如果兩個相鄰方格（上下左右四個方向相鄰）內(nèi)的數(shù)的最大公約數(shù)大于 1 ，則可以從其中一個方格移動到另一個方格，當然也可以從另一個方格移回第一個方格。
假設(shè)開始時站在第 r 行第 c 列，請問可以移動到方格圖內(nèi)的多少個方格？

思路：采用廣度優(yōu)先遍歷，在將可行的方格放入到隊列之前，計數(shù)+1

易錯點+技巧點：

二維數(shù)組的初始化；

用同樣尺寸的數(shù)組記錄某個位置是否已經(jīng)被訪問過了；

沒有記錄路線的要求就可以不使用pre屬性

二維數(shù)組的動態(tài)初始化：

//動態(tài)定義一個二維數(shù)組，并將其全部值初始化為0
	int** map;
	map = new int* [m];
	
	for (int i = 0; i < m; i++)
	{
        int* row = new int[n];
		for (int j = 0; j < n; j++)
		{
			row[j] = 1;
		}
		map[i] = row;
	}

或者

//動態(tài)定義一個二維數(shù)組，并將其全部值初始化為0
	int** map;
	map = new int* [m];

	for (int i = 0; i < m; i++)
	{
		map[i] = new int[n];
		for (int j = 0; j < n; j++)
		{
			map[i][j] = 1;
		}
	}

使用memset

int** map = new int* [m];
for (int i = 0; i < m; ++i) {
	map[i] = new int[n];
	memset(map[i], 3, n * sizeof(int));
}

#include<iostream>
#define MAXQ 100					//隊列大小
#define MAxN 100						//最大迷宮大小
using namespace std;

int** map;
int** flag;	//記錄是否已經(jīng)被訪問了
int m;
int n;

int H[4] = { 0, 1, 0, -1 };			//水平偏移量,下標對應(yīng)方位號0～3
int V[4] = { -1, 0, 1, 0 };			//垂直偏移量

struct Position						//隊列元素類型
{
	int x, y;//當前方塊位置
};

Position qu[MAXQ];					//定義一個隊列qu
int front = -1, rear = -1;			//定義隊頭和隊尾

bool moreThanOne(int x, int y)
{
	//兩個數(shù)的最大公約數(shù)大于1，返回true
	int theSmallOne = x < y ? x : y;
	for (int i = 2; i <= theSmallOne; i++)
	{
		if (x % i == 0 && y % i == 0) return true;
	}
	return false;
}

void printMap()
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << map[i][j]<<"  ";
		}
		cout << endl;
	}
}

void BFS(int x, int y)			 
{
	int count = 0;          //記錄可以跳躍的個數(shù)
	Position p, p1, p2;
	p.x = x; p.y = y; 		//建立入口結(jié)點			
	rear++; qu[rear] = p;		
	count++;

	while (front != rear)				//隊不空循環(huán)
	{
		front++; p1 = qu[front];		//出隊方塊p1;
		for (int k = 0; k < 4; k++)		//試探p1的每個相鄰方位
		{
			p2.x = p1.x + V[k];			//找到p1的相鄰方塊p2
			p2.y = p1.y + H[k];

			if (p2.x >= 0 && p2.y >= 0 && p2.x < m && p2.y < n && moreThanOne(map[p2.x][p2.y], map[p1.x][p1.y]) && flag[p2.x][p2.y] != -1)
			{
				//方塊p2有效并且可走
				flag[p1.x][p1.y] = -1;	//改為-1避免重復(fù)查找
				rear++;	qu[rear] = p2;	//方塊p2進隊
				count++;
			}
		}
	}

	printMap();
	cout << count << endl;
}

int main()
{
	//初始化矩陣
	cin >> m >> n;
	map = new int* [m];       //動態(tài)初始化二維數(shù)組這一步很重要，但是這一步最容易忘
	flag = new int* [m];
	for (int i = 0; i < m; i++)
	{
		int* row = new int[n];
		int* flag_row = new int[n];
		for (int j = 0; j < n; j++)
		{
			cin >> row[j];
			flag_row[j] = 0;
		}
		map[i] = row;
		flag[i] = flag_row;
	}

	//輸入初始化的位置
	int x, y;
	cin >> x >> y;
	BFS(x - 1, y - 1);

	return 0;
}

運行結(jié)果：

蠻力算法之深度優(yōu)先遍歷和廣度優(yōu)先遍歷——圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷，附帶案例：迷宮問題及矩陣中傳染性傳播問題,深度優(yōu)先,算法,廣度優(yōu)先,c++,visualstudio,數(shù)據(jù)結(jié)構(gòu),圖搜索文章來源地址http://www.zghlxwxcb.cn/news/detail-754785.html

到了這里，關(guān)于蠻力算法之深度優(yōu)先遍歷和廣度優(yōu)先遍歷——圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷，附帶案例：迷宮問題及矩陣中傳染性傳播問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔相關(guān)法律責任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費用

Python 算法基礎(chǔ)篇之圖的遍歷算法：深度優(yōu)先搜索和廣度優(yōu)先搜索
2023年10月31日
瀏覽(19)
【數(shù)據(jù)結(jié)構(gòu)與算法】圖的基本概念 | 鄰接矩陣和鄰接表 | 廣度優(yōu)先遍歷和深度優(yōu)先遍歷
?? 作者：@ 阿亮joy. ?? 專欄：《數(shù)據(jù)結(jié)構(gòu)與算法要嘯著學(xué)》 ?? 座右銘：每個優(yōu)秀的人都有一段沉默的時光，那段時光是付出了很多努力卻得不到結(jié)果的日子，我們把它叫做扎根圖是由頂點集合及頂點間的關(guān)系組成的一種數(shù)據(jù)結(jié)構(gòu)：G = (V， E) ，其中：頂點集合V = {x|x屬于某
2024年02月04日
瀏覽(44)
數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)-學(xué)習-24-圖的遍歷之DFS（深度優(yōu)先搜索）和BFS（廣度優(yōu)先搜索）
目錄一、遍歷定義二、遍歷實質(zhì) 三、DFS 四、BFS 五、宏定義六、自定義類型七、函數(shù)實現(xiàn) 1、DFS（鄰接矩陣實現(xiàn)） 2、DFS（鄰接表實現(xiàn)） 3、BFS（鄰接矩陣實現(xiàn)） 4、BFS（鄰接表實現(xiàn)） 5、打印鄰接矩陣遍歷順序 ?6、打印鄰接表遍歷順序八、遍歷算法效率分析 1、DFS 2、BFS 九
2024年02月03日
瀏覽(19)
圖的遍歷——深度優(yōu)先遍歷與廣度優(yōu)先遍歷
目錄何謂遍歷？圖的遍歷特點圖的遍歷方式深度優(yōu)先搜索過程分析案例分析：算法的代碼實現(xiàn) ?測試案例：測試結(jié)果如下：遍歷非連通圖算法復(fù)雜度分析額外補充廣度優(yōu)先搜索過程分析輔助隊列算法的代碼實現(xiàn) 隊列部分廣度搜索部分測試案例：測試結(jié)果：非連
2024年02月04日
瀏覽(17)
圖的廣度優(yōu)先遍歷和深度優(yōu)先遍歷
前言：在上一篇博客我們學(xué)習了圖的基本操作，包括圖的建立、結(jié)點插入與刪除等操作，怎么判斷我們建立的圖是否正確，很簡單把它輸出出來就是，但是如何輸出它，這就是圖的遍歷問題了。圖的遍歷是指從圖中的某一頂點出發(fā)，按照某種搜索方法沿著圖中的邊對圖中的所
2024年02月11日
瀏覽(16)
圖的兩種遍歷：深度優(yōu)先遍歷+廣度優(yōu)先遍歷
深度優(yōu)先遍歷是指按照深度方向搜索，它類似于樹的先根遍歷，是樹的先根遍歷的推廣。基本思想（通俗）選一條路走到底，直到走不通，就原路返回看看是否還有路可走，如果返回到起點還無路可走，說明深度優(yōu)先遍歷已完成。這是要深度遍歷的無向圖： ? ?深
2024年02月06日
瀏覽(16)
圖的二種遍歷-廣度優(yōu)先遍歷和深度優(yōu)先遍歷
1.樹的廣度優(yōu)先遍歷這樣一個圖中，是如何實現(xiàn)廣度優(yōu)先遍歷的呢，首先，從1遍歷完成之后，在去遍歷2,3,4，最后遍歷5 ，6 , 7? , 8。這也就是為什么叫做廣度優(yōu)先遍歷，是一層一層的往廣的遍歷不存在“回路”，搜索相鄰的結(jié)點時，不可能搜到已經(jīng)訪問過的結(jié)點樹的廣度優(yōu)
2024年02月02日
瀏覽(24)
圖的遍歷（廣度優(yōu)先遍歷BFS，深度優(yōu)先遍歷DFS）
目錄圖的遍歷概念：圖的廣度優(yōu)先遍歷（BFS）：代碼實現(xiàn)如下：測試如下：注意：圖的深度優(yōu)先遍歷（DFS）：代碼實現(xiàn)如下：測試如下：總代碼：結(jié)語：給定一個圖G和其中任意一個頂點v0，從v0出發(fā)，沿著圖中各邊訪問圖中的所有頂點，且每個頂點僅被遍歷一次。\\\"遍
2024年02月21日
瀏覽(15)
圖的遍歷-深度優(yōu)先遍歷與廣度優(yōu)先遍歷（C語言）
圖的遍歷概念：指的是從圖中的任一頂點出發(fā)，對圖中的所有頂點訪問一次且只訪問一次。鄰接矩陣及鄰接表的創(chuàng)建：圖的存儲結(jié)構(gòu)-無向鄰接矩陣與無向鄰接表（C語言）. 結(jié)構(gòu)定義鄰接矩陣的深度優(yōu)先遍歷操作鄰接矩陣的深度優(yōu)先遞歸算法結(jié)構(gòu)定義鄰接表的深度優(yōu)先遍
2024年02月06日
瀏覽(21)
大話數(shù)據(jù)結(jié)構(gòu)-圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷
??圖的遍歷分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷兩種。 ??深度優(yōu)先遍歷（Depth First Search），也稱為深度優(yōu)先搜索，簡稱DFS，深度優(yōu)先遍歷，是指從某一個頂點開始，按照一定的規(guī)則，訪問并記錄下一個未訪問頂點。對于非連通圖，則是按連通分量，采用同一規(guī)則進行深度優(yōu)
2024年02月04日
瀏覽(24)