diff --git a/networkx/algorithms/bipartite/matching.py b/networkx/algorithms/bipartite/matching.py
index 85f40a6eb..20a26f222 100644
--- a/networkx/algorithms/bipartite/matching.py
+++ b/networkx/algorithms/bipartite/matching.py
@@ -300,7 +300,8 @@ def eppstein_matching(G, top_nodes=None):
             recurse(v)
 
 
-def _is_connected_by_alternating_path(G, v, matching, targets):
+def _is_connected_by_alternating_path(G, v, matched_edges, unmatched_edges,
+                                      targets):
     """Returns True if and only if the vertex `v` is connected to one of
     the target vertices by an alternating path in `G`.
 
@@ -314,65 +315,56 @@ def _is_connected_by_alternating_path(G, v, matching, targets):
 
     `v` is a vertex in `G`.
 
-    `matching` is a dictionary representing a maximum matching in `G`, as
-    returned by, for example, :func:`maximum_matching`.
+    `matched_edges` is a set of edges present in a maximum matching in `G`.
+
+    `unmatched_edges` is a set of edges not present in a maximum
+    matching in `G`.
 
     `targets` is a set of vertices.
 
     """
-    # Get the set of matched edges and the set of unmatched edges. Only include
-    # one version of each undirected edge (for example, include edge (1, 2) but
-    # not edge (2, 1)).
-    matched_edges = {(u, v) for u, v in matching.items() if u <= v}
-    unmatched_edges = set(G.edges()) - matched_edges
-
-    def _alternating_dfs(u, depth, along_matched=True):
+    def _alternating_dfs(u, along_matched=True):
         """Returns True if and only if `u` is connected to one of the
         targets by an alternating path.
 
         `u` is a vertex in the graph `G`.
 
-        `depth` specifies the maximum recursion depth of the depth-first
-        search.
-
         If `along_matched` is True, this step of the depth-first search
         will continue only through edges in the given matching. Otherwise, it
         will continue only through edges *not* in the given matching.
 
         """
-        # Base case 1: u is one of the target vertices. `u` is connected to one
-        # of the target vertices by an alternating path of length zero.
-        if u in targets:
-            return True
-        # Base case 2: we have exceeded are allowed depth. In this case, we
-        # have looked at a path of length `n`, so looking any further won't
-        # help.
-        if depth < 0:
-            return False
-        # Determine which set of edges to look across.
-        valid_edges = matched_edges if along_matched else unmatched_edges
-        for v in G[u]:
-            # Consider only those neighbors connected via a valid edge.
-            if (u, v) in valid_edges or (v, u) in valid_edges:
-                # Recursively perform a depth-first search starting from the
-                # neighbor. Decrement the depth limit and switch which set of
-                # vertices will be valid for next time.
-                return _alternating_dfs(v, depth - 1, not along_matched)
-        # If there are no more vertices to look through and we haven't yet
-        # found a target vertex, simply say that no path exists.
+        if along_matched:
+            edges = itertools.cycle([matched_edges, unmatched_edges])
+        else:
+            edges = itertools.cycle([unmatched_edges, matched_edges])
+        visited = set()
+        stack = [(u, iter(G[u]), next(edges))]
+        while stack:
+            parent, children, valid_edges = stack[-1]
+            try:
+                child = next(children)
+                if child not in visited:
+                    if ((parent, child) in valid_edges
+                            or (child, parent) in valid_edges):
+                        if child in targets:
+                            return True
+                        visited.add(child)
+                        stack.append((child, iter(G[child]), next(edges)))
+            except StopIteration:
+                stack.pop()
         return False
 
     # Check for alternating paths starting with edges in the matching, then
     # check for alternating paths starting with edges not in the
