判断一个简单图是否为平面图(c++ )

《判断一个简单图是否为平面图(c++ )》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、判断一个简单图是否为平面图(c++)#include#include#include#include#include#include#include#include#include#include#include#include#includeusingnamespacestd;///图,碎片,环,面以及道路的存储结构typedefve

2、ctor*>graph;typedefvector*>fragment;typedeflistcircle;///环用链表表示,链表按顺时针记录环的点typedeflistface;///面用链表表示即可,链表按顺时针记录面的点typedeflistpath;constintMAXINT=((unsigned)-1)>>1;constintMAXPOINTCOUNT=200;intcolour[MAXPOINTCOUNT];///为遍历设置的数组constintWHITE=

3、0;constintGRAY=1;constintBLACK=2;intparent[MAXPOINTCOUNT];///为遍历设置的数组intdepth[MAXPOINTCOUNT];intpointKind[MAXPOINTCOUNT];constintEMBEDED=-1;constintAVAILABLE=0;boolpointEmbed[MAXPOINTCOUNT];booledgeEmbed[MAXPOINTCOUNT][MAXPOINTCOUNT];intlowpoint[MAXPOINTCOUNT];///为找割点设置的数组i

4、ntlowneighbour[MAXPOINTCOUNT];intpointType[MAXPOINTCOUNT];constintNONCUTVERTEX=0;constintCUTVERTEX=1;intleave[MAXPOINTCOUNT];intenter[MAXPOINTCOUNT];intvisitTime;voidremoveBidegreePoint(graph*g){}voidremoveSingleDegreePoint(graph*g){}voidremoveParallelEdge(graph*g){}graph*c

5、reateGraph(intpointCount){graph*g=newgraph;for(inti=0;ipush_back(newlist);}returng;}graph*inputGraph(void){intpointCount,edgeCount,from,to;printf("请输入顶点个数：");cin>>pointCount;printf("请输入边的条数:");cin>>edgeCount;graph*g=createGraph(pointCount);cout<<"

6、请输入图的信息:"<>from>>to;g->at(from)->push_back(to);g->at(to)->push_back(from);}returng;}circle*getOneCircle(constgraph*g,intstart){intpointCount=g->size();//图的节点数for(inti=0;iq;q.push(start);colo

7、ur[start]=GRAY;parent[start]=-1;depth[start]=0;list::iteratortra;list::iteratorend;intu,v;///对图进行一次广度优先遍历即可以找到一个环while(!q.empty()){u=q.front();q.pop();tra=g->at(u)->begin();end=g->at(u)->end();for(;tra!=end;tra++){v=*tra;//解引用操作if(colour[v]==WHITE){q.push(v);colou

8、r[v]=GRAY;parent[v]=u;depth[v]=depth[u]+1;}///广度优先树的某一片树叶有在队列中的邻居,则可以找到一个环elseif(c