精华内容
下载资源
问答
  • 判断无向图是否有环
    2021-03-15 17:35:25

    //深度优先遍历图,当某个节点的子节点已经访问过,且该节点不是其父节点,肯定存在环

    #include

    #include

    #include

    using namespace std;

    bool dfs(vector >&graph, vector&visited,int father,int &son,const int start)

    {

    visited[son] = true;

    for (int i = 0; i < graph.size(); i++)

    {

    //-1代表没有边相连接

    if (graph[son][i] != -1 && graph[son][i]!=0 && ((father==-1 && i!=start) || father!=-1 && i!=father) && visited[i] == true) return true;

    else if (graph[son][i] != -1 && i != son && visited[i] == false)

    {

    if (dfs(graph, visited,son,i,start)) return true;

    }

    }

    return false;

    }

    int main(void)

    {

    int vexNum;

    cin >> vexNum;

    vector>graph(vexNum, vector(vexNum, 0));

    int temp;

    for (int i = 0; i < vexNum; i++)

    {

    for (int j = 0; j < vexNum; j++)

    {

    cin >> temp;

    graph[i][j] = temp;

    }

    }

    for (int i=0;i<=vexNum-1;i++)

    {

    graph[i][i] = 0;  //节点到自己的距离为0

    }

    //单从一个节点开始访问,不能保证所有节点都能访问到,需考虑以每个节点为起始点

    for (int i = 0; i < vexNum; i++)

    {

    vector visited(vexNum, false);  //存放节点是否访问,每次都重新初始化

    if (dfs(graph, visited, -1,i,i)) { cout << "Yes" << endl; system("pause"); return 0; }

    }

    cout << "No" << endl;

    system("pause");

    return 0;

    }

    转载至链接:https://my.oschina.net/u/3397950/blog/1936209

    更多相关内容
  • * @Description:判断无向图是否有环 深度优先遍历 * 需要保存父节点 * @Create 2020-04-03 21:04 * @Email:1173748742@qq.com */ public class IsHaveLoop { public static void main(String[] args) { ...
  • 使用并查集:如果找到两个节点的头节点一个的时候,就判断有环。 剑指 Offer II 118. 多余的边 树可以看成是一个连通且 无环 的 无向 。 给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的。添加的边的两...

    使用并查集:如果找到两个节点的头节点一个的时候,就判断有环。

    剑指 Offer II 118. 多余的边

    树可以看成是一个连通且 无环 的 无向 图。
    给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

    请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的边。

    示例 1:
    输入: edges = [[1,2], [1,3], [2,3]]
    输出: [2,3]

    示例 2:
    输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
    输出: [1,4]

    提示:
    n == edges.length
    3 <= n <= 1000
    edges[i].length == 2
    1 <= ai < bi <= edges.length
    ai != bi
    edges 中无重复元素
    给定的图是连通的

    class Solution {
        public int[] findRedundantConnection(int[][] edges) {
            int n = edges.length;
            int[] parent = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
            for (int[] edge : edges) {
                int node1 = edge[0], node2 = edge[1];
                if (find(node1, parent) != find(node2, parent)) {
                    union(node1, node2, parent);
                } else {
                    return edge;//题目中只含有一个环,所以找到环的时候就是最右边的边了,直接返回就可以了
                }
            }
            return new int[0];
        }
    
        public static int find(int i, int[] parent) {
            while (parent[i] != i) {
                i = parent[i];
            }
            return i;
        }
    
        public static void union(int x, int y, int[] parent) {
            int fx = find(x, parent);
            int fy = find(y, parent);
            if (fy != fx) {
                parent[fx] = fy;
            }
        }
    }
    
    展开全文
  • 思路:根据无向图的邻接矩阵遍历图中每一条边,因为是无向图,所以只用遍历上三角矩阵,遍历到顶点为i,j的边时,若顶点i,j的根节点a,b相同,则说明两个顶点在一个集合,一个集合中的顶点相连的边说明有环;...

    二维数组map是邻接矩阵,一位数组pre记录各个顶点的根节点
    思路:根据无向图的邻接矩阵遍历图中每一条边,因为是无向图,所以只用遍历上三角矩阵,遍历到顶点为i,j的边时,若顶点i,j的根节点a,b相同,则说明两个顶点在一个集合,一个集合中的顶点有相连的边说明有环;若不在一个集合,则将两个集合合并

    #include<iostream>
    using namespace std;
    
    int find(int x, int pre[]){
        // 返回根节点,并进行压缩路径
        int p=x, temp;
        while(x!=pre[x]){
            pre[x] = pre[pre[x]];
            x=pre[x];
        }
        return x;
    }
    
    int hasHuan(int map[5][5]){
        // 用并查集判断无向图是否有环
        int pre[5];
        for(int i=0; i<5; i++){
            pre[i] = i;
        }
        for(int i=0; i<5; i++){
            for(int j=i+1; j<5; j++){
                if(map[i][j] == 1){
                    // 遍历到顶点为i,j的边时,若顶点i,j的根节点a,b相同,
                    //则说明在一个集合,一个集合中的顶点有相连的边说明有环
                    int a = find(i, pre);
                    int b = find(j, pre);
                    if(a!=b){
                        pre[a] = b;
                    }else{
                        return 1; // 有环
                    }
                }
            }
        }
        return 0; // 无环
    }
    
    int main() {
        int map1[5][5] = 
                    {{0,1,1,0,0},
                    {1,0,1,1,1},
                    {1,1,0,0,0},
                    {0,1,0,0,0},
                    {0,1,0,0,0}};
    
        int map2[5][5] = 
                    {{0,1,1,0,0},
                    {1,0,0,1,1},
                    {1,0,0,0,0},
                    {0,1,0,0,0},
                    {0,1,0,0,0}};
        cout<<hasHuan(map1)<<endl; // 输出 1
        cout<<hasHuan(map2)<<endl; // 输出 0
    }
    
    展开全文
  • 无向图中,给定一些边,然后判断这些边组成的图是否有环。注意这个方法必须保证没有输入重边 对于一条边用(a, b)表示,然后把a,b加入到并查集中。如果又加入了一条边(b ,c) ,那么如果这个时候又需要加入一条边(c,...

    无向图中,给定一些边,然后判断这些边组成的图是否有环。注意这个方法必须保证没有输入重边

    对于一条边用(a, b)表示,然后把a,b加入到并查集中。如果又加入了一条边(b ,c) ,那么如果这个时候又需要加入一条边(c, a)就会被判定为有环(a, b, c形成了环)。

    并查集中,可以得到a,c在同一个集合中。就可以判断,有没有形成环。

    模板题

    题意:

    判断一个无向图是不是存在环,输入包含多组数据,每组数据是一个以0 0结尾的整数对列表,表示了一条通道连接的两个点的编号。点的编号至少为1,且不超过100000。每两组数据之间有一个空行。
    整个文件以两个-1结尾。

    这个输入有点奇怪,没有确定的边的输入个数。但是又边界条件。

    代码:

    #pragma warning(disable:4996)
    #include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<string>
    #include<map>
    #include<stack>
    #include<algorithm>
    #include<vector>
    #include<queue>
    #include<set>
    using namespace std;
    const int maxn = 100005;
    int a, b, fa[maxn], flag;
    int find(int x) {
    	if (x == fa[x])return x;
    	return find(fa[x]);
    }
    void uni(int x, int y) {
    	int fx, fy;
    	fx = find(x); fy = find(y);
    	if (fx != fy)
    	{
    		fa[fx] = fy;
    	}
    	else flag = 1;//如果想等的话,就说明有环。
    }
    int main()
    {
    	while (scanf("%d%d", &a, &b) == 2)
    	{
    		if (a == -1 && b == -1)break;
    		flag = false;
    		set<int>st;
    		st.clear();
    		st.insert(a); st.insert(b);//加入最初的边
    		if (a == 0 && b == 0)//边集为空
    		{
    			printf("Yes\n");
    			continue;
    		}
    		for (int i = 1; i < maxn; i++)
    		{
    			fa[i] = i;
    		}
    		int sume = 1;//边的数量为1了
    		uni(a, b);//加入这两个点
    		while (1)
    		{
    			scanf("%d%d", &a, &b);//输入后面的边
    			if (a == 0 && b == 0)break;
    			st.insert(a); st.insert(b);
    			if (!flag)
    			{
    				uni(a, b);
    			}
    			sume++;
    		}
    		if (!flag && st.size() == (sume + 1))
    			printf("Yes\n");
    		else printf("No\n");
    	}
    	return 0;
    }

     

     

    展开全文
  • #无向图判断环是否存在 def dfs(u,fa): for i in range(v): n=g[u][i]#n为图中的顶点数 # print(u,n,fa,i,'') if n in vertex:#判断n是否属于图的顶点 if n==fa: continue if visit[n]==0: visit[n]=1 if ...
  • 判断无向图/向图中是否存在

    千次阅读 2019-02-03 11:54:50
    本文主要针对如何判断向图/无向图中是否存在的问题进行简单...首先,利用DFS判断无向图是否换的原理是:若在深度优先搜索的过程中遇到回边(即指向已经访问过的顶点的边),则必定存在。 所以说,是否存在...
  • 判断无向图是否有环

    千次阅读 2016-05-14 10:46:05
    无向图: 1 并查集   首先我们把每个点看成独立的集合{0} ,{1}, {2}, 然后规定如果两个点之间边相连,如果这两个点不属于同一个集合,那就将他们所属的结合合并,看边0-1,直接将这两个点代表的集合合并{0, ...
  • 今天小编就为大家分享一篇关于判断一个无向图是否为连通图的方法,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
  • 判断无向图是否存在

    千次阅读 2021-05-09 21:58:41
    判断无向图是否存在 并查集 遍历所有边,对于遍历到边的两个端点,如果本身已经连通(在此前遍历到,并属于一个祖先),则说明存在一个。 利用树的性质 对于无向图来说,如果边数为点数-1则一定能重构为树形,...
  • 有向图不能用这个 */ function dfs ( v , G ) { var marked = [ ] //from[v]=v for ( let i = 0 ; i < V ; i ++ ) { marked [ i ] = false } dfs_ ( v , G , marked , v ) } function...
  • 使用并查集的方法判断无向图是否存在。class UnionFind{private $parent = [];public function __construct($n){for ($i = 0; $i < $n; $i++) {$this->parent[$i] = $i;}}public function find($x){while ...
  • 判断给定的图是不是有向无环图,方法是应用拓扑排序,代码如下
  • = father[node]/*无向图如果i是node的父节点则不是*/) //找到一个 { int tmp = node; cout; while(tmp != i) { cout<<tmp<<"->"; tmp = father[tmp]; } cout; } else if(visit[i] == 0)//未遍历过 { father[i] =...
  • 判断有向图是否有环

    千次阅读 2021-03-15 02:40:32
    方法一:拓扑排序时间复杂度O(n^2)比较常用的是用拓扑排序来判断有向图是否存在。什么是拓扑排序呢?我们先定义一条u到v的边e=,u生成拓扑序列的算法就叫拓扑排序啦~算法流程描述while(节点个数次(N)循环)1.找出...
  • *利用并查集判断无向图是否有环 */ public class Solution { public int[] parent;//记录并查集元素父节点 public int depth[];//记录并查集每个元素的深度 //初始化操作 public Solution(int nums) { ...
  • 第一次写博客,不太会用,话不多说 直接上代码 详细可以看注释,... * @Description:判断无向图是否有环 深度优先遍历 * 需要保存父节点 * @Create 2020-04-03 21:04 * @Email:1173748742@qq.com */ public clas...
  • //并查集判断无向图是否存在环路+树的直径 //树的直径是指树的最长简单路,使用两次bfs:先任选一个起点bfs找到最长路的终点,再从终点进行bfs,则第二次bfs找到的最长路即为树的直径 #include &lt;iostream&...
  • 没有找到原文出处,请参考一下链接:一、无向图:方法1:如果存在回路,则必存在一个子图,是一个环路。环路中所有顶点的度>=2。n算法:第一步:删除所有度<=1的顶点及相关的边,并将另外与这些边相关的其它...
  • 一、判断给定的“无向图是不是”无图“ 首先在这里我们假设不存在自与平行边)。同时定义边数为m,顶点为n;,且分为两种情况讨论。 m>n时,则无向图有环 m<n时, 第一步:删除所有度<=1的顶点及相关...
  • 1:判断无向图是否有环: 如果图g有环,用dfs遍历图g,会访问到已经访问过的顶点。 2:判断无向图是否为二分图:利用gfs遍历图给图上色(2种颜色),然后判断上色顶点间是否冲突。若冲突,则为非二分图。 package...
  • 判断图中是否存在无向图5分,向图10分 给出顶点u和v,判断u到v是否存在路径(5分) 10、求顶点u到v的一条简单路径(10分) 11、求顶点u到v的所有简单路径(15分) 12、求顶点u到v的最短路径(10分) 13、求...
  • 文章目录一、无向图 Detect Cycle in a Undirected Graph1. DFS(1) 判断环的存在(2) 输出环路2. BFS(1) 判断环的存在3. Union-Find(1) 原理讲解(2) 代码实现二、向图 Detect Cycle in a Directed Graph1. Detect ...
  • 给定一个nn个点mm条边的无向图。 点的编号从11到nn。 图中不含重边和自。 请你对给定图进行判断,如果该图是一个且仅一个的连通图,则输出YES,否则输出NO。 输入格式 第一行包含两个整数n,mn,m。 接...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 56,990
精华内容 22,796
关键字:

判断无向图是否有环

友情链接: SymbianC++.rar