Java廣度優先遍歷怎么實現

本篇內容主要講解“Java廣度優先遍歷怎么實現”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Java廣度優先遍歷怎么實現”吧!

廣度優先遍歷 breadth first search   BFS 

圖的深度優先遍歷類似與樹的前序遍歷，  廣度優先遍歷類似與樹的 層序 遍歷。

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;
}

類似于一個分層搜索的過程，廣度優先遍歷需要使用一個隊列以保持訪問過的結點的順序，以便按這個順序來訪問這些結點的鄰接結點。

具體算法表述如下：

1. 訪問初始結點v并標記結點v為已訪問。

2. 結點v入隊列

3. 當隊列非空時，繼續執行，否則算法結束。

4. 出隊列，取得隊頭結點u。

5. 查找結點u的第一個鄰接結點w。

6. 若結點u的鄰接結點w不存在，則轉到步驟3；否則循環執行以下三個步驟：

   1). 若結點w尚未被訪問，則訪問結點w并標記為已訪問。
   2). 結點w入隊列
   3). 查找結點u的繼w鄰接結點后的下一個鄰接結點w，轉到步驟6。

   
   

如下圖，其廣度優先算法的遍歷順序為：1->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);//初始化建立一個隊列
	for(int i=0;i<G.numV; i++)
	{
		if(! visited[i])//如果沒訪問過就處理
		{
			visited[i] = true;
			cout<<G.ArrVex[i];
			enQueue(&Q,i)//將此頂點入隊列
			while(! QueueEmpty(Q))//如果當前隊列不為空
			{
				DeQueue(&Q,&i);//將隊中元素出隊列 賦值給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);//初始化建立一個隊列  
    for(int i=0;i<G.numV; i++)  
    {  
        if(! visited[i])//如果沒訪問過就處理  
        {  
            visited[i] = true;  
            cout<<G.adjlist[i].data;  
            enQueue(&Q,i)//將此頂點入隊列  
            while(! QueueEmpty(Q))//如果當前隊列不為空  
            {  
                DeQueue(&Q,&i);//將隊中元素出隊列 賦值給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;
                }  
            }  
        }  
    }  
      
}

到此，相信大家對“Java廣度優先遍歷怎么實現”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！