-    # matching. Initiate the depth-first search with the current depth equal to
-    # the number of nodes in the graph.
-    return (_alternating_dfs(v, len(G), along_matched=True) or
-            _alternating_dfs(v, len(G), along_matched=False))
+    # matching.
+    return (_alternating_dfs(v, along_matched=True) or
+            _alternating_dfs(v, along_matched=False))
 
 
 def _connected_by_alternating_paths(G, matching, targets):
     """Returns the set of vertices that are connected to one of the target
-    vertices by an alternating path in `G`.
+    vertices by an alternating path in `G` or are themselves a target.
 
     An *alternating path* is a path in which every other edge is in the
     specified maximum matching (and the remaining edges in the path are not in
@@ -388,9 +380,18 @@ def _connected_by_alternating_paths(G, matching, targets):
     `targets` is a set of vertices.
 
     """
-    # TODO This can be parallelized.
-    return {v for v in G if _is_connected_by_alternating_path(G, v, matching,
-                                                              targets)}
+    # Get the set of matched edges and the set of unmatched edges. Only include
+    # one version of each undirected edge (for example, include edge (1, 2) but
+    # not edge (2, 1)). Using frozensets as an intermediary step we do not
+    # require nodes to be orderable.
+    edge_sets = {frozenset((u, v)) for u, v in matching.items()}
+    matched_edges = {tuple(edge) for edge in edge_sets}
+    unmatched_edges = {(u, v) for (u, v) in G.edges()
+                       if frozenset((u, v)) not in edge_sets}
+
+    return {v for v in G if v in targets or
+            _is_connected_by_alternating_path(G, v, matched_edges,
+                                              unmatched_edges, targets)}
 
 
 def to_vertex_cover(G, matching, top_nodes=None):

bipartite.to_vertex_cover() gives incorrect results
This program:
```python
import networkx as nx

print('Using version ' + nx.__version__)

G = nx.Graph([(0, 3), (1, 3), (1, 4), (2, 3)])
print('Edges: ' + repr(list(G.edges())))
assert nx.is_bipartite(G)
assert nx.is_connected(G)
matching = nx.bipartite.maximum_matching(G)
print('Matching: ' + repr(matching))
for u, v in matching.items():
    assert matching[v] == u
vertex_cover = nx.bipartite.to_vertex_cover(G, matching)
print('Vertex cover: ' + repr(vertex_cover))
for u, v in G.edges():
    assert u in vertex_cover or v in vertex_cover
```

produces:
```
$ python2.7 vertex_cover.py
Using version 1.11
Edges: [(0, 3), (1, 3), (1, 4), (2, 3)]
Matching: {0: 3, 1: 4, 3: 0, 4: 1}
Vertex cover: set([0, 1])
Traceback (most recent call last):
  File "vertex_cover.py", line 16, in <module>
    assert u in vertex_cover or v in vertex_cover
AssertionError
$ python3.6 vertex_cover.py
Using version 1.11
Edges: [(0, 3), (3, 1), (3, 2), (1, 4)]
Matching: {0: 3, 1: 4, 3: 0, 4: 1}
Vertex cover: {0, 1}
Traceback (most recent call last):
  File "vertex_cover.py", line 16, in <module>
    assert u in vertex_cover or v in vertex_cover
AssertionError
```

The vertex cover is incorrect, as verified by the `assert`s.

Current git version (21114082) fails in the same way.
diff --git a/networkx/algorithms/bipartite/tests/test_matching.py b/networkx/algorithms/bipartite/tests/test_matching.py
index c30582a19..22944c2c1 100644
--- a/networkx/algorithms/bipartite/tests/test_matching.py
+++ b/networkx/algorithms/bipartite/tests/test_matching.py
@@ -166,6 +166,25 @@ class TestMatching():
         independent_set = set(G) - {v for _, v in vertex_cover}
         assert_equal({'B', 'D', 'F', 'I', 'H'}, independent_set)
 
+    def test_vertex_cover_issue_2384(self):
+        G = nx.Graph([(0, 3), (1, 3), (1, 4), (2, 3)])
+        matching = maximum_matching(G)
+        vertex_cover = to_vertex_cover(G, matching)
+        for u, v in G.edges():
+            assert_true(u in vertex_cover or v in vertex_cover)
+
+    def test_unorderable_nodes(self):
+        a = object()
+        b = object()
+        c = object()
+        d = object()
+        e = object()
+        G = nx.Graph([(a, d), (b, d), (b, e), (c, d)])
+        matching = maximum_matching(G)
+        vertex_cover = to_vertex_cover(G, matching)
+        for u, v in G.edges():
+            assert_true(u in vertex_cover or v in vertex_cover)
+
 
 def test_eppstein_matching():
     """Test in accordance to issue #1927"""

