图构建邻接表

有人可以告诉我什么样的邻接表我必须作出建立一个图形与适当的节点和链接？我必须创建一个树结构来定义一个相关列表？还是有另一种方式？
现在对矩阵不感兴趣，谢谢。图构建邻接表

我可以例如使与其他arralists一个ArrayList每个位置内到边缘的其他节点有像：

nodes {a,b,c}, connection {{a-c},{b,c}}

，所以我有和ArrayList或者我邻接表[a[c],b[c],c[a,b]]

来源

2012-05-24 Defi

的邻接表只是表示哪些节点相互连接。

如果你有以下节点1-4的图形，相邻的矩阵看起来就像这样。 '1'表示节点之间的连接。

和列表将如下所示。 - >表示链接

1 -> 1 -> 2 -> 3 -> 4 
2 -> 1 
3 -> 2 -> 4 
4 -> 2 -> 3

你有虽然关于在阵列中使用链表如上所以该阵列会包含节点1指定 - 4.然后，你既可以具有表示到另一个节点的连接的成员变量或在数组的每个元素中都有一个单独的数组列表。

来源

2012-05-24 15:58:10 Hmm

不，我没有想过，但这不是一个坏主意。所以我可以使用简单的列表来构建图形结构。感谢您的安慰。 – Defi

没问题，有多种适用于创建图形的数据结构，链接列表通常更具动态性并且需要更少的内存。邻接矩阵O（n^2）需要时间来迭代。而邻接表使用与边缘数量成比例的存储器。 – Hmm

是的，我知道所有类型的表示，但我有一个例子，其中邻接表由二叉树表示，我感到困惑。 – Defi

ArrayList的ArrayList（或更一般地说，列表的列表）是一个很好的方法，是的。这是相当多的邻接表的标准代表。所以你的想法很好。另外，如果您事先知道图的大小（节点数），并且在创建之后不需要添加节点，那么ArrayLists数组也可以做并且更有效一些。

来源

2012-05-24 16:02:45 niklon

您可以使用Dictionary实现邻接列表。字典中的每个键将代表边的起始节点。每个值都是对象的List，每个对象都定义边的目标节点。

例如，您可以将Tuples的List存储在每个密钥中。 Tuple中的第一项表示目标节点。其他项目将定义边的属性。

class AdjacencyList 
{ 

    Dictionary<int, List<Tuple<int, int>>> adjacencyList; 

    // Constructor - creates an empty Adjacency List 
    public AdjacencyList(int vertices) 
    { 
     adjacencyList = new Dictionary<int, List<Tuple<int, int>>>(); 
    } 

    // Appends a new Edge to the linked list 
    public void addEdge(int startVertex, int endVertex, int weight) 
    { 
     if (!adjacencyList.ContainsKey(startVertex)) { 
      adjacencyList[startVertex] = new List<Tuple<int, int>>(); 
     } 

     adjacencyList[startVertex].Add(new Tuple<int, int>(endVertex, weight)); 
    } 

    // Removes the first occurence of an edge and returns true 
    // if there was any change in the collection, else false 
    public bool removeEdge(int startVertex, int endVertex, int weight) 
    { 
     Tuple<int, int> edge = new Tuple<int, int>(endVertex, weight); 

     return adjacencyList[startVertex].Remove(edge); 
    } 
}

来源

2016-03-18 00:17:42 gnerkus

图构建邻接表

回答

相关问题