Undirected (Multi) Graph (Hierholzers Algorithm)

I am very stuck with the looping structure for my graph to work out Eulers tour.

This is the graph I am drawing, remember it's undirected, so a journey from N1 to N4 is the same as a journey from N4 to N1 (don't mean to be patronizing just trying to increase my chances of help).

The way to solve this problem is to find a collection of closed tours. Then if every line has been used and we have found a set of closed tours then the Euler tour has been found.

This is an image开发者_StackOverflow社区 of the graph I am working with along with the 2d array representation

http://i306.photobucket.com/albums/nn269/MCTWEED15/Untitled-5.png

As you can see next to my lovely image, there is a 2d array of int's representing the edges between vertices. My problem is creating a loop that, when run, will go to any vertex and end back at the start point (for a closed tour). There must be a mathematical, logical way of doing this.

I need to, loop through a line i guess. If the position in matrix [column][row] > 0 (ie there is a link) then matrix[row][column]-- to take one link away but i am still unsure how this will serve me in collecting links for the closed tour

I am really sorry for the explanation. I have tried to explain my problem the best I can, if you need any more information to try and help then please let me know

thanks

---

• Check your vocabulary vertex (plural: vertices/vertexes) are what you also refer to as nodes. The connections between vertices are called edges. You mixed that up in your description of the array.
• Your 2d array is called "adjacency matrix" and strictly speaking the one in your image isn't a valid one as several values are missing
• Before trying to calculate the Euler tour you could do some sanity checks

Sanity check

1. Check if all vertices have an even degree
2. Check if the graph is connected

If one of those two checks fails your graph can't contain an Euler tour. Else if both checks pass your graph is Eulerian.

For example the graph provided by you can't contain an Euler tour as N2 and N4 have an uneven degree.. Your image differs from the provided adjacency matrix (overlooked that). The graph provided based on the adjacency matrix contains a euler tour.

Else follow this recipe:

Be G=(V,E) your graph which is connected and only contains vertices with even degree

1. Choose some arbitrary vertex x from G
2. Create a valid Euler tour K1 starting from x in G (uses just subset of all edges E)
3. Delete all edges used by K1
4. Choose a vertex y from K1 which still has a degree > 0
5. Construct another Euler tour Kn starting from y from the remaining subset of edges in E
6. Repeat until edges are used
7. Now you get your Euler tour by starting with the first "sub"-Euler tour K1 you found and including the other "sub"-Euler tours found on the corresponding intersections

e.g. given this adjacency matrix representing G we find on Euler tour (with name H)

   V1 V2 V3 V4 V5
V1  0  0  2  0  0
V2  0  0  1  1  2
V3  2  1  0  1  0
V4  0  1  1  0  0
V5  0  2  0  0  0

1.) Start from V1=x

2.) K1 = (V1,V3,V1)

3.) Remove the edges in K1 from G

Updated adjacency matrix

   V1 V2 V3 V4 V5
V1  0  0  0  0  0
V2  0  0  1  1  2
V3  0  1  0  1  0
V4  0  1  1  0  0
V5  0  2  0  0  0

4.) V3=y (is in K1 and has degree=2)

5.) K2 = (3,4,2,3)

3.) remove K2 edges

Updated adjacency matrix

   V1 V2 V3 V4 V5
V1  0  0  0  0  0
V2  0  0  0  0  2
V3  0  0  0  0  0
V4  0  0  0  0  0
V5  0  2  0  0  0

4.) V2=y (is in K2 and has degree=2

5.) K3 = (2,5,2)

6.) All edges used

7.) Starting from x=V1 we build H

H=(1,3

Here the first intersection with another "sub"-Euler tour (K2) occurs and we include it. Thus

H=(1,3,4,2

Another intersection (with K3) we include that one too

H=(1,3,4,2,5,2

We included the whole tour and continue with the one we where previously following (K2)

H(1,3,4,2,5,2,3

Here the K2 ends we are back on the K1 tour and follow that.

H=(1,3,4,2,5,2,3,1)

Done. Euler tour found

So you see the algorithm you mentioned can't really be done just with some simple looping over an array. You will need to hold some state info on which edges you already used and which "sub"-Euler tours you already found.