图邻接列表实现
我试图用C＃表示Adjacency List的图形，如下面的代码。 但我想知道在哪里可以找到更好的C＃实现。 喜欢这个Java网站： http ： //algs4.cs.princeton.edu/41undirected/Graph.java.html
为了改进这个实现，我有一些问题：
- 是否有另一种简单的数据结构可供使用，并且您能够更轻松地进行
DFS，BFS，Find the Shortest-path操作？ 或者根据要解决的问题，数据结构变化太大了？
===已编辑===
我试图将数据结构实现如下。
OBS ：这种方法看起来很简单，但后来我意识到这不太适合DFS，例如，因为你需要一直跟踪LinkedList的第一个元素。在我的解决方案中似乎最好使用一个自定义创建的链接列表，而不是LinkedList 。
考虑到下面的评论并保持简洁，我做了一些改变。 但我不知道这些变化是否会影响进一步的运营，比如BFS 。 为了能够拥有直接和间接的图形，我认为使用接口比使用属性更好。
public interface IGraph { void InsertEdge(int edgeAKey, int edgeBKey); void IsertNewVertex(int vertexKey); LinkedList FindByKey(int vertexKey); bool ExistKey(int vertexKey); }
为了使它尽可能简单，我们可以使用已经实现的数据结构，如Dictionary和LinkedList 。 而不是使用object作为Dictionary key ，为了简化我们可以在Vertex创建一个key （或label ）和一个value ，如果你想添加一个已存在于另一个Vertex 。
public class GraphDirect : IGraph { private Dictionary<int,LinkedList> Vertexes { get; set; } public GraphDirect() { Vertexes = new Dictionary<int, LinkedList>(); } 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 listVertexes = new LinkedList(); 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 FindByKey(int vertexKey) { if (this.Vertexes.ContainsKey(vertexKey)) return this.Vertexes[vertexKey]; return null; } }
Vertex类不需要任何其他指针，只需保留key和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); } }