ASKSAGE: Sage Q&A Forum - Individual question feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 10 Jan 2019 18:34:48 -0600can we use BFS and DFS algorithm in sagemath?https://ask.sagemath.org/question/44970/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?
Wed, 09 Jan 2019 05:18:58 -0600https://ask.sagemath.org/question/44970/can-we-use-bfs-and-dfs-algorithm-in-sagemath/Answer by tmonteil for <p>hello,
I want to color the vertices of graphs using greedy or BFS algorithm. can do that in sagemath?</p>
https://ask.sagemath.org/question/44970/can-we-use-bfs-and-dfs-algorithm-in-sagemath/?answer=45001#post-id-45001You 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)))})Thu, 10 Jan 2019 18:34:48 -0600https://ask.sagemath.org/question/44970/can-we-use-bfs-and-dfs-algorithm-in-sagemath/?answer=45001#post-id-45001Answer by slelievre for <p>hello,
I want to color the vertices of graphs using greedy or BFS algorithm. can do that in sagemath?</p>
https://ask.sagemath.org/question/44970/can-we-use-bfs-and-dfs-algorithm-in-sagemath/?answer=44992#post-id-44992In 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".
See also [SageMath documentation for graph coloring](http://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_coloring.html).Thu, 10 Jan 2019 12:58:26 -0600https://ask.sagemath.org/question/44970/can-we-use-bfs-and-dfs-algorithm-in-sagemath/?answer=44992#post-id-44992