Give an algorithm to check whether a given undirected graph has cycles of odd length. The length of a cycle is the number of vertices (or equivalently, the number of edges) in the cycle.

Question

Use Breadth First Search (BFS).

Answer 1

Not exactly an *expert* answer, but this is the first thing that comes to mind.

First, some things to keep in mind:

1. As an *undirected* graph, any node B that node A can reach can also reach node A. This means that we have to remember that we've seen node A.
2. BFS allows us to order the nodes of a graph into 'layers', wherein each layer is connected to the next by a single edge, so
3. if we ensure that each node 'retained' in the BFS is unique, and
4. we remember which level with (first) saw the node, then
5. we can use the difference in 'layer' between the first and any other time we see a node to identify the number of edges of a span or cycle.

So:

1. Create an empty map of node to cardinal, node-to-level, and an empty queue of nodes, next-nodes. (We'll use node-to-level to both keep track of whether we've seen a node already, and at what level we first saw it. We use next-nodes to implement BFS.)
2. Push any node, n, from the graph onto next-nodes, and record its [current] level, node-to-level[current-node] = 0.
3. While next-nodes is not empty, pop current-node from the queue:
4. Set current-level = node-to-level[current-node].
5. For each node, connected-node, reachable from current-node:
6. If connected-node is already in node-to-level, then we have identified a cycle.
7. The length of the cycle is length = current-level - node-to-level[connected-node].
8. If length is odd, report it.
9. Otherwise;
10. remember connected-node's level, node-to-level[connected-node] = current-level + 1, and
11. push connected-node onto next-nodes.