Есть реализация графа через матрицу смежности. Но у меня получился ступор при реализации алгоритмов обхода и алгоритма Прима.
Растолкуйте, кто может, как реализовать.
Ниже привожу написанный класс взвешенного, неориентированного графа.
Код:
//CGraph.h
class CGraph
{
public:
CGraph(): count(0),count_rib(0), matrix_val(NULL) {}
CGraph(int _count); // конструктор (_count - количество вершин)
~CGraph(); // деструктор
bool isEmpty() {return count==0;} //Проверка, является ли граф пустым
void Print(); // Вывод матрицы связей
void AddRib(int A,int B,int val); // Добавление ребра (A,B - вершины,val - вес ребра)
void DelRib(int A,int B); // Удаление ребра (A,B - вершины)
bool isRib(int A, int B); //Есть ли ребро между вершинами А и В
int CountOfRib() {return count_rib;} //Подсчет количества ребер в графе
int CountOfTip() {return count;} //вывод количества вершин
void AddTip(); // Добавление вершины
void DelTip(int A); // Удаление вершины
int DegreeOfTip(int A); // Степень вершины
void dfs(int u); //Обход графа в глубину.
void Floid();
private:
int** matrix_val; // матрица значений ребер
int count; // количество вершин
int count_rib;
};
Код:
//Graph.cpp
#include "stdafx.h"
#include <stdio.h>
#include "CGraph.h"
CGraph::CGraph(int _count)
{
count = _count;
count_rib=0;
matrix_val = new int*[count];
for(int i = 0;i < count;i++)
{
matrix_val[i] = new int[count];
for(int j = 0;j < count;j++) matrix_val[i][j] = 0x0FFFFFFF;
}
}
CGraph::~CGraph()
{
if(count > 0)
{
for(int i = 0;i < count;i++) delete [] matrix_val[i];
delete [] matrix_val;
}
count=count_rib=0;
}
void CGraph::Print()
{
for(int i = 0;i < count;i++)
{
for(int j = 0;j < count;j++)
{
if(i == j) break;
if(matrix_val[i][j] != 0x0FFFFFFF) printf("%d -- %d [%d]\n",i + 1,j + 1,matrix_val[i][j]);
}
}
}
void CGraph::AddRib(int A,int B,int val)
{
if(A > count) return;
if(B > count) return;
A--;
B--;
matrix_val[A][B] = val;
matrix_val[B][A] = val;
count_rib++;
}
void CGraph::DelRib(int A,int B)
{
if(A > count) return;
if(B > count) return;
A--;
B--;
matrix_val[A][B] = 0x0FFFFFFF;
matrix_val[B][A] = 0x0FFFFFFF;
count_rib--;
}
bool CGraph::isRib(int A, int B)
{
return matrix_val[A][B]!=0x0FFFFFFF;
}
//int CGraph::CountOfRib()
//{
// int cnt=0;
// for (int i=0; i<count; i++)
// for (int j=0; j<count; j++)
// if (matrix_val[i][j]!=0x0FFFFFFF) cnt++;
// cnt/=2;
// return cnt;
//}
void CGraph::AddTip()
{
int** _matrix_val;
_matrix_val = new int*[count + 1];
for(int i = 0;i < count + 1;i++)
{
_matrix_val[i] = new int[count + 1];
for(int j = 0;j < count + 1;j++)
{
_matrix_val[i][j] = 0x0FFFFFFF;
}
}
if(count > 0)
{
for(int i = 0;i < count;i++)
{
for(int j = 0;j < count;j++)
{
_matrix_val[i][j] = matrix_val[i][j];
}
delete [] matrix_val[i];
}
delete matrix_val;
}
matrix_val = _matrix_val;
count++;
}
void CGraph::DelTip(int A)
{
if(A > count) return;
A--;
// убираем связи
for(int i = 0;i < count;i++)
{
matrix_val[A][i] = 0x0FFFFFFF;
matrix_val[i][A] = 0x0FFFFFFF;
}
if(count > 1)
{
// создаём массив на 1 меньше и зануляем
int** _matrix_val;
_matrix_val = new int*[count - 1];
for(int i = 0;i < count - 1;i++)
{
_matrix_val[i] = new int[count - 1];
for(int j = 0;j < count - 1;j++)
{
_matrix_val[i][j] = 0x0FFFFFFF;
}
}
// копируем старую матрицу без строки A и столбца A
for(int i = 0;i < count;i++)
{
if(i < A)
{
for(int j = 0;j < count;j++)
{
if(j < A)
{
_matrix_val[i][j] = matrix_val[i][j];
}
else if(j > A)
{
_matrix_val[i][j - 1] = matrix_val[i][j];
}
}
}
else if(i > A)
{
for(int j = 0;j < count;j++)
{
if(j < A)
{
_matrix_val[i - 1][j] = matrix_val[i][j];
}
else if(j > A)
{
_matrix_val[i - 1][j - 1] = matrix_val[i][j];
}
}
}
delete [] matrix_val[i];
}
delete matrix_val;
// меняем ссылки
matrix_val = _matrix_val;
}
else
{
matrix_val = NULL;
}
// уменьшаем количество
count--;
}
int CGraph::DegreeOfTip(int A)
{
A--;
int degree = 0;
for(int i = 0;i < count;i++)
{
if(matrix_val[A][i] != 0x0FFFFFFF) degree++;
}
return degree;
}
//=========================== Depth First Search =================================
void CGraph::dfs(int u)
{
}
void CGraph::Floid()
{
/*for(int k = 0;k < count;k++)
{
for(int i = 0;i < count;i++)
{
for(int j = 0;j < count;j++)
{
if(matrix_val[i][k] != 0x0FFFFFFF && matrix_val[k][j] != 0x0FFFFFFF)
{
matrix_val[i][j] = min(matrix_val[i][j],matrix_val[i][k] + matrix_val[k][j]);
}
}
}
}*/
}