Как реализовать функцию add_vertex и add_edge в графе?

Question

Я создаю структуру данных шаблонного графа в C ++ и работаю над функциями add_vertex и add_edge.

Для функции add_vertex я попытался использовать матрицу смежности и установил для нее значение false. Однако я не уверен, правильно ли я это сделал.

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

template<typename vertex>
class directed_graph
{
    private:
            std::vector<std::vector<bool> > adj_matrix;
            size_t size;
            int num_of_vertices;

    public:
            void add_vertex(const vertex&); 
            void add_edge(const vertex&, const vertex&); 
}


template <typename vertex> 
void directed_graph<vertex>::add_vertex(const vertex& u) 
{
int newVertexNumber = num_of_vertices;
num_of_vertices++;

for(int i = 0; i<num_of_vertices; i++)
{
    adj_matrix[i][newVertexNumber] = false;
    adj_matrix[newVertexNumber][i] = false;
}

newVertexNumber = u;

}


template <typename vertex>
void directed_graph<vertex>::add_edge(const vertex& u, const vertex& v) 
{
 if ((u >= 0) && (u < size) && (v >= 0) && (v < size) && (u != v))
     {
    adj_matrix[u][v] = true;        
    adj_matrix[v][u] = true;
 }
}

для параметров метода, таких как "const vertex & u", я не слишком уверен, возможно ли передать тип вершины в индекс в adj_matrix [] []. Итак, я думаю, что мне нужен какой-то метод для извлечения индекса (позиции) u и v в матрице, а затем передать индекс в adj_matrix [index_u] [index_v], но я не уверен, как. Пожалуйста, помогите, спасибо.

Answer 1

При добавлении новой вершины размер matix также должен измениться, std::vector не изменяет размер автоматически при записи.

// Extend the matrix
int n = adj_matrix.size();
adj_matrix.resize(n+1);          // Add one more row
for (auto& row : adj_matrix) {
    row.resize(n+1);             // Add one more column to each row
}

Обратите внимание, что новые элементы в векторах bool автоматически инициализируются как false, если не указано явно использовать true.