1

我正在尝试Adjacency List使用 C# 表示图形，如下面的代码。 但我想知道在哪里可以找到更好的 C# 实现。喜欢这个 Java 网站： http: //algs4.cs.princeton.edu/41undirected/Graph.java.html

为了改进这个实现，我有一些问题：

  1. 是否有另一种简单的数据结构可供使用，并且您可以使诸如DFS, BFS,之类的操作Find the Shortest-path更容易？或者数据结构根据要解决的问题变化太大？

=== 已编辑 ===

我试图将数据结构实现如下。

OBS：这种方法看起来很简单，但我后来意识到这不太适合 DFS，例如，因为你需要一直跟踪第一个元素。在LinkedList我的解决方案中似乎最好使用自定义创建了链接列表，而不是 LinkedList<Vertex>.

考虑到下面的评论并保持简单性，我做了一些更改。但我不知道这些更改是否会影响进一步的操作，例如BFS. 为了能够拥有直接和间接图，我认为使用接口比使用属性更好。

 public interface IGraph
    {
        void InsertEdge(int edgeAKey, int edgeBKey);
        void IsertNewVertex(int vertexKey);
        LinkedList<Vertex> FindByKey(int vertexKey);
        bool ExistKey(int vertexKey);
    }

为了使其尽可能简单，我们可以使用已经实现的数据结构，例如Dictionary和LinkedList。而不是使用objectas Dictionary key，为了简单起见，我们可以在Vertexa key(or label) 和 a中创建value，如果您想添加一个已经存在于另一个中的值Vertex。

public class GraphDirect : IGraph
    {
        private Dictionary<int,LinkedList<Vertex>> Vertexes { get; set; }

        public GraphDirect()
        {
            Vertexes = new Dictionary<int, LinkedList<Vertex>>();
        }

        public bool ExistKey(int vertexKey)
        {
            if (this.FindByKey(vertexKey) == null)
                return false;
            else
                return true;
        }

        public void IsertNewVertex(int vertexKey)
        {
            if (!this.ExistKey(vertexKey))
            {
                Vertex vertex = new Vertex(vertexKey);
                LinkedList<Vertex> listVertexes = new LinkedList<Vertex>();
                listVertexes.AddFirst(vertex);
                this.Vertexes.Add(vertexKey, listVertexes);
            }
        }

        public void InsertEdge(int vertexAKey, int vertexBKey)
        {
            //Create the vertex A, if it doesn't exist            
            if (!this.ExistKey(vertexAKey))
            {
                this.IsertNewVertex(vertexAKey);
            } 
            //Will always insert the vertex B on this edge
            this.FindByKey(vertexAKey).AddLast(new Vertex(vertexBKey));
            //Create the vertex B, if doesn't exist
            if (!this.ExistKey(vertexBKey))
            {
                this.IsertNewVertex(vertexBKey);
            }
        }

        public LinkedList<Vertex> FindByKey(int vertexKey)
        {
            if (this.Vertexes.ContainsKey(vertexKey))
                return this.Vertexes[vertexKey];

            return null;
        }

    }

Vertex 类不需要任何其他指针，如有必要，只需保留keyand a 。value

public enum State { Visited = 0, UnVisited = 1, Processed = 2 }

public class Vertex
{
    public int Key;
    public int Value;
    public State Status = State.UnVisited;

    public Vertex(int key)
    {
        this.Key = key;
        this.Value = 0;
    }

    public Vertex(int key, int value)
    {
        this.Key = key;
        this.Value = value;
    }
}

public class Start
{
     public static void Main(){
         GraphDirect gDirect = new GraphDirect();
         gDirect.InsertEdge(2, 3);
         gDirect.InsertEdge(2, 8);
         gDirect.InsertEdge(5, 6);
     }
}
4

0 回答 0