python判断无向图环是否存在的示例

暂时是一个手动设置无向图中的边，用一个二维数组表示，后面会改进为用户自己定义无向图的边。

学习python的新手，若大佬有解决的办法，希望不吝赐教

#无向图判断环是否存在
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 dfs(n,u)==1:
          return 1
      else:
        return 1
  return 0
global flag,visit,v,g,e,vertex
vertex=[]
flag=0
v=4;e=4#v是顶点，e是边数
#v,e=map(int,input().split())
vertex=[1,2,3,4]#无向图的顶点集合
g=[[0 for i in range(20)]for i in range(20)]
visit=[0 for i in range(20)]
g[1][0]=2;g[2][0]=1;g[2][1]=3;g[3][0]=2;g[3][1]=4;g[4][0]=3;g[1][1]=3;g[3][2]=1
for i in range(1,v+1):
  if visit[i]==0:
    visit[i]=1
    if dfs(i,-1):
      flag=1
      break
if flag==1:
  print('Yes, there is A loop in this network')
else:
  print('No loop')

以上这篇python判断无向图环是否存在的示例就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持我们。

赞 (0)

相关推荐

  • python绘制无向图度分布曲线示例

    如下所示: #Copyright (c)2017, 东北大学软件学院学生 # All rightsreserved #文件名称:a.py # 作 者:孔云 #问题描述:统计图中的每个节点的度,并生成度序列 #问题分析:利用networkx.代码如下: import matplotlib.pyplot as plt #导入科学绘图包 import networkx as nx G=nx.random_graphs.barabasi_albert_graph(1000,3)#生成n=1000,m=3

  • Python根据已知邻接矩阵绘制无向图操作示例

    Python根据已知邻接矩阵绘制无向图操作示例

    本文实例讲述了Python根据已知邻接矩阵绘制无向图操作.分享给大家供大家参考,具体如下: 有六个点:[0,1,2,3,4,5,6],六个点之间的邻接矩阵如表格所示,根据邻接矩阵绘制出相对应的图 0 1 2 3 4 5 6 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 2 0 1 0 1 0 1 0 3 1 1 1 0 1 1 1 4 0 1 0 1 1 1 1 5 1 1 1 1 1 0 0 6 0 1 0 1 1 0 0 将点之间的联系构造成如下矩阵 N = [[0, 3,

  • Python 判断 有向图 是否有环的实例讲解

    实例如下: import numpy from numpy import * def dfs( v ): vis[v] = -1 flag = 0 for i in range(n): # print (a[v][i],'---', vis[i] ) if a[v][i] != 0 and vis[i] != -1: dfs(i) vis[i] = 1 else: pass if a[v][i] != 0 and vis[i] == -1: print ('Yes, there is A loo

  • python判断无向图环是否存在的示例

    暂时是一个手动设置无向图中的边,用一个二维数组表示,后面会改进为用户自己定义无向图的边. 学习python的新手,若大佬有解决的办法,希望不吝赐教 #无向图判断环是否存在 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 dfs(n,u)==1:

  • Python判断变量名是否合法的方法示例

    Python判断变量名是否合法的方法示例

    问题: 变量名是否合法: 1.变量名可以由字母,数字或者下划线组成 2.变量名只能以字母或者下划线开头 s = 'hello@' 判断变量名的第一个元素是否为字母或者下划线 s[0] 如果第一个元素符合条件,判断除了第一个元素之外的其他元素s[1:] 思路: 1.变量名的第一个字符是否为字母或下划线 2.如果是,继续判断 --> 4 3.如果不是,报错 4.依次判断除了第一个字符之外的其他字符 5.判断是否为字母数字或者下划线 while True: s = input('变量名:') #定义退

  • Python判断变量是否为Json格式的字符串示例

    Json介绍 全名JavaScript Object Notation,是一种轻量级的数据交换格式.Json最广泛的应用是作为AJAX中web服务器和客户端的通讯的数据格式.现在也常用于http请求中,所以对json的各种学习,是自然而然的事情. 本文主要介绍的是利用Python判断变量是否为Json格式的字符串,对大家日常学习工作具有一定的参考价值,下面话不多说,直接来看代码吧. 示例代码如下 # -*- coding=utf-8 -*- import json def check_json_

  • Python判断字符串是否xx开始或结尾的示例

    判断是否xx开始 使用startswith 示例代码: String = "12345 上山打老虎" if str(String).startswith('1'): #判断String是否以"虎"结尾 print("有老虎") else: print("没老虎") 执行结果: 有老虎 判断是否xx结尾 使用endswith 示例代码1: String = "12345 上山打老虎" if str(Strin

  • Python判断一个三位数是否为水仙花数的示例

    如下所示: daffodil = int(input('请输入一个三位数:')) if daffodil == pow(daffodil // 100 , 3) + pow(daffodil % 10 , 3) + pow(daffodil // 10 % 10, 3): print("这是一个水仙花数%d" % daffodil) else: print("这不是一个水仙花数%d" % daffodil) 以上这篇Python判断一个三位数是否为水仙花数的示例就是

  • python判断单向链表是否包括环，若包含则计算环入口的节点实例分析

    python判断单向链表是否包括环，若包含则计算环入口的节点实例分析

    本文实例讲述了python判断单向链表是否包括环,若包含则计算环入口的节点.分享给大家供大家参考,具体如下: 关于数据结构相关的面试题,经常会问到链表中是否存在环结构的判断,下图就是存在环结构的链表. 那么如何判断链表中是否存在环呢,下面解法的思路是采用快慢指针: 两个指向头节点的指针,fast和slow,一起从头结点开始往后遍历,fast每次移动两个节点,slow每次移动一个节点, 这样,如果存在环结构,那么fast指针在不断绕环过程中,肯定会追上slow指针. # -*- coding:ut

  • Python判断有效的数独算法示例

    本文实例讲述了Python判断有效的数独算法.分享给大家供大家参考,具体如下: 一.题目 判断一个 9x9 的数独是否有效.只需要根据以下规则,验证已经填入的数字是否有效即可. 1. 数字 1-9 在每一行只能出现一次. 2. 数字 1-9 在每一列只能出现一次. 3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次. 数独部分空格内已填入了数字,空白格用 '.' 表示. 例1: 输入: [ ["5","3",".","

  • 用Python判断奇偶数示例

    用Python判断奇偶数示例

    目录 题目 解法 输出结果 题目 1. 请输入一个整数 , 若该数是偶数 , 输出 “ 是偶数” ” , 若为奇数 ,输出 “ 是奇数” . 2.从键盘输入一个正整数,判断它是否为 3 和 5 的倍数,若是,则输出 yes ,否则是3的倍数反之是5的倍数. 思路: 问题1:首先我们要知道判断是否奇偶数可以用余数来作为判断依据,由题目可知我们所用的变量类型是整形,这样就排除了用余数作为判断依据,然后要知道能被2整除的数为偶数. 问题2:根据题目可以知道输入的这个是一个正整数则变量类型是整形,然后进

随机推荐