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

Commit674844a

Browse files
committed
Code and stuff
1 parent0616fae commit674844a

File tree

5 files changed

+151
-73
lines changed

5 files changed

+151
-73
lines changed
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
# BFS often used to reach portion of graph
2+
# Shortest Path and Minimum Spanning Tree for unweighted graph
3+
# search graph for shortest paths (fastest way to get everywhere, searches layer by layer)
4+
# web crawlers
5+
# solve rubiks cubes
6+
# p2p networks
7+
# social networking (6 degrees etc..)
8+
# network broadcasting
9+
# path finding
10+
# Finding all nodes within one connected component
11+
12+
defbfs(s,Adj):
13+
# s is what can reach in 0 moves
14+
level= {s:0}
15+
parent= {s:None}# stores parent links of visited vertices, is shortest path in reverse. Is length level of v
16+
i=1# just finished level 0
17+
frontier= [s]# what we just reached on previous level (using i - 1 moves)
18+
whilefrontier:
19+
next= []# all things can reach in i moves (next level in graph)
20+
foruinfrontier:# look at every node in frontier
21+
forvinAdj[u]:# and then all nodes you can reach from frontier nodes
22+
ifvnotinlevel:# check for duplicate visits, v would be in level if already visited
23+
level[v]=i# add if not there
24+
parent[v]=u# set parent of this vertex to vertex we came from
25+
print(v)# do stuff at unexplored node
26+
next.append(v)# add to next frontier
27+
frontier=next# done with this frontier, set frontier to next level
28+
i+=1
29+
returnparent
30+
31+
32+
# Adjacency list
33+
graph= {"a" : ["c","d"],
34+
"b" : ["d","e"],
35+
"c" : ["a","e"],
36+
"d" : ["a","b"],
37+
"e" : ["b","c"]
38+
}
39+
40+
printbfs("a",graph)
Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
# DFS often used to reach whole graph
2+
# edge classification, useful for cycle detection and topological sort
3+
# tree edges (parent pointer)
4+
# forward edge: node to descendent
5+
# backward edge: node to ancestor
6+
# cross edge: between two non-ancestor-related subtrees
7+
# job scheduling (topological sort)
8+
# Grapn G has a cycle if G has a backward edge
9+
10+
# visit only vertices reachable from s
11+
parent= {"a":None}
12+
defdfs_visit(s,Adj):
13+
forvinAdj[s]:
14+
ifvnotinparent:
15+
parent[v]=s
16+
print(s)
17+
dfs_visit(v,Adj)
18+
19+
20+
# visit all vertices
21+
defdfs(V,Adj):
22+
parent= {}
23+
forsinV:
24+
ifsnotinparent:
25+
parent[s]=None
26+
dfs_visit(s,Adj)
27+
28+
29+
# Adjacency list representation
30+
graph= {"a" : ["b"],
31+
"b" : ["c"],
32+
"c" : ["e","d"],
33+
"d" : [],
34+
"e" : []
35+
}
36+
37+
printdfs(["a","b"],graph)

‎python_algorithms/algorithms/search/search.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -38,4 +38,4 @@ def binary_search_recursive(data, target, low, high):
3838
returnbinary_search_recursive(data,target,mid+1,high)
3939

4040
printbinary_search_iter(data,5)
41-
printbinary_search_recursive(data,5,0,len(data)-1)
41+
printbinary_search_recursive(data,5,0,len(data)-1)

‎python_algorithms/collections/dictionaries/dict.py‎

