【概述】

LexBFS 是字典序廣度優先搜索（Lexicographic BFS），其常用于弦圖的判定。

每次按從?n 到 1 的順序依次給點編號，每個點維護一個?list，用于記錄與其相鄰的已標號點的標號，每次選擇 list 中字典序最大的未標號點標號。

LexBFS 與 BFS 的不同，在于每次擴展的結點加了特殊的順序

檢查時利用桶排的思想，在更新一個點的 list 時，新建一個桶，且任何時候桶的數目不超過 n，通過維護桶中元素來進行判定

【實現】

struct Edge{int to;Edge(){}Edge(int to):to(to){} }; struct Node{int id,num;Node(){}Node(int id,int num):id(id),num(num){}friend bool operator<(Node a,Node b) {return a.num<b.num;} }; int n,m; int G[N][N]; vector<Edge>edge[N]; int link[N],tot;//標號序列 int order[N];//完美消除序列 int num[N];//點編號 int bucket[N];//更新一個點的標號序列時的桶 bool vis[N];void bfs(int x){//維護標號序列memset(num,0,sizeof(num));memset(link,0,sizeof(link));memset(vis,0,sizeof(vis));tot=n;priority_queue<Node> Q;Q.push(Node(x,1));while(!Q.empty()) {Node now=Q.top();Q.pop();if(!vis[now.id]){vis[now.id]=true;link[tot]=now.id;order[now.id]=tot;tot--;if(tot==0)break;}for(int i=0;i<edge[now.id].size();i++) {int to=edge[now.id][i].to;num[to]++;if(!vis[to])Q.push(Node(to,num[to]));}} } bool check() {bfs(1);//維護標號序列for(int i=1;i<=n;i++){int minn=n+1;int tail=0;//桶的指針int value;for(int j=0;j<edge[link[i]].size();j++) {int to=edge[link[i]][j].to;if(order[to]>i) {if(minn>order[to]) {minn=order[to];value=to;}bucket[tail++]=to;//入桶}}for(int j=0;j<tail;j++) {if(bucket[j]!=value&&G[value][bucket[j]]==0)return false;}}return true; } int main() {scanf("%d%d",&n,&m);memset(G,0,sizeof(G));for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);edge[x].push_back(y);edge[y].push_back(x);G[x][y]=1;G[y][x]=1;}if(check())printf("Yes\n");elseprintf("No\n");return 0; }

?

總結

以上是生活随笔為你收集整理的图论 —— 弦图 —— LexBFS 算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。