如果任何组件在 C# 中的另一个 HashSet<int> 列表中，则从 Tuple<int, int> 列表中删除元素

Question

我正在对一个无向图执行 DFS，目标是获得我稍后要读出的所有簇。为此，我实例化了 List<Tuple<int, int>> 类型的 edges 并且 vertices 是一个简单的整数数组。 DFS(graph, vertex) returns 整数的 HashSet。问题是 while 循环中的最后一行，如何删除 edges 中已经访问过的所有元素？

using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;

public class Test {
    static public void Main(String[] args)
    {
        var vertices = Enumerable.Range(0, 10).ToArray();
        var edges = new List<Tuple<int, int>> {};
        edges.Add(Tuple.Create(1, 4));
        edges.Add(Tuple.Create(4, 1));
        edges.Add(Tuple.Create(3, 5));
        edges.Add(Tuple.Create(5, 3));

        var graph = new Graph<int>(vertices, edges);
        var algorithms = new GraphAlgorithms();
        var visited = new List<HashSet<int>>();

        // Apply DFS while there are clusters left
        while (edges.Any())
        {
            visited.Add(algorithms.DFS(graph, edges[0].Item1));
            edges.RemoveAll(node => visited.Contains(node));
        }
    }
}

这里有参考的类Graph和GraphAlgorithms，如果你想自己尝试的话：

using System;
using System.Collections.Generic;

public class Graph<T> 
{
    public Graph() {}
    public Graph(IEnumerable<T> vertices, IEnumerable<Tuple<T,T>> edges)
    {
        foreach(var vertex in vertices)
            AddVertex(vertex);

        foreach(var edge in edges)
            AddEdge(edge);
    }

    public Dictionary<T, HashSet<T>> AdjacencyList { get; } = new Dictionary<T, HashSet<T>>();

    public void AddVertex(T vertex) 
    {
        AdjacencyList[vertex] = new HashSet<T>();
    }

    public void AddEdge(Tuple<T,T> edge) 
    {
        if (AdjacencyList.ContainsKey(edge.Item1) && AdjacencyList.ContainsKey(edge.Item2)) 
        {
            AdjacencyList[edge.Item1].Add(edge.Item2);
            AdjacencyList[edge.Item2].Add(edge.Item1);
        }
    }
}

using System.Collections.Generic; 

public class GraphAlgorithms {
    public HashSet<T> DFS<T>(Graph<T> graph, T start) {
        var visited = new HashSet<T>();

        if (!graph.AdjacencyList.ContainsKey(start))
            return visited;
            
        var stack = new Stack<T>();
        stack.Push(start);

        while (stack.Count > 0) {
            var vertex = stack.Pop();

            if (visited.Contains(vertex))
                continue;

            visited.Add(vertex);

            foreach(var neighbor in graph.AdjacencyList[vertex])
                if (!visited.Contains(neighbor))
                    stack.Push(neighbor);
        }

        return visited;
    }
}

非常感谢任何帮助:)

我重新发布我之前删除的问题的编辑版本，因为之前的问题缺少最小的可重现示例。

Answer 1

据我所知，您的 visited 应该不是 List<Hashset<int>> 而只是 Hashset<int>，因此您的代码将更改为：

var visited = new HashSet<int>();
while(edges.Any())
{
    visited.UnionWith(algorithms.DFS(graph, edges[0].Item1));
    edges.RemoveAll(tuple => visited.Contains(tuple.Item1));
}

如果任何组件在 C# 中的另一个 HashSet<int> 列表中，则从 Tuple<int, int> 列表中删除元素

Remove element from list of Tuple<int, int> if any component is in another list of HashSet<int> in C#

c#

graph

list

depth-first-search