Python实现图遍历
2022/3/25 17:22:42
本文主要是介绍Python实现图遍历,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Python实现图遍历
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#coding=utf-8 def dfs(G,s): Q=[] S=set() Q.append(s) while Q: u=Q.pop() if u in S: continue S.add(u) Q.extend(G[u]) yield u def createGraph(pairlist): graph = {} keys = set() for index in pairlist: keys.add(index[0]) keys.add(index[1]) for key in keys: graph[key] = set() for index in pairlist: graph[index[0]].add(index[1]) graph[index[1]].add(index[0]) graph[index[0]].add(index[0]) graph[index[1]].add(index[1]) print("顶点的个数为:",len(keys)) return graph def getLinkInfo(graph): #使用集合来存放已访问过的节点 looked = set() #标记序号 i = 0 for keys in list(graph.keys()): #判断该节点是否已经访问(已经归属于某一个链路) if keys in looked: del graph[keys] continue else: result = set(list(dfs(graph, keys))) looked = looked.union(result) i = i + 1 print('--------第'+str(i)+'号-------共'+str(len(result))+'名成员') for keyidvalue in result: print(str(i)+','+keyidvalue) #可以理解为任务依赖圈 data = [('A','B'),('B','G'),('D','E'),('C','C')] pairlist = [] for index in data: pairlist.append(list(index)) graph = createGraph(pairlist) print(graph) getLinkInfo(graph)View Code
这篇关于Python实现图遍历的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-08有遇到过吗?同样的规则 Excel 中 比Python 结果大
- 2024-03-30开始python成长之路
- 2024-03-29python optparse
- 2024-03-29python map 函数
- 2024-03-20invalid format specifier python
- 2024-03-18pool.map python
- 2024-03-18threads in python
- 2024-03-14python Ai 应用开发基础训练,字符串,字典,文件
- 2024-03-13id3 algorithm python
- 2024-03-13sum array elements python