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

Please start posting anonymously - your entry will be published after you log in or create a new account.

Asked: ** 2019-01-09 12:18:58 +0200 **

Seen: **281 times**

Last updated: **Jan 11 '19**

Univariate Polynomial Multiplication

Sympy integration algorithm towards -infinity

Rational reconstruction in ring of integers

Number of line segments in a group - algorithm

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

Line segments instersection 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.