Search in graphs to solve the theorem of euler

Navigation
3

Hello, I would like some help to do a search on a graph and check if it satisfies the euler theorem.

Theorem says: " A connected graph will contain an Euler cycle if, and only if, each of the vertices has an even number of edges falling on it.

Then the problem comes down to finding out the degree of each vertex in my graph, and whether it is connected.

I thought of representing my graph through an adjacency list, because as each vector will have the list of neighbors, just ask for its size minus one and get the degree of the vertex. To find out if it is connected I thought of using a DFS so that I can check as much as possible of each of my neighbors in the graph.

What other ways can I optimize my solution suggestion?

    
asked by anonymous 24.08.2016 / 18:07

1 answer

3

To determine if the graph is connected, the best approach is likely to be either width or depth search. (Reference)

To count the degree of each vertex, you can use adjacency list or adjacency array. Both approaches consume memory intheworstcase.

Todetermineiftwoverticesareneighbors,youhavetogothroughtheadjacencylistofoneofthemandsequentiallysearchfortheothervertexyouwantthere,whichisreasonablyslow.Withadjacencyarray,thiscanbedoneinconstanttime.

Tocomputethedegreeofavertex,eitheryouscrollthroughtheentireadjacencylist,orcountthenumberofelementsintheline.Bothapproacheshavetimeproportionaltoeachvertex,soitwillbe if applied to the entire graph.

For sparse graphs where the number of edges is proportional to the number of vertices (that is,

24.08.2016 / 19:12
DataTables highlight line with higher percentage How to send multiple requests at the same time