Структура данных дерева с ценными краями

Question

У меня есть график - например, - автобусные остановки и расстояния между ними.

График: AB5, ВС4, CD8, DC8, DE6, AD5, CE2, ЕВ3, AE7

AB5: остановка A, чтобы остановить B с расстоянием 5 и т.д.

Можете ли вы предложить структуру данных или дизайн объектов, которые могут поддерживать этот график.

Мое мнение по этому вопросу:

Узел - автобусная остановка в этом случае - может иметь один или несколько маршрутов. Маршрут имеет SourceNode и DestinationNode со значением - расстоянием. Узел имеет название адреса карты -> Маршрут.

Тогда это будет возможным тренировки расстояние для A-B-C, которая 9.

Отказ, эта проблема возникла сформировать упражнения приеме на работу несколько лет назад. Ваш вклад только для моего интереса к решению проблемы и не более того. Кроме того, я бы не решил работу с приложением, используя внешние источники, такие как StackOverflow.

Answer 1

Есть несколько структур данных для представления графа: Wikilink

Если вы выбрали бы матрицу смежности, вы бы иметь п * п матрицу, где каждый слот будет представлять собой расстояние между 2 вершинами. Я предпочитаю это представление, когда вы знаете количество вершин (желательно не слишком много, чтобы ваша матрица не занимала слишком много места). Легко найти расстояние между двумя вершинами, а также обновить расстояние, если вам нужно. Но если вы не уверены в количестве вершин, или это число может расти в будущем, другое представление будет лучшим выбором.

Вот некоторые фрагменты кода:

static void Main(string[] args) 
     { 
      int length = 7; //number of vertices 
      int [,] Matrix = new int[length-1,length-1]; 
      //instantiate Matrix with 0's 
      for(int i = 0; i < length; i++) 
      { 
       for(int j = 0; j < length; j++) 
       { 
        Matrix[i,j] = 0; 
       } 
      } 
      // Import your distances: 
      Matrix[0, 1] = 5; // AB5 
      Matrix[1, 2] = 4; //BC4 and so on.. 

     } 

Надеется, что вы получите представление о том, как продолжить. Если у вас много данных для ввода, вы можете прочитать его из некоторого файла и пополнить данные в матрице итеративно.