Создание матрицы смежности для BFS

Question

Создание матрицы смежности для BFS

Мне дают входной файл, который содержит такие числа:

3 (поиск значения 3 на графике)

5 (количество вершин в графе)

0 0 (вершина 0 имеет значение 0)

2 (добавить 2 ребра из вершины 0)

1 (добавить ребро из вершины 0 в вершину 1)

2 (добавить ребро из вершины 0 в вершину 2)

1 1 (вершина 1 имеет значение 1)

2 (добавить 2 ребра из вершины 1)

3 (добавить ребро из вершины 1 в вершину 3)

4 (добавить ребро из вершины 1 в вершину 4)

2 2 (вершина 2 имеет значение 2) …….

Я хочу создать матрицу смежности, используя указанные числа в файле, но я не уверен, как это сделать. Как мне убедиться, что я просто заполняю матрицу нулями или единицами в зависимости от того, существует ли существующее ребро? Я не думаю, что смогу просто читать в каждом файле по одному, потому что не все строки содержат подробную информацию о краях. Любое понимание будет с благодарностью. Спасибо!

-1

adjacency-matrix breadth-first-search c++graph

Решение

Другие решения

Предполагая вашу матрицу Edges заполнен нулями, вы можете сделать что-то вроде этого:

Прочитайте первое число и сохраните значение где-нибудь (я не
понять, для чего вообще нужен первый номер).
Прочитайте второе число и сохраните его в n,
Пока нет конца строки, делайте строки 4..8
Прочитайте число и сохраните его в переменной v (количество
вершина)
Прочитайте номер и сохраните его в Values[v] (значение тока
вершина)
Прочитайте номер и сохраните его в e (количество ребер от
vвершина
Для меня от 1 до е сделать 8.
Читать v1 и положи Edges[v, v1] = 1 (и, возможно, E [v1, v], если E должен быть симметричным).

0

Источник

Accepted Answer

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

std::ifstream in;

// Read the target and number of nodes.
int target;
int num_nodes;

in >> target >> num_nodes;

// Whatever matrix data type you are using.
matrix adj_matrix(num_nodes, num_nodes);

// Process each vertex.
for (int i = 0; i < num_nodes; ++i) {
int node;
int value;
in >> node >> value;

// Figure out how many edges the vertex has.
int num_edges;
in >> num_edges;

// Process each edge and add it to the matrix.
for (int j = 0; j < num_edges; ++j) {
int other_node;
in >> other_node;

// Add the dependency both ways to the matrix.
adj_matrix[node][other_node] = true;
adj_matrix[other_node][node] = true;
}
}

0