| 判断有向图是否有环 、环的个数以及环中元素 | 您所在的位置：网站首页 › 上环的步骤 › 判断有向图是否有环 、环的个数以及环中元素 |
|
判断有向图是否有环有三种方法：拓扑排序、深度遍历+回溯、深度遍历 + 判断后退边 这里使用 拓扑排序 和 深度遍历 + 回溯判断是不是环。使用 深度遍历 + 判断后退边找出环个数 以及环中元素 1、拓扑排序 思想：找入度为0的顶点，输出顶点，删除出边。循环到无顶点输出。 若：输出所有顶点，则课拓扑排序，无环；反之，则不能拓扑排序，有环 使用：可以使用拓扑排序为有向无环图每一个结点进行编号，拓扑排序输出的顺序可以为编号顺序 源代码： [cpp] view plain copy #include using namespace std; const int MAX_Vertex_Num = 20; template class MGraph { public: void CreateGraph();//创建图 int LocateVex(VexType v);//返回顶点v所在顶点向量中的位置（下标） void CheckCircle(); private: VexType vexs[MAX_Vertex_Num];//顶点向量 ArcType arcs[MAX_Vertex_Num][MAX_Vertex_Num]; //这里把邻接矩阵类型用模板表示，主要是为了处理有权值的情况，比如：权值可以为小数（代价），也可以为整数 int vexnum;//顶点数 int arcnum;//边数 private: bool TopSort(); }; template void MGraph::CreateGraph() { VexType first; VexType Secend; coutvexnum; coutarcnum; cout for (int j=0;j cin>>first>>Secend; //如果边有权值的话，则还应该输入权值 int x = LocateVex(first); int y = LocateVex(Secend); arcs[x][y]=1;//如果是有权的话，这里应该是arc[x][y]=权值 } } /* 参数：v：表示顶点向量中一个值 函数返回值：函数返回v在顶点向量中的下标 */ template int MGraph::LocateVex(VexType v) { for (int i=0;i return i; } } return -1; } /*有向图可以拓扑排序的条件是：图中没有环。 具体方法： ⑴ 从图中选择一个入度为0的点加入拓扑序列。 ⑵ 从图中删除该结点以及它的所有出边（即与之相邻点入度减1）。 */ template bool MGraph::TopSort() { int count = 0;//拓扑排序输出顶点的个数 int top = -1; int stack[MAX_Vertex_Num]; int indegree[MAX_Vertex_Num]={0}; //求各个顶点的入度--邻接矩阵要查询该元素的列（记录入度情况）-- //如果是邻接表，就是麻烦在这里，查询结点入度很不方便 for (int i=0;i if (arcs[j][i]!=0) { num++; } } indegree[i]=num; } //把入度为0的顶点入栈 for (int i=0;i stack[++top]=i;//顶点的下标 } } //处理入度为0的结点：把入度为0的结点出栈，删除与之有关的边 while (top>-1) { int x = stack[top--]; cout arcs[x][i]=0;//删除到下标为i的顶点的边，这时此顶点的入度减一 indegree[i]--; if (!indegree[i])//顶点的入度为0，则入栈 { stack[++top]=i; } } } } cout if (TopSort()) { cout MGraph G; G.CreateGraph(); G.CheckCircle(); system("pause"); return 1; }测试： 有向图： 结果： 2、深度遍历 + 回溯 思想：用回溯法,遍历时，如果遇到了之前访问过的结点，则图中存在环。 代码： [cpp] view plain copy #include using namespace std; const int MAX_Vertex_Num = 20; template class MGraph { public: void CreateGraph();//创建图 int LocateVex(VexType v);//返回顶点v所在顶点向量中的位置（下标） bool CheckCircle();//检查图中有无环 private: VexType vexs[MAX_Vertex_Num];//顶点向量 ArcType arcs[MAX_Vertex_Num][MAX_Vertex_Num]; //这里把邻接矩阵类型用模板表示，主要是为了处理有权值的情况，比如：权值可以为小数（代价），也可以为整数 int vexnum;//顶点数 int arcnum;//边数 private: void CheckCircle(int u,bool& isExist,bool visited[MAX_Vertex_Num],bool Isvisited[MAX_Vertex_Num]); }; template void MGraph::CreateGraph() { VexType first; VexType Secend; coutvexnum; coutarcnum; cout for (int j=0;j cin>>first>>Secend; //如果边有权值的话，则还应该输入权值 int x = LocateVex(first); int y = LocateVex(Secend); arcs[x][y]=1;//如果是有权的话，这里应该是arc[x][y]=权值 } } /* 参数：v：表示顶点向量中一个值 函数返回值：函数返回v在顶点向量中的下标 */ template int MGraph::LocateVex(VexType v) { for (int i=0;i return i; } } return -1; } /*思想：用回溯法,遍历时，如果遇到了之前访问过的结点，则图中存在环。 引入visited数组的原因： 1）在一次深度遍历时，检测路径上是否结点是否已经被检测到，如果被重复检测，则表示有环。 2）注意，在深度递归返回时，总是要把visited置为false。 引入Isvisited数组的原因： 1）用于记录目前为止深度遍历过程中遇到的顶点。 2）因为，我们不一定以所有结点为起始点都进行一次深度遍历。 3）举例，在结点A为起点，进行深度遍历时，遇到了结点B，此时Isvisited在A和B两个位置都为true。 那么没遇到环，那么我们就不用再以B为起始点继续进行一次深度遍历了， 因为A为起点的深度遍历已经验证不会有环了。 */ template void MGraph::CheckCircle(int u,bool& isExist,bool visited[MAX_Vertex_Num],bool Isvisited[MAX_Vertex_Num]) { visited[u]=true; Isvisited[u]=true; for (int j=0;j if (visited[j]==false) { CheckCircle(j,isExist,visited,Isvisited); } else { isExist = true; } } } visited[u]=false;//回溯，如果不写就变成一半的深度遍历，不能进行判断是否有边存在 } template bool MGraph::CheckCircle() { bool isExist = false; bool Isvisited[MAX_Vertex_Num]={false}; bool visited[MAX_Vertex_Num]={false}; for (int i=0;i CheckCircle(i,isExist,visited,Isvisited); if (isExist) { return true; } } } return isExist; } int main() { MGraph G; G.CreateGraph(); if (G.CheckCircle()) { cout public: void CreateGraph();//创建图 int LocateVex(VexType v);//返回顶点v所在顶点向量中的位置（下标） void CheckCircle(); private: VexType vexs[MAX_Vertex_Num];//顶点向量 ArcType arcs[MAX_Vertex_Num][MAX_Vertex_Num]; //这里把邻接矩阵类型用模板表示，主要是为了处理有权值的情况，比如：权值可以为小数（代价），也可以为整数 int vexnum;//顶点数 int arcnum;//边数 private: void DFS(int x,bool visited[MAX_Vertex_Num],int stack[MAX_Vertex_Num],int& top,bool inStack[MAX_Vertex_Num],int& count); }; template void MGraph::CreateGraph() { VexType first; VexType Secend; coutvexnum; coutarcnum; cout for (int j=0;j cin>>first>>Secend; //如果边有权值的话，则还应该输入权值 int x = LocateVex(first); int y = LocateVex(Secend); arcs[x][y]=1;//如果是有权的话，这里应该是arc[x][y]=权值 } } /* 参数：v：表示顶点向量中一个值 函数返回值：函数返回v在顶点向量中的下标 */ template int MGraph::LocateVex(VexType v) { for (int i=0;i return i; } } return -1; } /* 检查图中是不是有回向边 思想： 如果有回向边，则无环，反之有环 */ template void MGraph::CheckCircle() { int count=0;//环的个数 int top=-1; int stack[MAX_Vertex_Num]; bool inStack[MAX_Vertex_Num]={false}; bool visited[MAX_Vertex_Num]={false}; for (int i=0;i DFS(i,visited,stack,top,inStack,count); } } } template void MGraph::DFS(int x,bool visited[MAX_Vertex_Num],int stack[MAX_Vertex_Num],int& top,bool inStack[MAX_Vertex_Num],int& count) { visited[x]=true; stack[++top]=x; inStack[x]=true; for (int i=0;i if (!inStack[i]) { DFS(i,visited,stack,top,inStack,count); } else //条件成立，表示下标为x的顶点到 下标为i的顶点有环 { count++; cout MGraph G; G.CreateGraph(); G.CheckCircle(); system("pause"); return 1; }来源：http://blog.csdn.net/insistgogo/article/details/6978718 |
| CopyRight 2018-2019 实验室设备网 版权所有 |