Efficient algorithm to find weights of all cycles in an undirected weighted graph

Question

My aim is to find all the cycles and their respective weights in an weighted undirected graph. The weight of a cycle is defined as sum of the weights of the paths that constitute the cycle. My preset algorithm does the following:

dfs(int start, int now,int val)
{
     if(visited[now])
        return;
     if(now==start)
     {
        v.push_back(val);// v is the vector of all weights
        return;
     }
     dfs through all nodes neighbouring to now;
 }

I call dfs() from each start point:

for(int i=0;i<V;++i)
{
    initialise visited[];
    for(int j=0;j<adj[i].size();++j)//  adj is the adjacency matrix
        dfs(i,adj[i][j].first,adj[i][j].second); 
//  adj is a vector of vector of pairs
// The first element of the pair is the neighbour index and the second element is the weight
}

So the overall complexity of this algorithm is O(V*E)(I think so). Can anyone suggest a better approach?

in the particular case when the graph is complete, any sequence of nodes constitutes a cycle. Thus (if I correctly understood the requirements), it seems impossible for a good algorithm to not require exponential complexity in the worst case scenario. — danbanica, Sep 02 '17 at 12:22
As queryman said, there can be an exponential amount of cycles. Do you really need each single weight (then there is no other way than up exponential many results too), or maybe just min, max or something like that? — deviantfan, Sep 02 '17 at 12:50
Take a look here https://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs — algrid, Sep 02 '17 at 14:02
@deviantfan To be precise I require to know whether any weight is an odd number. But does it not require to calculate all the weights? (weight == weight of a cycle) — yobro97, Sep 03 '17 at 02:47
@yobro97 No, it doesn't require that. I'm writing an answer... — deviantfan, Sep 03 '17 at 07:03

deviantfan · Accepted Answer · 2017-09-03T10:36:49.540

Since not everyone defines it the same way, I assume...

the weigths are on the edges, not vertices
the only vertex in a cycle that is visited more than one time is the start/end vertex
a single vertex, or two connected vertices, are no cycle, ie. it needs at least three vertices
between two vertices in your graph, there can't be more than one edge (no "multigraph")

Following steps can determine if (at least) one odd-weighted cycle exists:

Remove all vertices that have only 0 or 1 connected edges (not really necessary, but it might be faster with it).
Split every even-weighted edge (only them, not the odd-weighted ones!) by inserting a new vertex. Eg. if the egde between vertex A and B has weight 4, it should become A-Z 2 and Z-B 2, or A-Z 3 and Z-B 1, or something like that.
- The actual weight distribution is not important, you don't even need to save it. Because, starting after this step, all weights are not necessary anymore.
- What did this actually do? Think like every odd weight is 1, and every even one is 2. (This doesn't change if there is a odd-weighted cycle: If 3+4+8 is odd then 1+2+2 is too). Now you're splitting all 2 into two 1. Since now the only existing weight is 1, determining if the sum is odd is the same as determining if the edge "count" is odd.
Now, for checking bipartiteness / 2coloring:
- You can use a modified DFS here
- A vertex can be unknown, 0, or 1. When starting, assign 0 to a single vertex, all others are unknown. The unknown neighbors of a 0-vertex always get 1, and the ones of a 1-vertex always get 0.
- While checking neighbors of a vertex if they were already visited, check too if the number is different from the vertex you're processing now. If not, you just found out that your graph has odd-weigthed cycles and you can stop everything.
- If you reach then end of DFS without finding that, there are no odd-weighted cycles.
- For the implementation, note that you could reach the "end" of DFS while there are still unvisited vertices, namely if you have a disconnected graph. If so, you'll need to set one of the remaining vertices to a known number (0) and continue DFS from there on.

Complexity O(V + E) (this time really, instead of a exponential thing or not-working solutions).

Efficient algorithm to find weights of all cycles in an undirected weighted graph

1 Answers1