# can we use BFS and DFS algorithm in sagemath?

hello, I want to color the vertices of graphs using greedy or BFS algorithm. can do that in sagemath?

edit retag close merge delete

Sort by ยป oldest newest most voted

You can do BFS and DFS as follows:

sage: G = graphs.PetersenGraph()
sage: G.plot()
[3, 2, 4, 8, 1, 7, 0, 9, 5, 6]
sage: list(G.depth_first_search(start=3))
[3, 8, 6, 9, 7, 5, 0, 4, 1, 2]


What you get is the ordered list of vertices visited in both searches, starting from vertex 3.

Regarding coloring, i am not sure about your exact question. If you want to provide colors to the vertices to show the order of visit, you can try somthing like:

sage: G.plot(vertex_colors={rainbow(40)[i]:[v] for i,v in enumerate(G.breadth_first_search(start=3))})


With more striking example:

sage: G = graphs.Grid2dGraph(10,10)
sage: G.plot()
sage: G.plot(vertex_colors={rainbow(500)[i]:[v] for i,v in enumerate(G.breadth_first_search(start=(0,0)))})
sage: sage: G.plot(vertex_colors={rainbow(500)[i]:[v] for i,v in enumerate(G.depth_first_search(start=(0,0)))})

more

In SageMath, if you define a graph G (for example G = Graph()), then G.coloring? gives the documentation of the coloring method for G, and G.coloring?? gives the source code.

Reading the documentation reveals two choices are offered: using the "dancing link algorithm" or using "mixed linear integer programming".

more