قطر گراف یعنی طولانی ترین مسیر بین ۲ راس دلخواه در گراف.
در جست و جوی اول سطح یا BFS هر بار یک راس رو گسترش میدیم و به آخر صف اضافه می کنیم .
یعنی مثلا اگر گراف ما این باشه :
/*
* A
* B C
* D E F
* G
در جست و جوی BFS در طول الگوریتم این صف به این شکل میشه :
* meghdar avalie : (A,B),(A,C)
* gostraresh (A,B) (A,C),(A,B,D),(A,B,E)
* (A,B,D),(A,B,E),(A,C,F)
* (A,B,E),(A,C,F),(A,B,D,G)
* (A,C,F),(A,B,D,G)
* (A,B,D,G)
* ...
*/
حالا کافیه که داخل این عبارات بزرگترین مجموعه رو پیدا کنیم که میشه قطر گراف مثلا توی مثال بالا ABDG قطر هستش .
برای این کار اگر از dfs هم اگر استفاده کنی باز هم به جواب میرسی .
داخل کد زیر فرض کردم که گراف همبند هستش اگر گراف همبند نباشه باید هر راس رو وقتی پیمایش کردی flag بزنی بعد این تابع رو برای همه ی راس هایی که flag نخوردن صدا بزنی و از بین همه ی نتایجی که بر میگردن بزرگترینشون رو انتخاب کنی .
کد : اجرا زنده
#include <algorithm>
#include <deque>
#include <iostream>
#include <list>
#include <map>
#include <vector>
#include <string>
/*
* A
* B C
* D E F
* G
*
* meghdar avalie : (A,B),(A,C)
* gostraresh (A,B) (A,C),(A,B,D),(A,B,E)
* (A,B,D),(A,B,E),(A,C,F)
* (A,B,E),(A,C,F),(A,B,D,G)
* (A,C,F),(A,B,D,G)
* (A,B,D,G)
* ...
*/
using AdjList=std::vector<std::vector<size_t>>;
std::vector<size_t> findMaxDistance(const AdjList& adjList)
{
std::deque<std::vector<size_t>> remain_nodes;
//meghdar avalie
for(size_t i=0;i<adjList[0].size();i++)
{
std::vector<size_t> pval;
pval.push_back(0);
pval.push_back(adjList[0][i]);
remain_nodes.push_back(pval);
}
//
std::vector<size_t> max_dist=remain_nodes[0];//for storing the longest path
while(remain_nodes.size() > 0 )
{
int Node=remain_nodes[0][remain_nodes[0].size()-1];//last node of the first pair
//expand first pair
if(Node<adjList.size()){
for(size_t i=0;i<adjList[Node].size();i++){
if(std::find(remain_nodes[0].begin(),//if not expanded before
remain_nodes[0].end(),adjList[Node][i])==remain_nodes[0].end()){
std::vector<size_t> temp=remain_nodes[0];
temp.push_back(adjList[Node][i]);
remain_nodes.push_back(std::move(temp));
}
}
}
//if expanded node is bigger than max_dist put it in max_dist
if(remain_nodes[0].size()>max_dist.size())
max_dist=remain_nodes[0];
// remove expanded pair
remain_nodes.pop_front();
}
return max_dist;
}
int main()
{
//graph shekl bala
AdjList adjList({ {1,2},// B C
{3,4},//D E
{5},//F
{6}//G
});
std::vector<size_t> result=findMaxDistance(adjList);
//printing the result
std::map<int,std::string> Names;
Names[0]="A";Names[1]="B";Names[2]="C";
Names[3]="D";Names[4]="E";Names[5]="F";
Names[6]="G";
for(auto i:result){
std::cout<<Names[i];//result ABDG
}
}