- 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
- Check if all vertices have an even degree
- 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
- Choose some arbitrary vertex x from G
- Create a valid Euler tour K1 starting from x in G (uses just subset of all edges E)
- Delete all edges used by K1
- Choose a vertex y from K1 which still has a degree > 0
- Construct another Euler tour Kn starting from y from the remaining subset of edges in E
- Repeat until edges are used
- 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.
