将边缘列表转换为邻接列表

Question

我有一个对象显示了索引之间的联系，它有变量 index1、index2。基于索引的连接，我想创建一棵树，它总是从 0.

开始

在此示例中，0 与 2 和 5 相关联，因此它们将首先添加到树中，然后从最低层继续，我需要找到什么数字连接到 2，在本例中是 6 和 7，等等。

{index1=0, index2=2}
{index1=3, index2=4}
{index1=1, index2=4}
{index1=0, index2=5}
{index1=2, index2=6}
{index1=1, index2=5}
{index1=2, index2=7}


               0
          2       5
       6    7       1
                      4

看来我需要的是将其转换为邻接表。

作为最终结果，我需要 preorder traverse 通过树或所有节点并获得结果，在本例中为：

0 - 2 - 6 - 7 - 5 - 1 - 4

我应该使用什么来获得想要的结果？

或者我如何创建一个 Adjacency List，我可以在其中添加到根，这意味着如果我要给出值 (0, 2) 然后 (0,5) 它会添加这些值不是在彼此之下而是分开然后 (2, 6) 会在 node 2.

之下

Answer 1

没有那么优化，但我认为它会起作用。

static class Connection{
  int index1;
  int index2;
  Connection(int index1,int index2){
       this.index1=index1;
       this.index2=index2;
  }
}

private static List<Connection> connections;
private static List<List<Integer>> adjList;
private static int max;

static void makeAdjList(){
     for(int i=0;i<max;i++){
        for(int j=0;j<connections.size();j++){
            Connection c=connection.get(j);
            if(c.index1==0||c.index2==0){
               adjList.get(i).add(c.index1==0?c.index2:index1);
            }
        }
     }
}

Answer 2

import os

vertexNum =#Vertexes
edgeNum = #Edges
edgeList = [[0,[-3]]]

source = "destination of edgelist file"

f = open(source, "r")
l = f.readlines()
l2 = [line.rstrip('\n') for line in l]

for i in range(1,vertexNum+1):
    edgeList.append([i,[]])

for line in l2:
    graph_Local = [line.split(" ")[0],line.split(" ")[1]]
    edgeList[int(graph_Local[0])][1].append(int(graph_Local[1]))
    edgeList[int(graph_Local[1])][1].append(int(graph_Local[0]))


with open('destination to save adjacency list','w') as eFile:
    for item in edgeList:
        eFile.write("%s\n" % item[1])

eFile.close()

将边缘列表转换为邻接列表

Converting Edgelist to Adjacency List

java

graph

adjacency-list