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

yipeiwu_com5年前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设计】。

相关文章

CentOS 7下Python 2.7升级至Python3.6.1的实战教程

CentOS 7下Python 2.7升级至Python3.6.1的实战教程

前言 大家应该都知道,Centos是目前最为流行的Linux服务器系统,其默认的Python 2.x,但是根据python社区的规划,在不久之后,整个社区将向Python3迁移,且将不在...

Python3从零开始搭建一个语音对话机器人的实现

Python3从零开始搭建一个语音对话机器人的实现

01-初心缘由 最近在研究语音识别方向,看了很多的语音识别的资料和文章,了解了一下语音识别的前世今生,其中包含了很多算法的演变,目前来说最流行的语音识别算法主要是依赖于深度学习的神经网络...

Python编程深度学习计算库之numpy

Python编程深度学习计算库之numpy

NumPy是python下的计算库,被非常广泛地应用,尤其是近来的深度学习的推广。在这篇文章中,将会介绍使用numpy进行一些最为基础的计算。 NumPy vs SciPy NumPy和...

解决Pycharm中import时无法识别自己写的程序方法

我们用pycharm打开自己写的代码,当多个文件之间有相互依赖的关系的时候,import无法识别自己写的文件,但是我们写的文件又确实在同一个文件夹中, 这种问题可以用下面的方法解决: 1...

Pytorch 实现自定义参数层的例子

注意,一般官方接口都带有可导功能,如果你实现的层不具有可导功能,就需要自己实现梯度的反向传递。 官方Linear层: class Linear(Module): def __in...