Задача:
Реализовать класс SimpleGraph - простейшее представление структуры данных граф. В котором будут следующие методы:
- добавление новой вершины, которая ни с какими другими вершинами не связана;
- проверка наличия ребра между вершинами;
- добавление ребра между двумя заданными вершинами;
- удаление ребра между двумя заданными вершинами;
- удаление вершины со всеми её рёбрами.
Предварительные условия:
Каждая вершина - экземпляр класса Vertex, хранящий (в нашем случае) некоторое целочисленное значение.
В классе графа SimpleGraph потребуются три поля:
- max_vertex - максимальное количество вершин;
- m_adjacency - матрица смежности, где 0 означает отсутствие ребра между i-й и j-й вершиной, а 1 означает наличие ребра;
- vertex - список Vertex, хранящий вершины.
Задача выполняется в учебных целях, для ознакомления со структурами данных, поэтому данные передаваемые создаваемым методам заведомо корректны.
Кстати, деревья являются частным случаем графов. Подробнее про графы можно почитать в Википедии.
Решение:
class Vertex {
public int Value;
public Vertex(int val) {
Value = val;
}
}
class SimpleGraph {
int max_vertex;
int[][] m_adjacency;
Vertex[] vertex;
// конструктор класса
public SimpleGraph(int size) {
max_vertex = size;
m_adjacency = new int[size][size];
vertex = new Vertex[size];
}
// добавление новой вершины
public void AddVertex(int value) {
Vertex vertex = new Vertex(value);
for (int i = 0; i < max_vertex; i++) {
if (this.vertex[i] == null) {
this.vertex[i] = vertex;
break;
}
}
}
// true если есть ребро между вершинами v1 и v2
public boolean IsEdge(int v1, int v2) {
if (vertex[v1] == null || vertex[v2] == null) return false;
return m_adjacency[v1][v2] == 1;
}
// добавление ребра между вершинами v1 и v2
public void AddEdge(int v1, int v2) {
if (vertex[v1] == null || vertex[v2] == null) return;
m_adjacency[v1][v2] = 1;
m_adjacency[v2][v1] = 1;
}
// удаление ребра между вершинами v1 и v2
public void RemoveEdge(int v1, int v2) {
m_adjacency[v1][v2] = 0;
m_adjacency[v2][v1] = 0;
}
// удаление вершины со всеми её рёбрами
public void RemoveVertex(int v) {
vertex[v] = null;
for (int i = 0; i < max_vertex; i++) {
m_adjacency[v][i] = 0;
m_adjacency[i][v] = 0;
}
}
}
Вопросы пишите в комментариях.
