Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2f81411

Browse files
author
ssjssh
committed
完成无向图的BFS和拓扑排序
1 parent09dee38 commit2f81411

File tree

4 files changed

+152
-190
lines changed

4 files changed

+152
-190
lines changed

‎src/ssj/graph/__init__.py

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,7 @@
11
#!/usr/bin/env python
22
# -*- coding:UTF-8
33
__author__='shenshijun'
4+
5+
6+
classGraphError(StandardError):
7+
pass

‎src/ssj/graph/digraph.py

Lines changed: 122 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,122 @@
1+
#!/usr/bin/env python
2+
# -*- coding:UTF-8
3+
4+
__author__='shenshijun'
5+
fromssj.lib.queueimportQueue
6+
fromssj.graphimportGraphError
7+
8+
9+
classVertex(object):
10+
def__init__(self,key,weight=None):
11+
"""
12+
adjust_list 表示邻接节点
13+
"""
14+
self.key=key
15+
self.weight_list= []
16+
self.adjust_list= []
17+
self.in_degree=0
18+
self.backup_in_degree=self.in_degree
19+
self.out_degree=0
20+
self.backup_out_degree=self.out_degree
21+
self.dist=0
22+
23+
defadd_adjust(self,to_vertex):
24+
self.adjust_list.append(to_vertex)
25+
self.out_degree+=1
26+
self.backup_out_degree+=1
27+
28+
29+
classDigraph(object):
30+
def__init__(self):
31+
self._vertexes= {}
32+
33+
defadd_vertex(self,key):
34+
"""
35+
Args:
36+
:param key:顶点关键字
37+
Returns:
38+
:rtype: bool
39+
"""
40+
ifkeyinself._vertexes:
41+
returnFalse
42+
else:
43+
self._vertexes[key]=Vertex(key)
44+
returnTrue
45+
46+
defadd_edge(self,from_key,to_key):
47+
# 首先把两个节点查入到图中
48+
self.add_vertex(from_key)
49+
self.add_vertex(to_key)
50+
self._vertexes[from_key].add_adjust(self._vertexes[to_key])
51+
self._vertexes[to_key].in_degree+=1
52+
self._vertexes[to_key].backup_in_degree+=1
53+
54+
deftop_sort(self,func):
55+
zero_in_degree_queue=Queue()
56+
57+
# 首先找到所有入度为0的顶点,遍历从这里开始
58+
forkey,vertexinself._vertexes.iteritems():
59+
vertex.backup_in_degree=vertex.in_degree
60+
ifvertex.in_degreeis0:
61+
zero_in_degree_queue.enter(vertex)
62+
63+
ifzero_in_degree_queue.empty():
64+
raiseGraphError('图中有环,无法执行图的拓扑排序')
65+
66+
result= []
67+
whilenotzero_in_degree_queue.empty():
68+
zero_vertex=zero_in_degree_queue.exit()
69+
result.append(func(zero_vertex.key))
70+
forvertexinzero_vertex.adjust_list:
71+
vertex.in_degree-=1
72+
ifvertex.in_degreeis0:
73+
zero_in_degree_queue.enter(vertex)
74+
75+
# 恢复
76+
forkey,vertexinself._vertexes.iteritems():
77+
vertex.in_degree=vertex.backup_in_degree
78+
returnresult
79+
80+
defbfs(self,key,func):
81+
next_vertex_queue=Queue()
82+
fork,vertexinself._vertexes.iteritems():
83+
vertex.dist=-1
84+
85+
result= []
86+
self._vertexes[key].dist=0
87+
next_vertex_queue.enter(self._vertexes[key])
88+
89+
whilenotnext_vertex_queue.empty():
90+
vertex=next_vertex_queue.exit()
91+
result.append(func(vertex.key,vertex.dist))
92+
foradjust_vertexinvertex.adjust_list:
93+
ifadjust_vertex.distis-1:
94+
adjust_vertex.dist=vertex.dist+1
95+
next_vertex_queue.enter(adjust_vertex)
96+
97+
fork,vertexinself._vertexes.iteritems():
98+
ifvertex.distis-1:
99+
result.extend(self.bfs(vertex.key,func))
100+
returnresult
101+
102+
103+
defmain():
104+
graph=Digraph()
105+
graph.add_edge('v1','v2')
106+
graph.add_edge('v1','v3')
107+
graph.add_edge('v1','v4')
108+
graph.add_edge('v2','v4')
109+
graph.add_edge('v4','v3')
110+
graph.add_edge('v4','v7')
111+
graph.add_edge('v4','v6')
112+
graph.add_edge('v3','v6')
113+
graph.add_edge('v2','v5')
114+
graph.add_edge('v5','v4')
115+
graph.add_edge('v5','v7')
116+
graph.add_edge('v7','v6')
117+
printgraph.top_sort(lambdakey:key)
118+
printgraph.bfs('v1',lambdakey,dist: (key,dist))
119+
120+
121+
if__name__=="__main__":
122+
main()

‎src/ssj/graph/general_graph.py

Lines changed: 0 additions & 189 deletions
This file was deleted.

‎src/ssj/tree/avl_tree.py

Lines changed: 26 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,11 +2,36 @@
22
# -*- coding:UTF-8
33
__author__='shenshijun'
44

5+
"""
6+
定义:
7+
AVL树是高度平衡的二叉搜索树,平衡的方式是每一个节点左右子树高度差顶多为1.
8+
每一个节点中会存储这个节点的高度。节点高度是指从这个节点到叶节点的最大距离。
9+
10+
高度:
11+
AVL树的高度大约是1.44log(N)。
12+
高度为n的AVL树的最小节点数：s(h)=s(h-1)+s(h-2)+1
13+
"""
14+
15+
16+
classNode(object):
17+
""""""
18+
19+
def__init__(self,value,parent,left,right,height=0):
20+
"""Constructor for Node"""
21+
self.value=value
22+
self.height=height
23+
self.parent=parent
24+
self.left=left
25+
self.right=right
26+
527

6-
# TODO 实现
728
classAVLTree(object):
829
""""""
930

1031
def__init__(self):
1132
"""Constructor for """
33+
self.__root=None
34+
self.__size=0
35+
36+
definsert(self,value):
1237
pass

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp