資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究偶數距離節點對的數量（使用 BFS）
在本文中，我們將找到圖中彼此之間距離為偶數的節點對的數量。我們將使用廣度優先搜尋 (BFS) 方法來查詢總數。
在本文討論的方法中，我們將使用一個包含整數對的佇列資料結構。佇列資料結構將允許我們使用廣度優先搜尋演算法 (BFS) 遍歷圖。我們將選擇一個隨機節點並從該節點應用廣度優先搜尋。我們將使用兩個變數來跟蹤出現在我們給定節點的偶數級別的節點數量，以及出現在我們給定節點的奇數級別的節點數量。所有與源節點距離為偶數的節點也彼此之間距離為偶數，所有與源節點距離為奇數的節點也彼此之間距離為偶數。因此，使用這兩個變數，我們可以計算彼此之間距離為偶數的節點總數。
問題陳述 - 給定一個圖，該圖是連通的並且不包含迴圈，包含 N 個節點和 N-1 條邊，我們需要找到彼此之間距離為偶數的節點對的總數。
注意 - 圖以鄰接表的形式給出。
示例
輸入
0
/
1
/
2
/
3
輸出
2
解釋
以下是唯一彼此之間距離為偶數的節點 {0,2}、{1,3}，所以輸出為 2
輸入
0
/ \
1 2
/ \
3 4
輸出
4
解釋
彼此之間距離為偶數的節點為 -
{0,3}, {0,4}, {1,2}, {3,4}
因此，輸出為 4。
輸入
0
/ \
1 2
/ \ / \
3 4 5 6
輸出
11
解釋
彼此之間距離為偶數的節點為 -
{0,3}, {0,4}, {0,5}, {0,6}, {1,2}, {3,4}, {3,5}, {3,6}, {4,5}, {4,6}, {5,6}
所以，輸出為 11。
方法
在這種方法中，我們將使用一個包含整數對的佇列資料結構。我們將隨機選擇一個源節點並將其推入佇列。然後，我們將使用選定的源節點應用廣度優先搜尋演算法。我們將維護兩個變數，它們將跟蹤與我們的源節點距離為偶數的節點數量以及與我們的源節點距離為奇數的節點數量。某個節點的極性將儲存在對中的第二個整數中。使用這兩個變數，我們可以計算彼此之間距離為偶數的節點總數。
演算法
步驟 1 - 建立一個向量 vis，它將跟蹤我們已訪問的節點。
步驟 2 - 建立一個佇列資料結構。
步驟 2.1 - 佇列將包含一對整數，對中的第一個整數將是圖中的節點，第二個整數將表示極性，即節點與我們的源節點的距離是偶數還是奇數。
步驟 2.2 - 將源節點與極性 0 推入佇列。
步驟 2.3 - 建立兩個變數，它們將儲存奇數和偶數級別的節點數量。
步驟 3 - 迴圈直到佇列變空
步驟 3.1 - 在每次迭代中，取出佇列的第一個元素並將其標記為已訪問。
步驟 3.2 - 迴圈當前節點的每個鄰居
步驟 3.3 - 如果鄰居未被訪問，則將其新增到佇列中，其極性與當前節點的極性相反。
步驟 3.4 - 如果當前節點的極性為偶數，則將 1 加到偶數變數中，否則將 1 加到奇數變數中
步驟 4 - 佇列變空後，答案可以計算如下：答案 = 偶數*(偶數-1)/2 + 奇數*(奇數-1)/2
步驟 5 - 返回答案。
示例
下面的 C++ 程式是上述方法的實現 -
#include <bits/stdc++.h>
using namespace std;
int Count_pair_nodes(vector<vector<int>> &gph){
int N = gph.size();
vector<int> vis(N,0);
queue<pair<int,int>> que;
que.push({0,0});
long long even_pos = 0 , odd_pos = 0;
while(!que.empty()){
int vertex = que.front().first , odd_even = que.front().second;
que.pop();
vis[vertex] = 1;
for(auto it:gph[vertex]){
if(vis[it]==0)que.push({it,1-odd_even});
}
if(odd_even)even_pos++;
else odd_pos++;
}
long long ans = even_pos*(even_pos-1)/2 + odd_pos*(odd_pos-1)/2;
return ans;
}
int main(){
vector<vector<int>> gph = {
{1},
{0,2},
{1,3},
{2}
};
cout<<Count_pair_nodes(gph)<<endl;
return 0;
}
輸出
2
時間複雜度 - O(N)，其中 N 是圖中節點的數量。
空間複雜度 - O(N)
64 次檢視
