def afs(g, s): bag = data_structure() bag.add(s) while bag is not empty: tile = bag.pop() if tile is not marked: mark(tile) for x in adj_list(tile): bag.add(x)
Depends what is plugged as a data_structure, we have dfs, bfs, or Minimum Spanning Tree algorithm, with some modification, of course. For example using data structure LIFO stack we have Depth First Search:
def dfs(g, v): if v is not marked: mark(v) for w in adj_list(v): dfs(g, w)
FIFO stack gave as Breadth First Search, etc..
Amount of problems which can be solved using graphs is huge, we even say: "If you have problem and can make graph from it, do it and problem solved":). Code as usually on github. Thats all, thank you, enjoy!
No comments:
Post a Comment