CODEWITHSUNDEEP
algorithmdepth-first-searchbreadth-first-searchminimum-spanning-tree
mane
mane

Reputation: 63

Creating a graph based on specific conditions

I have a question that asks me to make a graph such that the BFS and DFS trees from the graph is not a minimum spanning tree and the order of the adjacency list does not matter, I know the properties of BFS DFS and MST but I'm a confused by the question. How should I be approaching the problem? (not looking for the solution)

Upvotes: 2

Views: 239

Answers (2)

Patrick87
Patrick87

Reputation: 28312

Imagine a complete graph on k vertices. For k > 3, a DFS tree will always look different from a BFS tree. For k > 4, you can have a MST that is different from both the BFS and DFS trees. You can choose the shape of the MST to be different from the DFS tree by ensuring one vertex needs three edges coming out of it. You can choose the shape of the MST to be different from the BFS tree by ensuring no vertex has more than three edges coming out of it. You choose the shape of the MST by assigning weights to make the edges you choose, and only those edges, part of the MST.

DFS Tree

1-----2----3
           |
           |
     4-----5

BFS Tree

      1
  ____|____
 /   / \   \
2   3   4   5

MST

2
|
1---3---5
|
4

The complete graph on five vertices has 5 * 4 / 2 = 10 edges, of which only four are needed in any tree.

Upvotes: 1

gilleain
gilleain

Reputation: 641

My suggestion would be to look at an algorithm for finding the MST from a graph, and think about why it is not just a BFS or DFS search.

For any algorithm, finding an edge case that actually tests the tricky parts is an important part of implementation. You could start with a simple example, and try adding new edges or altering the input in a way that would make a simple BFS/DFS search fail.

The condition that it should be independent of the adjacency list order is to ensure that your test graph has a truly hard structure, not just that you have artificially fed the edges to the algorithm in a way that makes it fail.

Upvotes: 0

Related Questions