#include <iostream>
#include <algorithm>
#include <windows.h>
#include <omp.h>
using namespace std;
class Graph {
private:
bool** adjMatrix;
bool** Pmatrix;
int numVertices;
int* p; // перестановка
public:
Graph(int numVertices) {
this->numVertices = numVertices;
adjMatrix = new bool* [numVertices];
Pmatrix = new bool* [numVertices];
for (int i = 0; i < numVertices; i++) {
adjMatrix[i] = new bool[numVertices];
Pmatrix[i] = new bool[numVertices];
for (int j = 0; j < numVertices; j++) {
adjMatrix[i][j] = false;
Pmatrix[i][j] = false;
}
}
p = new int[numVertices];
for (int i = 0; i < numVertices; i++)
p[i] = i;
}
int getNumVertices() {
return numVertices;
}
void addEdge(int i, int j) {
adjMatrix[i][j] = true;
adjMatrix[j][i] = true;
}
int* getP() {
return p;
}
bool** getAdjMatrix() {
return adjMatrix;
}
int* retPer() {
next_permutation(p, p + numVertices);
cout << "Перестановка" << endl;
for (int i = 0; i < numVertices; i++)
cout << p[i] << " ";
cout << endl;
return p;
}
bool** retPmatrix(int* p) {
for (int i = 0; i < numVertices; i++)
for (int j = 0; j < numVertices; j++)
Pmatrix[i][j] = false;
for (int i = 0; i < numVertices; i++)
Pmatrix[p[i]][i] = true;
return Pmatrix;
}
bool** traspPmatrix(bool** Pmatrix) {
bool** tPmatrix = new bool* [numVertices];
for (int i = 0; i < numVertices; i++) {
tPmatrix[i] = new bool[numVertices];
for (int j = 0; j < numVertices; j++)
tPmatrix[i][j] = Pmatrix[j][i];
}
return tPmatrix;
}
bool** mulMatrix(bool** A, bool** B) {
bool** C = new bool* [numVertices];
int i, j, k;
for (i = 0; i < numVertices; i++) {
C[i] = new bool[numVertices];
for (j = 0; j < numVertices; j++)
C[i][j] = false;
}
for (i = 0; i < numVertices; i++) {
for (j = 0; j < numVertices; j++)
for (k = 0; k < numVertices; k++)
C[i][j] = C[i][j] || (A[i][k] && B[k][j]);
}
return C;
}
void printMatrix(bool** Matrix) {
for (int i = 0; i < numVertices; i++) {
cout << i << " : ";
for (int j = 0; j < numVertices; j++)
cout << Matrix[i][j] << " ";
cout << endl;
}
cout << endl;
}
Graph(const Graph &graph) : adjMatrix(graph.adjMatrix), Pmatrix(graph.Pmatrix),
numVertices(graph.numVertices), p(graph.p) {}
~Graph() {
for (int i = 0; i < numVertices; ++i) {
delete[] adjMatrix[i];
delete[] Pmatrix[i];
}
delete[] adjMatrix;
delete[] Pmatrix;
delete p;
}
};
bool isIsomorph(Graph g1, Graph g2) {
int* Per = g1.getP();
bool** Iso = g1.mulMatrix(g1.mulMatrix(g1.retPmatrix(Per), g1.getAdjMatrix()), g1.traspPmatrix(g1.retPmatrix(Per)));
if (g2.getAdjMatrix() == Iso)
return 1;
else
return 0;
}
int main() {
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
double start_time, end_time;
Graph g1(4), g2(4);
//GRAPH1////////
g1.addEdge(0, 1);
g1.addEdge(0, 2);
g1.addEdge(1, 2);
g1.addEdge(2, 3);
//GRAPH2/////////
g2.addEdge(0, 1);
g2.addEdge(0, 2);
g2.addEdge(1, 2);
g2.addEdge(2, 3);
if (g1.getNumVertices() == g2.getNumVertices()) {
if (g1.getAdjMatrix() != g2.getAdjMatrix()) {
cout << "Матрица смежности графа А" << endl;
g1.printMatrix(g1.getAdjMatrix());
cout << "Матрица смежности графа B" << endl;
g2.printMatrix(g2.getAdjMatrix());
cout << "Первоначальная перестановка = [0, 1, 2, 3]" << endl; //ее не видно
start_time = omp_get_wtime();
if (isIsomorph(g1, g2))
cout << "Графы изоморфны" << endl;
else
cout << "Графы НЕ изоморфны" << endl;
end_time = omp_get_wtime();
printf("Время на замер времени %lf\n", end_time - start_time);
}
else
cout << "Вы ввели идентичные графы с одинаковыми матрицами смежностями, проверка на изоморфизм не требуется" << endl;
}
else
cout << "Error: Количество вершин не совпадает, проверка на изоморфизм отклоняется" << endl;
}
好吧,看看如果你突然复制会发生什么:
两个对象的指针将指向内存中的相同位置。这就是所谓的浅(表面)复制。
移除时
两个对象中的相同指针将导致内存在同一地址再次被释放......
在这里你需要一个深拷贝 - 即 为相同大小的矩阵分配新内存并重新复制所有元素...