s***i
发帖数: 49 | 1 How can I give algorithm that checks whether a graph is bipartite (a graph
whose nodes can be divided into two sets N1 and N2, and every edge is
between a member of N1 and N2)?
And since non-bipartite means there must be a cycle of odd length, how can I
check bipartite, and if false, prints a cycle of odd length?
Thanks in advance. | v********e
发帖数: 1058 | 2 BFS
I
【在 s***i 的大作中提到】
: How can I give algorithm that checks whether a graph is bipartite (a graph
: whose nodes can be divided into two sets N1 and N2, and every edge is
: between a member of N1 and N2)?
: And since non-bipartite means there must be a cycle of odd length, how can I
: check bipartite, and if false, prints a cycle of odd length?
: Thanks in advance.
| y*******f
发帖数: 26 | 3
Breadth first search
I
Record the parent of each node visited.
【在 s***i 的大作中提到】
: How can I give algorithm that checks whether a graph is bipartite (a graph
: whose nodes can be divided into two sets N1 and N2, and every edge is
: between a member of N1 and N2)?
: And since non-bipartite means there must be a cycle of odd length, how can I
: check bipartite, and if false, prints a cycle of odd length?
: Thanks in advance.
| s***i
发帖数: 49 | 4 Thanks. Can you give me some pseudo-code? |
|