Lines changed: 0 additions & 72 deletions
Original file line numberDiff line numberDiff line change
@@ -73,75 +73,3 @@
7373
# a more Pythonic approach.
7474
# dict_data = {i[0]:[*i[1:]] for i in data}
7575
# print(dict_data)
76-
77-
# Graphs
78-
79-
graph= {"a" : ["c"],
80-
"b" : ["c","e"],
81-
"c" : ["a","b","d","e"],
82-
"d" : ["c"],
83-
"e" : ["c","b"],
84-
"f" : []
85-
}
86-
87-
# import dictionary for graph
88-
fromcollectionsimportdefaultdict
89-
90-
# function for adding edge to graph
91-
graph=defaultdict(list)
92-
93-
defaddEdge(graph,u,v):
94-
graph[u].append(v)
95-
96-
defgenerate_edges(graph):
97-
edges= []
98-
99-
# for each node in graph
100-
fornodeingraph:
101-
102-
# for each neighbour node of a single node
103-
forneighbouringraph[node]:
104-
# if edge exists then append
105-
edges.append((node,neighbour))
106-
returnedges
107-
108-
109-
# function to find path
110-
deffind_path(graph,start,end,path=[]):
111-
path=path+ [start]
112-
ifstart==end:
113-
returnpath
114-
fornodeingraph[start]:
115-
ifnodenotinpath:
116-
newpath=find_path(graph,node,end,path)
117-
ifnewpath:
118-
returnnewpath
119-
returnNone
120-
121-
122-
# function to generate all possible paths
123-
deffind_all_paths(graph,start,end,path=[]):
124-
path=path+ [start]
125-
ifstart==end:
126-
return [path]
127-
paths= []
128-
fornodeingraph[start]:
129-
ifnodenotinpath:
130-
newpaths=find_all_paths(graph,node,end,path)
131-
fornewpathinnewpaths:
132-
paths.append(newpath)
133-
returnpaths
134-
135-
# function to find the shortest path
136-
deffind_shortest_path(graph,start,end,path=[]):
137-
path=path+ [start]
138-
ifstart==end:
139-
returnpath
140-
shortest=None
141-
fornodeingraph[start]:
142-
ifnodenotinpath:
143-
newpath=find_shortest_path(graph,node,end,path)
144-
ifnewpath:
145-
ifnotshortestorlen(newpath)<len(shortest):
146-
shortest=newpath
147-
returnshortest

‎python_algorithms/collections/graphs/graph.py‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,3 +13,76 @@ def define_edges(graph):
1313
returnedges
1414

1515
print(define_edges(graph))
16+
17+
18+
# Dict Graphs
19+
20+
graph= {"a" : ["c"],
21+
"b" : ["c","e"],
22+
"c" : ["a","b","d","e"],
23+
"d" : ["c"],
24+
"e" : ["c","b"],
25+
"f" : []
26+
}
27+
28+
# import dictionary for graph
29+
fromcollectionsimportdefaultdict
30+
31+
# function for adding edge to graph
32+
graph=defaultdict(list)
33+
34+
defaddEdge(graph,u,v):
35+
graph[u].append(v)
36+
37+
defgenerate_edges(graph):
38+
edges= []
39+
40+
# for each node in graph
41+
fornodeingraph:
42+
43+
# for each neighbour node of a single node
44+
forneighbouringraph[node]:
45+
# if edge exists then append
46+
edges.append((node,neighbour))
47+
returnedges
48+
49+
50+
# function to find path
51+
deffind_path(graph,start,end,path=[]):
52+
path=path+ [start]
53+
ifstart==end:
54+
returnpath
55+
fornodeingraph[start]:
56+
ifnodenotinpath:
57+
newpath=find_path(graph,node,end,path)
58+
ifnewpath:
59+
returnnewpath
60+
returnNone
61+
62+
63+
# function to generate all possible paths
64+
deffind_all_paths(graph,start,end,path=[]):
65+
path=path+ [start]
66+
ifstart==end:
67+
return [path]
68+
paths= []
69+
fornodeingraph[start]:
70+
ifnodenotinpath:
71+
newpaths=find_all_paths(graph,node,end,path)
72+
fornewpathinnewpaths:
73+
paths.append(newpath)
74+
returnpaths
75+
76+
# function to find the shortest path
77+
deffind_shortest_path(graph,start,end,path=[]):
78+
path=path+ [start]
79+
ifstart==end:
80+
returnpath
81+
shortest=None
82+
fornodeingraph[start]:
83+
ifnodenotinpath:
84+
newpath=find_shortest_path(graph,node,end,path)
85+
ifnewpath:
86+
ifnotshortestorlen(newpath)<len(shortest):
87+
shortest=newpath
88+
returnshortest

0 commit comments

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