pip install -e .
parse_log_pytest
requirements.txt
nose pytest
apt-get update apt-get install -y libgdal-dev graphviz
3.6
requirements/default.txt requirements/test.txt
pytest --no-header -rA --tb=line --color=no -p no:cacheprovider -W ignore::DeprecationWarning
attrs==22.2.0
certifi==2021.5.30
decorator==5.1.1
importlib-metadata==4.8.3
iniconfig==1.1.1
-e git+https://github.com/networkx/networkx.git@464bf8fc08ffa09cfd0183fb5cae1adfe6839e12#egg=networkx
nose==1.3.7
packaging==21.3
pluggy==1.0.0
py==1.11.0
pyparsing==3.1.4
pytest==7.0.1
tomli==1.2.3
typing_extensions==4.1.1
zipp==3.6.0

name: networkx
channels:
  - defaults
  - https://repo.anaconda.com/pkgs/main
  - https://repo.anaconda.com/pkgs/r
  - conda-forge
dependencies:
  - _libgcc_mutex=0.1=main
  - _openmp_mutex=5.1=1_gnu
  - ca-certificates=2025.2.25=h06a4308_0
  - certifi=2021.5.30=py36h06a4308_0
  - ld_impl_linux-64=2.40=h12ee557_0
  - libffi=3.3=he6710b0_2
  - libgcc-ng=11.2.0=h1234567_1
  - libgomp=11.2.0=h1234567_1
  - libstdcxx-ng=11.2.0=h1234567_1
  - ncurses=6.4=h6a678d5_0
  - openssl=1.1.1w=h7f8727e_0
  - pip=21.2.2=py36h06a4308_0
  - python=3.6.13=h12debd9_1
  - readline=8.2=h5eee18b_0
  - setuptools=58.0.4=py36h06a4308_0
  - sqlite=3.45.3=h5eee18b_0
  - tk=8.6.14=h39e8969_0
  - wheel=0.37.1=pyhd3eb1b0_0
  - xz=5.6.4=h5eee18b_1
  - zlib=1.2.13=h5eee18b_1
  - pip:
      - attrs==22.2.0
      - decorator==5.1.1
      - importlib-metadata==4.8.3
      - iniconfig==1.1.1
      - nose==1.3.7
      - packaging==21.3
      - pluggy==1.0.0
      - py==1.11.0
      - pyparsing==3.1.4
      - pytest==7.0.1
      - tomli==1.2.3
      - typing-extensions==4.1.1
      - zipp==3.6.0
prefix: /opt/conda/envs/networkx

networkx/algorithms/bipartite/tests/test_matching.py::TestMatching::test_vertex_cover_issue_2384 networkx/algorithms/bipartite/tests/test_matching.py::TestMatching::test_unorderable_nodes
networkx/algorithms/bipartite/tests/test_matching.py::TestMatching::test_eppstein_matching networkx/algorithms/bipartite/tests/test_matching.py::TestMatching::test_hopcroft_karp_matching networkx/algorithms/bipartite/tests/test_matching.py::TestMatching::test_to_vertex_cover networkx/algorithms/bipartite/tests/test_matching.py::TestMatching::test_eppstein_matching_simple networkx/algorithms/bipartite/tests/test_matching.py::TestMatching::test_hopcroft_karp_matching_simple networkx/algorithms/bipartite/tests/test_matching.py::TestMatching::test_eppstein_matching_disconnected networkx/algorithms/bipartite/tests/test_matching.py::TestMatching::test_hopcroft_karp_matching_disconnected networkx/algorithms/bipartite/tests/test_matching.py::TestMatching::test_issue_2127 networkx/algorithms/bipartite/tests/test_matching.py::test_eppstein_matching
networkx/algorithms/bipartite/matching.py
networkx/algorithms/bipartite/matching.py