# 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?

can we use BFS and DFS algorithm in sagemath?

add a comment

1

You can do BFS and DFS as follows:

```
sage: G = graphs.PetersenGraph()
sage: G.plot()
sage: list(G.breadth_first_search(start=3))
[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)))})
```

0

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".

Asked: **
2019-01-09 05:18:58 -0500
**

Seen: **76 times**

Last updated: **Jan 10**

Code stopped compiling out of nowhere for no apparent reason

speed up execution time of script (Cython or other...)

Univariate Polynomial Multiplication

Elliptic curve scalar multiplication algorithm

How to use Sage to find a pair of vertex-disjoint paths of minimal total length?

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.