Преобразование пограничного списка в список смежности - PullRequest
Новая
       42

Преобразование пограничного списка в список смежности

0 голосов
/ 04 декабря 2018

У меня есть объект, который показывает мне связь между индексами и имеет переменные 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.

Ответы [ 2 ]

0 голосов
/ 16 апреля 2019 
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()
0 голосов
/ 01 апреля 2019

Не так оптимизировано, но я думаю, что это будет работать. 

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