本篇內(nèi)容主要講解“Java廣度優(yōu)先遍歷怎么實(shí)現(xiàn)”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“Java廣度優(yōu)先遍歷怎么實(shí)現(xiàn)”吧!

創(chuàng)新互聯(lián)長(zhǎng)期為上千家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開(kāi)放共贏平臺(tái)，與合作伙伴共同營(yíng)造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為運(yùn)河企業(yè)提供專業(yè)的網(wǎng)站建設(shè)、成都做網(wǎng)站，運(yùn)河網(wǎng)站改版等技術(shù)服務(wù)。擁有10余年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開(kāi)發(fā)。

廣度優(yōu)先遍歷 breadth first search   BFS 

圖的深度優(yōu)先遍歷類似與樹(shù)的前序遍歷，  廣度優(yōu)先遍歷類似與樹(shù)的 層序 遍歷。

void printNodeByLevel(NODE* root)//Tree層序遍歷
{
	if(root == NULL)
	{
		return;
	}
	vector<NODE*>vec;
	vec.push_back(root);
	int cur=0;
	while(cur<vec.size())
	{
		cout<<vec[cur]->data<<" ";
		if(vec.[cur]->left != NULL)
		{
			vec.push_back(vec.[cur]->left);
		}
		if(vec.[cur]->right != NULL)
		{
			vec.push_back(vec.[cur]->right);
		}
		++cur;
	}
	cout<<endl;
}

類似于一個(gè)分層搜索的過(guò)程，廣度優(yōu)先遍歷需要使用一個(gè)隊(duì)列以保持訪問(wèn)過(guò)的結(jié)點(diǎn)的順序，以便按這個(gè)順序來(lái)訪問(wèn)這些結(jié)點(diǎn)的鄰接結(jié)點(diǎn)。

具體算法表述如下：

1. 訪問(wèn)初始結(jié)點(diǎn)v并標(biāo)記結(jié)點(diǎn)v為已訪問(wèn)。

2. 結(jié)點(diǎn)v入隊(duì)列

3. 當(dāng)隊(duì)列非空時(shí)，繼續(xù)執(zhí)行，否則算法結(jié)束。

4. 出隊(duì)列，取得隊(duì)頭結(jié)點(diǎn)u。

5. 查找結(jié)點(diǎn)u的第一個(gè)鄰接結(jié)點(diǎn)w。

6. 若結(jié)點(diǎn)u的鄰接結(jié)點(diǎn)w不存在，則轉(zhuǎn)到步驟3；否則循環(huán)執(zhí)行以下三個(gè)步驟：

   1). 若結(jié)點(diǎn)w尚未被訪問(wèn)，則訪問(wèn)結(jié)點(diǎn)w并標(biāo)記為已訪問(wèn)。
   2). 結(jié)點(diǎn)w入隊(duì)列
   3). 查找結(jié)點(diǎn)u的繼w鄰接結(jié)點(diǎn)后的下一個(gè)鄰接結(jié)點(diǎn)w，轉(zhuǎn)到步驟6。

如下圖，其廣度優(yōu)先算法的遍歷順序?yàn)椋?->2->3->4->5->6->7->8

廣度遍歷-鄰接矩陣
bool visited[MAX];
void BFSTraverse(MGraph G)
{
	for(int i=0;i<G.numV; i++)
	{
		visited[i] = false;
	}
	Queue tempQ;  
	InitQueue(& tempQ);//初始化建立一個(gè)隊(duì)列
	for(int i=0;i<G.numV; i++)
	{
		if(! visited[i])//如果沒(méi)訪問(wèn)過(guò)就處理
		{
			visited[i] = true;
			cout<<G.ArrVex[i];
			enQueue(&Q,i)//將此頂點(diǎn)入隊(duì)列
			while(! QueueEmpty(Q))//如果當(dāng)前隊(duì)列不為空
			{
				DeQueue(&Q,&i);//將隊(duì)中元素出隊(duì)列 賦值給i;
				for(int j=0;j<G.numV;j++)
				{
					if(G.arc[i][j]==1 && !visited[j])
					{
						visited[j] = true;
						cout<< G.ArrVex[j];
						EnQueue(&Q，j);
					}
				}
			}
		}
	}
	
}

鄰接表 

鄰接表 BFS 遍歷
bool visited[MAX];  
void BFSTraverse(MGraph G)  
{  
    for(int i=0;i<G.numV; i++)  
    {  
        visited[i] = false;  
    }  
    Queue tempQ;    
    InitQueue(& tempQ);//初始化建立一個(gè)隊(duì)列  
    for(int i=0;i<G.numV; i++)  
    {  
        if(! visited[i])//如果沒(méi)訪問(wèn)過(guò)就處理  
        {  
            visited[i] = true;  
            cout<<G.adjlist[i].data;  
            enQueue(&Q,i)//將此頂點(diǎn)入隊(duì)列  
            while(! QueueEmpty(Q))//如果當(dāng)前隊(duì)列不為空  
            {  
                DeQueue(&Q,&i);//將隊(duì)中元素出隊(duì)列 賦值給i;
                EdgeNode* p =NULL;
                p=G.adjlist[i].firstedge;
                while(p)
                {
                    if(!visited[p->adjvex])  
                    {  
                        visited[p->adjvex] = true;  
                        cout<< adjlist[j].data;  
                        EnQueue(&Q，j);  
                    }
                     p=p->next;
                }  
            }  
        }  
    }  
      
}

到此，相信大家對(duì)“Java廣度優(yōu)先遍歷怎么實(shí)現(xiàn)”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

本文名稱：Java廣度優(yōu)先遍歷怎么實(shí)現(xiàn)
文章源于：http://www.chinadenli.net/article18/igpgdp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營(yíng)銷推廣、關(guān)鍵詞優(yōu)化、網(wǎng)站營(yíng)銷、品牌網(wǎng)站制作、電子商務(wù)、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)