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

文档介绍：判断一个简单图是否为平面图(c++ ) #include <iostream> #include <cstdio> #include <cstdlib> #include <ctime> #include <vector> #include <list> #include <queue> #include <deque> #include <stack> #include <string> #include <algorithm> #include <cassert> #include <cctype> using namespace std; /// 图, 碎片,环, 面以及道路的存储结构 typedef vector< list<int>* > graph; typedef vector< list<int>* > fragment; typedef list<int> circle; /// 环用链表表示, 链表按顺时针记录环的点 typedef list<int> face; /// 面用链表表示即可, 链表按顺时针记录面的点 typedef list<int> path; const int MAXINT = ((unsigned)-1)>>1; const int MAXPOINTCOUNT = 200; int colour[MAXPOINTCOUNT]; /// 为遍历设置的数组 const int WHITE = 0; const int GRAY = 1; const int BLACK = 2; int parent[MAXPOINTCOUNT]; /// 为遍历设置的数组 int depth[MAXPOINTCOUNT]; int pointKind[MAXPOINTCOUNT]; const int EMBEDED = -1; const int AVAILABLE = 0; bool pointEmbed[MAXPOINTCOUNT]; bool edgeEmbed[MAXPOINTCOUNT][MAXPOINTCOUNT]; int lowpoint[MAXPOINTCOUNT]; /// 为找割点设置的数组 int lowneighbour[MAXPOINTCOUNT]; int pointType[MAXPOINTCOUNT]; const int NONCUTVERTEX = 0; const int CUTVERTEX = 1; int leave[MAXPOINTCOUNT]; int enter[MAXPOINTCOUNT]; int visitTime; void removeBidegreePoint(graph *g) {} void removeSingleDegreePoint(graph *g) {} void removeParallelEdge(graph *g) {} graph* createGraph(int pointCount) { graph* g= new graph; for (int i=0; i<pointCount; i++) { g->push_back(new list<int>); } return g; } graph* inputGraph(void) { int pointCount, edgeCount, from, to; printf(" 请输入顶点个数: "); cin >> pointCount; printf("\n 请输入边的条数: "); cin >> edgeCount; graph *g= createGraph(pointCount); cout<<"\n 请输入图的信息:"<<endl; for (int i=0; i<edgeCount; i++) { cin >> from >> to; g->at(from)->push_back(to); g->at(to)->push_back(from); } return g; } circle* getOneCircle(const graph *g, int start) { int pointCount = g->size();// 图的节点数 for (int i=0; i<pointCount; i++) { colour[i] = WHITE; } queue<int> q; (start); colour[start] = GRAY; parent[start] = -1; depth[start] = 0; list<int>::iterator tra; list<int>::iterator end; int u,v; /// 对图进