Regarding your second point: in the original paper by Garland & Heckbert, the cost of contracting a pair of vertices/an edge (v1, v2) is the sum of squared distances between the newly created vertex v_bar (that replaces the edge) and the planes of the triangles that meet at v1 and v2.

Now MeshLab relies on VCGlib for most of its computations. You can find details about the implementation of the edge collapse algorithm here. Basically it rescans the faces after the (simulated) collapse and uses a penalty if newly created triangles have an aspect ratio under a certain threshold and if their normals vary more than another threshold.

I'm not sure I understand your other questions, but my understanding is that the algorithm just considers the mesh connectivity (which is quite easy to get whether the mesh is stored as a face-vertex list or another format such as winged edge) and just works as long as there is an edge connecting two vertices.