将Edgelist转换为邻接列表

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

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()

Answer 2

不是那么优化，但我认为它会起作用。

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);
            }
        }
     }
}