精华内容
下载资源
问答
  • 判断图中是否有回路
    千次阅读
    2019-11-19 22:33:01

    数据结构–判断一个图中是否有环
    bool VCycle(v)
    {
    bool flag;

    visited(v)=-1;//标记起始点

    p=adjacent(v);//即p与v相邻

    WHILE (p !=NULL)
    DO 
    {
    
    	if( visited(vertex(p))==-1) //又回到了起点,所以,存在环
    
    	{
    		flag=ture;
    		return flag;
    	}
    
    	if(visited(vertex(p))==0 )//没被访问过
    
    	{
    		flag=VCycle(vertex(p));//判断该点是否有回路
    		if(flag==ture)
    			return flag;
    	}
    	p=link(p);
    }
    

    visited(v)=1;//被访问过
    flag=false;//该点不成环
    return flag;
    }
    bool Cycle(G)//判断整个图是否有回路

    {
    Let v be the first vertex in G;//此处用英文理解吧

    WHILE v is existed DO (

    	IF visited(v) = 1 
    	THEN CONTINUE
    

    ;
    VCycle(v. flag) ;

    	IF flag=TRUE 
    	THEN RETURN
    

    ;
    Reset the status of visited vertices

    	Let v be the next vertex;)
    

    }

    更多相关内容
  • 判断一个图中是否存在回路,并进行输出(拓扑算法)
  • 5——判断有图中是否存在回路

    万次阅读 多人点赞 2019-06-22 09:32:13
    假设以邻接矩阵作为的结构,编写算法,判别在给定的图中是否存在一个简单的回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)(注意:图中不存在顶点到自身的弧) 这是清华大学的考研试题。...

    假设以邻接矩阵作为图的结构,编写算法,判别在给定的有向图中是否存在一个简单的有向回路,若存在,则以顶点序列的方式输出该回路(找到一条即可)(注意:图中不存在顶点到自身的弧)

    这是清华大学的考研试题。为了判断有向图是否存在环,可以通过深度优先搜索的方法来实现。从编号0的顶点出发,若两个顶点间存在路径,则记录下源顶点标记为已访问(标记为-1)。在遍历的过程中,若有顶点与源顶点相同,则说明存在环。

    code:

    #include <iostream>
    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <conio.h>
    using namespace std;
    const int N = 100;
    int G[N][N];
    int path[N], visited[N], n, cycle;
    int DFS(int u, int start)
    {
    	int i;
    	visited[u] = -1;
    	path[u] = start;
    	for (i = 0; i < n;i++)
    	{
    		if (G[u][i]&&i!=start)
    		{
    			if (visited[i]<0)
    			{
    				cycle = u;
    				return 0;
    
    			}
    			if (!DFS(i,u))
    			{
    				return 0;
    			}
    		}
    	}
    	visited[u] = 1;
    	return 1;
    }
    
    void DisPath(int u)
    {
    	if (u<0)
    	{
    		return;
    	}
    	DisPath(path[u]);
    	cout << " " << u;
    
    }
    
    void main()
    {
    	int i, j;
    	cout << "请输入图中的顶点个数:" << endl;
    	cin >> n;
    	memset(G, 0, sizeof(G));
    	cout << "请输入一个" << n << "*" << n << "矩阵(1表示存在弧,0表示不存在弧):" << endl;
    	for (i = 0; i < n;i++)
    	{
    		for (j = 0; j < n;j++)
    		{
    			cin >> G[i][j];
    		}
    	}
    	cycle = -1;
    	for (i = 0; i < n;i++)
    	{
    		if (!visited[i]&&!DFS(i,-1))
    		{
    			break;
    
    		}
    	}
    	if (cycle<0)
    	{
    		cout << "不存在环!" << endl;
    	} 
    	else
    	{
    		cout << "存在环!" << endl;
    		DisPath(cycle);
    		cout << endl;
    	}
    
    	system("pause");
    }

    结果:

    该算法创建4x4矩阵对应的有向图如下图所示


    其中,a,b,c,d分别对应的编号为0,1,2,3,有向图有5条弧:<a,b> ,<a,c>,<b,c>,<b,d>和<d,a>,因此存在环a->b->d->a

    展开全文
  • 判断有图中回路

    2013-12-24 13:31:55
    数据结构的作业…拓扑排序 判断有图中的环并打印
  • 存储结构:邻接矩阵; 实现功能:深度遍历求回路; 博客的代码实现
  • 根据拓扑排序中是否所有点都入队(可形成拓扑序)来判断是否有回路 ​ ​ #include #include #include #include using namespace std; int main() { queueq; int cnt = 0; vectorindegree(1000,0); //数组记录每个...

     根据拓扑排序中是否所有点都入队(可形成拓扑序)来判断是否有回路

    ​
    ​
    #include<iostream>
    #include<vector>
    #include<algorithm>
    #include<queue>
    using namespace std;
    int main()
    {
        queue<int>q;
        int cnt = 0;
        vector<int>indegree(1000,0);                //数组记录每个点的入度
        vector<int>Adj[1000];                              //邻接表
        int n,m;
        cin >> n>>m;
        for (int i = 0; i < m; i++)
        {
            int u, v;
            cin >> u >> v;
            Adj[u].push_back(v);
            indegree[v]++;                                       //计算每个点的入度
        }
        for (int i =1;i <= n; i++)
        {
            if (indegree[i] == 0)
            {
                q.push(i);                                        //初始化,将所有入度为0的点放入队列
            }
        }
        while (!q.empty())
        {
            int u = q.front();
            for (int j = 0; j < Adj[u].size(); j++)
            {
                indegree[Adj[u][j]]--;                        //将队首指向的点的入度减一
            }
            for (int j = 0; j <Adj[u].size(); j++)
            {
                if (indegree[Adj[u][j]]== 0 )
                {
                    q.push(Adj[u][j]);                                       //更新队列
                }
            }
             q.pop();cnt++;                                        //队首元素弹出,记录个数
        }
        if (cnt < n)cout << "有环";                        //如果所有点均入过队列,则无环,否则有环
        else cout << "无环";
        return 0;
    }
    
    ​
    
    ​

    展开全文
  • 而拓扑排序的作用,就是帮我们判断一个图是否有回路出现。 2. 拓扑排序的思想 其实拓扑排序的思想很简单: (1)在图中选择一个没有前驱(入度为0)的顶点输出; (2)从图中删除该顶点和所有以它为尾的弧;...

    1. 拓扑排序的用处

    对于有向图,我们有时候需要确保没有回路出现,如下面的例子:

    在这里插入图片描述
    学生学习的课程之间的优先关系构成了一个有向图,显然,该有向图不能出现回路,毕竟哪个学生也不想一直循环学习某几门课程不毕业。

    P.s:这种用顶点表示活动,有向边表示活动之间的关系的有向图成为AOV网。

    而拓扑排序的作用,就是帮我们判断一个有向图是否有回路出现。

    2. 拓扑排序的思想

    其实拓扑排序的思想很简单:

    (1)在有向图中选择一个没有前驱(入度为0)的顶点输出;

    (2)从图中删除该顶点和所有以它为尾的弧;

    (3)重复(1)、(2)两步,直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止。

    若所有顶点都被输出,则说明原有向图中没有回路;否则,说明有回路。

    【举例】

    在这里插入图片描述

    3. 代码实现

    代码实现也很简单,首先基于邻接表构造有向图,注意每个顶点结构体中需要加入一项int InDgree 表示该顶点的入度数(因为要把入度为0的顶点删除)。

    我用的是栈来暂时存储删除的顶点,其实用队列或者别的容器都行,只是为了临时存储。

    #include <iostream>
    #include <stack>
    #define MAX_VERTEX_NUM 20
    #define OK 1
    #define ERROR 0
    using namespace std;
    typedef char NumType;
    typedef int Status;
    
    //下面是邻接表构造有向图过程
    struct ArcNode
    {
        int AdjVex;
        ArcNode *NextArc;
    };
    struct VexNode
    {
        NumType data;
        int InDegree;
        ArcNode *FirstArc;
    };
    struct ALGraph
    {
        VexNode Vex[MAX_VERTEX_NUM];
        int VexNum;
        int ArcNum;
    };
    int Locate(ALGraph G,NumType v)
    {
        int i;
        for(i=0;i<G.VexNum;i++)
            if(v==G.Vex[i].data)return i;
        return -1;
    }
    void CreatALGraph(ALGraph &G)
    {
        cout<<"请输入顶点数和弧数:"<<endl;
        cin>>G.VexNum;cin>>G.ArcNum;
        int i;
        cout<<"请输入顶点数据:"<<endl;
        for(i=0;i<G.VexNum;i++)
        {
            cin>>G.Vex[i].data;
            G.Vex[i].FirstArc=0;
            G.Vex[i].InDegree=0;
        }
        NumType v1,v2;
        int j,k;
        cout<<"请输入弧:"<<endl;
        for(k=0;k<G.ArcNum;k++)
        {
            cin>>v1;cin>>v2;
            i=Locate(G,v1);j=Locate(G,v2);
            G.Vex[j].InDegree++;
            ArcNode *p=new ArcNode();
            *p={j,G.Vex[i].FirstArc};
            G.Vex[i].FirstArc=p;
        }
    }
    
    //上面是用邻接表构造有向图
    //下面是拓扑排序代码
    
    void TopoLogicalSort(ALGraph G)
    {
        ArcNode *p=0;
        stack<int> s;
        int i;
        for(i=0;i<G.VexNum;i++)
            if(G.Vex[i].InDegree==0)s.push(i);
        int t;
        int count0=0;
        while(!s.empty())
        {
            count0++;
            t=s.top();
            s.pop();
            cout<<G.Vex[t].data<<" ";
            for(p=G.Vex[t].FirstArc;p!=0;p=p->NextArc)
            {
                G.Vex[p->AdjVex].InDegree--;
                if(!G.Vex[p->AdjVex].InDegree)s.push(p->AdjVex);
            }
        }
    
        if(count0==G.VexNum){cout<<"YES";return;}
        cout<<"NO";
    }
    int main()
    {
        ALGraph G;
        CreatALGraph(G);
        TopoLogicalSort(G);
        return 0;
    }
    
    
    展开全文
  • 算法——判断有图是否有回路

    千次阅读 2020-06-12 19:36:24
    思路: 一.借助AOV的拓扑排序算法来对整个有向进行排序 拓扑排序算法: 1.统计所有节点的入度 2.把所有入度为0的节点入栈 ...否则说明图中有回路 关键代码: int AOV::Topusort_AOV() { stack<int
  • = g.num_vertex)//如果最终计数值和顶点数不相等,说明的顶点入度没有变为0,存在环路 cout存在环路!" int main() { Graph g; create_graph(g); print_graph(g); cout拓扑排序:" topologicalsort(g); ...
  • 判断一个图是否存在回路

    千次阅读 2020-12-13 10:10:45
    loop函数无论是强连通和非强连通均能判断是否存在回路。 在loop函数 1.visited数组用于记录被访问过的节点,和DFS算法的visited数组相同。 2.count数组只有一个元素即count[0],初始值为1,若能找到回路,...
  • DFS判断回路,仅需一个栈保存每一次的路径,然后判断该路径是否存在回路即可,具体看代码即可
  • 2)重复过程1),直到没有入读为0的点,如果还有没被删除的节点,则该一定存在回路 如果G为无向: 1)首先删除所有度数<=1的点,然后将与这些点相连的所有点的度数-1,然后将所有度数为1的点加入队列...
  • 算法——判断无向图是否含有回路

    千次阅读 2020-06-13 16:01:41
    2.根据图论,如果无向弧的个数大于等于节点个数,那么必定存在环 3.把度小于2的点全部删除,并且删除与此节点相关的弧,再统计剩下节点度小于2的点,再把这些点删除,同时删除与此节点相关的弧,直到最后,形成...
  • 我希望通过这篇博客来整理一下判断图中是否有回路的算法,以及相关的源代码(C++)。 判断图中回路 - Andy's Oasis昨天做了CCF 2020年9月CSP认证的第三题,《点亮数字人生》。这道题不难,就是一个简单的记忆化搜索和...
  • 遍历数组indegree[],如果顶点的入度为零,便将顶点依次入队或者入栈 当栈或者队列不为空时,一直重复下面两个操作 1)进行出栈或者出队的操作,这里假设操作顶点为v 2)将与顶点v邻接的所有顶点的入度减一,...
  • 判断无向图中是否有回路

    万次阅读 多人点赞 2014-12-15 17:05:10
     第一种是类似拓扑排序的思路:(参考图判断回路的解答)   如果存在回路,则必存在一个子图,是一个环。因此该子图所有顶点入度>=1。 算法:   在图中,先找出入度为0的顶点,删除与这个顶点...
  • 设快、慢两个指针:fast和slow,在程序开始时,二者都指向单链表的...),两指针进行追赶,若在任何一次循环中两指针指向同一结点,则说明此单链表中有回路;而若二者中任何一个指针指向了NULL(即到达了链表末尾),...
  • ),两指针进行追赶,若在任何一次循环中两指针指向同一结点,则说明此单链表中有回路;而若二者中任何一个指针指向了NULL(即到达了链表末尾),则说明此单链表中没有回路。 /* 判断链表是否有环 */ bool ...
  • 判断给定图是否存在回路。 输入 第一行为图中顶点的个数n; 第二行为途中弧度条数e;第三行为顶点信息;接着e行为e条弧依附的两个顶点。 输出 该图是否存在回路,是输出yes,不是输出no。 样例输入 4 4 A B C...
  • 判断无向图是否有回路

    万次阅读 多人点赞 2014-03-06 00:22:47
    在搜索过程中判断是否会出现后向边(DFS,连接顶点u到它的某一祖先顶点v的边),即在DFS对顶点进行着色过程,若出现所指向的顶点为黑色,则此顶点是一个已经遍历过的顶点(祖先),出现了后向边,若完成DFS后,...
  • //用来标记是否访问过该节点 HashMap visitedMap = new HashMap(); visitedMap.put(a, true ); queue.offer(a); while (!queue.isEmpty()) { UndirectedGraphNode node = queue.poll(); //从队列头部移除 for ...
  • 也适用于回路判断,因为下面算法是基于邻接矩阵的。 总体思路: (1)通过广度遍历(BFS)访问的所有点,对于每个点,都检测和已访问过的点是否有边(除了和它连接的上层节点)。 (1.1)如果边,...
  • 题意:这道题讲的是判断所给图中是否存在一个欧拉回路。知识普及:欧拉通路: 通过图中每条边且只通过一次,并且经过每一顶点的通路。欧拉回路: 通过图中每条边且只通过一次,并且经过每一顶点的回路。无向图是否具有...
  • 判断无向图是否有回路有四种方法

    万次阅读 多人点赞 2014-03-06 10:51:22
    在搜索过程中判断是否会出现后向边(DFS,连接顶点u到它的某一祖先顶点v的边),即在DFS对顶点进行着色过程,若出现所指向的顶点为黑色,则此顶点是一个已经遍历过的顶点(祖先),出现了后向边,若完成DFS后,...
  • 判断给定图是否存在回路。 输入 第一行为图中顶点的个数n; 第二行为途中弧度条数e; 第二行为顶点信息;接着e行为e条弧依附的两个顶点。 输出 该图是否存在回路,是输出yes;,不是输出no。 样例输入 4 4 A B C D...
  • //对每个顶点v都进行一次深搜,如果深搜过程又能走回顶点v,则不在进行搜索,将回路标志flag置为1 #include<stdio.h> int a[6][6]={0}; int flag=0;//回路标记 //a[1][2]=1;a[1][5]=1;a[2][3]=1;a[3][1]=1; ...
  • 1.欧拉回路:定义:经过或无向每条边一次且仅一次并且行遍图中每个顶点的回路( 闭合的欧拉路径,即一个环,保证每条边都通过且仅通过一次)。 2.问题2:判断一个图是否有欧拉路径: (1)G是连通...
  • 1076: 判断给定图是否存在回路 题目描述 判断给定图是否存在回路。 输入 第一行为图中顶点的个数n; 第二行为途中弧度条数e; 第二行为顶点信息;接着e行为e条弧依附的两个顶点。 输出 该图是否存在回路,是...
  • 如何判断一个图中是否存在回路

    千次阅读 2012-10-15 21:21:58
    问题描述:给一个G=,问如何判断这个图中是否存在回路?请给出至少3方法 分析: 方法1:利用减枝的方法,如果G为:  1)首先删除入读为0的点,并且将对应的和该点相连的点的入读-1。(可以用一...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 41,173
精华内容 16,469
关键字:

判断图中是否有回路