Thursday 17 August 2017

New Repository: Python Graphs!

I have a new repo on my github: Python-Graphs. There are just few very basic graph algorithms; in fact variations of one, say, Any First Search.

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: