A* algorithm to check if the graph k3 free

Question

I'm wondering if I can use A* algorithm to check if the graph is K3 free?? if yes how can I do that? How can I deal with f, g , and h functions. if no what is the best algorithm to use except DFS and BFS.

Thanks

BFS. If there is K3 in graph, at least one edge will point to the vertice at the same level. — user482594
– user482594, Commented Mar 5, 2012 at 7:19

foobar · Accepted Answer · 2012-03-05 13:04:46Z

2

A* is not an appropriate tool for this problem. Iterate through the edges in the graph and check whether their endpoints have a neighbor in common. user482594's BFS solution fails to detect K3s consisting of vertices at equal depth in the BFS tree.

answered Mar 5, 2012 at 13:04

foobar

862 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Python Over a year ago

Thanks for your answer. So which algorithm you suggest to solve this problem?

Collectives™ on Stack Overflow

A* algorithm to check if the graph k3 free

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related