想利用test函数在实现构造随机网络的大函数下计算连通图个数,以及最大连通图节点个数。test函数需要调用主函数里的adjacentMatrix及邻接矩阵,编译没有问题但是运行后报错。
//#include <stdafx.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<iostream>
#include <vector>
#include<algorithm>
#include<string.h>
#include<string>
using namespace std;
int NETWORK_SIZE;
double PROBABILITY_OF_EAGE;
int** adjacentMatrix;
void initial();
void generateRandomNetwork();
void writeRandomNetworkToFile();
void calculateDegreeDistribution();
void write2File_degreedistribut(double*);
int test();
int dfs();
int num = 0;
int ori[8][2] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, 1 }, { 0, -1 }, { 1, 0 }, { 1, 1 }, { 1, -1 } };
int main(int argc, char** argv)
{
clock_t start, finish;//用以记录算法起始时间
double duration;
cout << "*****************您将构建一个ER随机网络,请根据提示进行操作:*****************" << endl;
cout << " 请输入网络规模(即节点总数):";
cin >> NETWORK_SIZE;
cout << " 请输入ER网络连边概率:";
cin >> PROBABILITY_OF_EAGE;
start = clock();
srand((unsigned)time(NULL));//用来初始化随机数种子,用于rand()产生随机数
initial();
generateRandomNetwork();//构建ER网络函数
writeRandomNetworkToFile();///将ER网络的邻接矩阵写入文件randomNetwork中
calculateDegreeDistribution();//计算度分布
test();
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout << endl << " 生成这个ER网络需要的时间为:" << duration << endl;
cout << " 您已成功构建ER网络,请进入randomNetwork.txt文件查看ER网络的邻接矩阵,进入degree.txt文件查看度分布" << endl;
system("pause");//加了这条语句就不用设置断点即可查看
return 0;
}
void initial()
{
if (!(adjacentMatrix = (int**)malloc(sizeof(int*) * (NETWORK_SIZE + 1))))
{
cout << "邻接矩阵内存分配错误" << endl;
exit(0);
}
int i;
for (i = 1; i <= NETWORK_SIZE; i++)
{
if (!(adjacentMatrix[i] = (int*)malloc(sizeof(int) * (NETWORK_SIZE + 1))))
{
cout << "adjacentMatrix[" << i << "]分配内存错误" << endl;
exit(0);
}
}
}
void generateRandomNetwork() {
int i, j;
for (i = 1; i <= NETWORK_SIZE; i++)
for (j = i; j <= NETWORK_SIZE; j++)
adjacentMatrix[i][j] = adjacentMatrix[j][i] = 0;//初始化ER网络的邻接矩阵
int count = 0;//用以统计网络中无向边的个数
double probability = 0.0;
for (i = 1; i <= NETWORK_SIZE; i++)
{
for (j = i + 1; j <= NETWORK_SIZE; j++)
{
probability = (rand() % NETWORK_SIZE) / (double)NETWORK_SIZE;//生成一个随机数
if (probability < PROBABILITY_OF_EAGE)//如果此随机数小于连边概率,则在此(i,j)节点对之间添加一条边,否则不添加边。
{
count++;
adjacentMatrix[i][j] = adjacentMatrix[j][i] = 1;
}
}
}//重复直到所有的节点对都被选择一次
cout << " 您所构造的ER网络中的边数为:" << count;
}
void writeRandomNetworkToFile()
{
FILE* fout;
if (NULL == (fout = fopen("randomNetwork.txt", "w")))
{
cout << "打开文件randomNetwork.txt错误!\n" << endl;
exit(0);
}//在代码存放路径中新建randomNetwork.txt文件用于存放ER网络的邻接矩阵
int i, j;
for (i = 1; i <= NETWORK_SIZE; i++)
{
for (j = 1; j <= NETWORK_SIZE; j++)
fprintf(fout, "%d ", adjacentMatrix[i][j]);
fprintf(fout, "\n");//每行的邻接矩阵输完进行换行
}
fclose(fout);
}
void calculateDegreeDistribution() {
int* degree;
double* statistic;
int i, j;
double averageDegree = 0.0;
if (!(degree = (int*)malloc(sizeof(int) * (NETWORK_SIZE + 1))))
{
cout << "degree*malloc错误" << endl;
exit(0);
}
for (i = 1; i <= NETWORK_SIZE; i++)degree[i] = 0;
if (!(statistic = (double*)malloc(sizeof(double) * NETWORK_SIZE)))
{
cout << "statistic*malloc错误" << endl;
exit(0);
}
for (i = 0; i < NETWORK_SIZE; i++)statistic[i] = 0.0;
for (i = 1; i <= NETWORK_SIZE; i++)
for (j = 1; j <= NETWORK_SIZE; j++)
degree[i] = degree[i] + adjacentMatrix[i][j];
for (i = 1; i <= NETWORK_SIZE; i++)
averageDegree += degree[i];
cout << "\t平均度<k>=" << averageDegree / (double)NETWORK_SIZE;
for (i = 1; i <= NETWORK_SIZE; i++)
statistic[degree[i]]++;
double indentify = 0.0;
for (i = 0; i < NETWORK_SIZE; i++)
{
statistic[i] = statistic[i] / (double)NETWORK_SIZE;
indentify += statistic[i];
}
cout << endl << " 如果output为1则该算法正确\toutput=" << indentify << endl;
write2File_degreedistribut(statistic);
}
void write2File_degreedistribut(double* statistic)
{
FILE* fwrite;
if (NULL == (fwrite = fopen("degree.txt", "w")))
{
cout << "打开文件错误" << endl;
exit(0);
}
int i;
for (i = 0; i < NETWORK_SIZE; i++)
fprintf(fwrite, "%d %f\n", i, statistic[i]);//i表示度,statistic[i]为其概率
fclose(fwrite);
}
int dfs(int **adjacentMatrix, int n, int m)
{
if (m < 0 || n < 0) return 0;
if (adjacentMatrix[n][m] == 1)
{
adjacentMatrix[n][m] = -1;
num++;
}
else return 0;
for (int i = 0; i < 8; i++)
{
dfs(adjacentMatrix, n + ori[i][0], m + ori[i][1]);
}
return num;
}
int test()
{
int n, m, tmp;
int maxp = 0, number = 0;
tmp = 0;
for (int i = 0; i < NETWORK_SIZE; i++)
{
for (int j = 0; j < NETWORK_SIZE; j++)
{
if (adjacentMatrix[i][j] == 1)
{
number++;
dfs(adjacentMatrix, i, j);
maxp = max(maxp, num);
}
else
num = 0;
}
}
cout << number << " " << maxp;
return 0;
}