Векторы и карты в C ++

Question

У меня есть вектор A [9 3 6 9 3 6], каждые 2 элемента представляют ребро графа, я хочу создать матрицу смежности из этого вектора.

Сначала я создал уникальный вектор A [3 6 9], чтобы узнать размер моей матрицы

Во-вторых, я создаю матрицу и заполняю ее 0

В-третьих, я проведу цикл на A, чтобы узнать, какие ребра связаны, мой вопрос заключается в том, как я могу сказать C ++, что первый элемент в A, который равен трем, фактически представляет элемент 0 в моей матрице, то же самое для 6, что он представляет 1 и 9 представлен как 3, вот так, когда я строю свою матрицу смежности, я знаю, что 0 1 2 фактически представляет 3 6 9, я слышал об использовании карты, но не знал, как создать ее в моей программе, потому что я новичок в C ++.

Answer 1

Несколько способов:

1. Вы можете выполнить линейный поиск, чтобы найти индекс элемента в векторе
2. Ваш вектор отсортирован, возможен также бинарный поиск
3. вы можете создать карту, а не вектор, если ваши элементы в векторе не отсортированы. Заполните карту ключом в качестве значения в вашем векторе, а Vs - индексом, куда вы вставляете.

Первое - худшее решение. Используйте 3-й случай, если вектор не отсортирован. Используйте 2nd, если вы хотите уменьшить сложность пространства. 3-е также было бы хорошо, если бы использовался большой размер и хэш-карта.

Answer 2

Вы пытаетесь отследить метки для своих вершин.Если каждой вершине присвоен последовательно назначенный номер, вы можете отсканировать новые метки вершин и вставить соответствующий последовательный номер в карту, например так:

std::map<int, std::size_t> labels;  // "int" is the label type; could be anything!

std::size_t store_vertex_label(int v)
{
  std::map<int, std::size_t>::const_iterator const it = labels.find(v);

  if (it != labels.end()) return it->second;

  const std::size_t new_number = labels.size();
  labels.insert(std::make_pair(v, new_number);
  return new_number;
}

Теперь, когда вы обрабатываете ввод, вы читаете один маркер метки v за один раз, отправьте его на store_vertex_label(), и вы получите соответствующий последовательный индекс вершины обратно.

Ваша матрица смежности будет иметь размер labels.size() в квадрате.

Обратите внимание, что ваштип метки не обязательно должен быть целым числом, это может быть что угодно (например, строка).