问从Tuple<int，int>列表中删除元素，如果任何组件位于C#中的另一个HashSet<int>列表中
EN

Stack Overflow用户

提问于 2021-06-30 01:51:48

回答 1查看 67关注 0票数 0

我正在一个无向图上执行DFS，目标是获取我以后想要读出的所有集群。为此，我实例化了edges类型为List<Tuple<int, int>>，vertices是一个简单的整数数组。DFS(graph, vertex)返回整数的HashSet。问题是been循环中的最后一行，如何从已经访问过的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;
    }
}

任何帮助都是非常感谢的:)

我正在重新发布我以前的问题的编辑版本，我现在删除了这个问题，因为前面的问题缺少一个最小的可重复的例子。

list

graph

depth-first-search

实时音视频9.9元起，弱网高质量通信

9.9元畅享2万分钟实时音视频通话时长，低成本、低门槛快速接入端到端延时＜300ms 的高品质实时互动通话

回答 1

Stack Overflow用户

回答已采纳

发布于 2021-06-30 02:27:34

据我所见，您的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));
}