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 loop in this network\n')
  global swi
  swi = True
  exit()
  return
  # break
 else:
  pass
 print ('s = 0')
 return False

global swi
swi = False
'''===装载数据'''
edges = numpy.loadtxt('9_nodes_with_r_edge_8_to_3.txt')

# edges = [ int(i) for i in edges]
bian = int(shape(edges)[0]) - 1
print (bian,'edges in the network \n')
print (shape(edges),'\n')

n = int( edges[0][1] )

c = int( edges[0][0] )
# n, c = input().split()
# n = int(n)
# c = int(c)
a = [([0] * n) for i in range(n)]
vis = [0] * c
for i in range(1, c+1):
 s, t = edges[i][0:2]
 # print (s,' - ', t )
 '''GO_OBO文件则 s, t 不需要 -1 '''
 s = int(s) - 1
 t = int(t) - 1
 # s = int(s)
 # t = int(t)
 a[s][t] = 1
# print (a)
# print (vis)
dfs(0)
# print (swi)
if not swi:
 print('No loop, DAG - DAG - DAG')

用到 numpy 模块，读取的 txt 文件为 有向图的连边，其中第一行 第一个数字 为 边的数量，第二个数字为 节点数 第二行及以后 前两个数字，第一个为 起点， 第二个为 落点。

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

您可能感兴趣的文章:

  • Python算法之图的遍历
赞 (0)

相关推荐

  • Python算法之图的遍历

    Python算法之图的遍历

    本节主要介绍图的遍历算法BFS和DFS,以及寻找图的(强)连通分量的算法 Traversal就是遍历,主要是对图的遍历,也就是遍历图中的每个节点.对一个节点的遍历有两个阶段,首先是发现(discover),然后是访问(visit).遍历的重要性自然不必说,图中有几个算法和遍历没有关系?! [算法导论对于发现和访问区别的非常明显,对图的算法讲解地特别好,在遍历节点的时候给节点标注它的发现节点时间d[v]和结束访问时间f[v],然后由这些时间的一些规律得到了不少实用的定理,本节后面介绍了部分内容,感

  • 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判断链表是否有环的实例代码

    先看下实例代码: class Node: def __init__(self,value=None): self.value = value self.next = None class LinkList: def __init__(self,head = None): self.head = head def get_head_node(self): """ 获取头部节点 """ return self.head def append(self

  • Python判断中文字符串是否相等的实例

    Python判断两个相等的中文字符串为false,将两个待比较的字符串都把unicode编码设为'utf-8'也不能解决问题,具体原因如下: 1.首先查看待比较两个字符串的编码格式 ,使用命令 import chardet ...... string_code = chardet.detect(string_word) 比较两个字符串的编码结果,如下图所示 一个编码格式为'UTF-8-SIG',另一个编码格式为'utf-8',两个字符串的编码格式不同,所以比较的结果为不相等 出现编码为'UTF-

  • 对python判断是否回文数的实例详解

    设n是一任意自然数.若将n的各位数字反向排列所得自然数n1与n相等,则称n为一回文数.例如,若n=1234321,则称n为一回文数:但若n=1234567,则n不是回文数. 上面的解释就是说回文数和逆序后的结果是相等的.这就是判断一个数值是否是回文数的标准. 代码也是根据这个思路来实现的. # -*- coding: utf-8 -*- """ Created on Sun Aug 5 09:01:38 2018 @author: FanXiaoLei ""

  • 对python判断ip是否可达的实例详解

    python中使用subprocess来使用shell 关于threading的用法 from __future__ import print_function import subprocess import threading def is_reachable(ip): if subprocess.call(["ping", "-c", "2", ip])==0:#只发送两个ECHO_REQUEST包 print("{0} is a

  • python判断集合的超集方法及实例

    1.说明 可以使用 >= 运算符判断当前集合是否为另一个集合的超集,即判断集合 b 中的所有元素是否都包含在集合 a 中. 2.语法 set_a >= set_b # 相当于set_a.issuperset(set_b) 3.参数 set_a:集合 a. set_b:集合 b. 4.返回值 返回布尔值,如果集合 b 中的所有元素都包含在集合 a 中,则返回 True,否则返回 False. 5.实例 # 创建集合 a = {'赵', '钱', '孙', '李'} b = {'赵', '孙',

  • python中判断数字是否为质数的实例讲解

    在计算机程序中,算法是灵魂,是程序的精髓所在.程序执行效率的高低直接取决于算法的优劣,所以计算机算法是计算机课程必修课.算法可以快速计算出我们所需要的结果,例如判断质数,这是很基础的内容,具体如何操作呢?下面小编向大家演示在python如何判断数字是否为质数. 质数:一个大于1的自然数,除了1和它本身外,不能被其他自然数(质数)整除(2, 3, 5, 7等),换句话说就是该数除了1和它本身以外不再有其他的因数. 判断代码: def isprime(a): if isinstance(a,int)

  • python递归打印某个目录的内容(实例讲解)

    以下函数列出某个目录下(包括子目录)所有文件,本随笔重点不在于递归函数的实现,这是一个很简单的递归,重点在于熟悉Python 库os以及os.path一些函数的功能和用法. 1. os.listdir(path): 列出path下所有内容(包括文件和目录,不包括.和..) 2. os.path.join(path1,path2,path3...): 拼接目录,例如将'home','test'拼接成'home/test/' 3. os.path.isdir(path): 判断path是否为目录 代

  • Python简单爬虫导出CSV文件的实例讲解

    流程:模拟登录→获取Html页面→正则解析所有符合条件的行→逐一将符合条件的行的所有列存入到CSVData[]临时变量中→写入到CSV文件中 核心代码: ####写入Csv文件中 with open(self.CsvFileName, 'wb') as csvfile: spamwriter = csv.writer(csvfile, dialect='excel') #设置标题 spamwriter.writerow(["游戏账号","用户类型","游戏

  • Python字典实现简单的三级菜单(实例讲解)

    如下所示: data = { "北京":{ "昌平":{"沙河":["oldboy","test"],"天通苑":["链接地产","我爱我家"]}, "朝阳":{"望京":["奔驰","陌陌"],"国贸":["CICC",&quo

随机推荐