当前位置 博文首页 > zhouwenyan2548的博客：随机生成有向连通图（c++）
提示：以下是本篇文章正文内容，下面案例可供参考
代码如下（示例）：
memset函数的作用就是把你快连续的内存初始化为你给的值。
void clearmap()//初始化
{
ff = true;
memset(b, 0, MAX*sizeof(int));//将b数组中的 MAX个int型内存空间全初始化为零
memset(c, 0, MAX*sizeof(int));//将c数组中的MAX个int型内存空间全部初始化为零
for (int i = 0; i < m; i++)
{
visit[i] = false;// 将节点未访问标记为没访问
for (int j = 0; j < m; j++)
{
a[i][j] = 0;
c[i][j] = 0;
}
}
}
INT_MAX是一个很大的整形数
代码如下（示例）：
void randcreat() //随机生成图,计算各结点的度,并输出矩阵
{
int ra, rb; //两个随机数，用于记录各节点的度
int count = 0; //只有m条边，count来记录当前生成的边数
srand(time(0));//按照当前的时间值种下随机种子数，使得任意时刻产生的随机数都是不同的
while (count<n)
{
ra = rand() % m;//生成数组随机位置
rb = rand() % m;
while (ra == rb)
rb = rand() % m;//这两个随机数必须是不相等
if (!a[ra][rb])
{
a[ra][rb] = a[rb][ra] = rand() %9 + 1;//对称生成邻接矩阵,随机生成权值，
count++;
b[ra]++;
b[rb]++;
}
}
for (int i = 0; i<m; i++)
{
for (int j = 0; j<m; j++){
if(a[i][j]==0){
a[i][j]=INT_MAX;// INT_MAX是一个很大的整形数
a[i][i]=0;
}
cout << " " << a[i][j] << " ";
}
cout << endl;
}
}
注意：这里仅限于随机生成有向图的邻接矩阵a[i][j]，后续的邻接矩阵转图还请读者自行摸索
通过jsp里javascript中location.href跳转到servlet并传多个变量参数实现。
相应的代码如下
void DFS(int x)
{
visit[x] = true;
for (int i = 0; i<m; i++)
if (!visit[i] && a[x][i])
DFS(i);
}
bool judge_connect()
{
DFS(0);
for (int i = 0; i<m; i++)
if (!visit[i])
return false;
return true;
}
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#define MAX 1000
using namespace std;
int a[MAX][MAX]; //图的矩阵
int b[MAX]; //记录各节点的度
bool visit[MAX], ff = true; //记录是否被访问过
int m, n; // m表示结点个数，n表示边的条数
int c[MAX][MAX]; //判断该边是否已经走过
void randcreat(); //随机生成图,计算各结点的度,并输出矩阵
void DFS(int x); //深度优先搜索判断是否为连通图
bool judge_connect(); //判断是否联通
//memset的作用就是把你快连续的内存初始化为你给的值。
void clearmap()//初始化
{
ff = true;
memset(b, 0, MAX*sizeof(int));//将b数组中的 MAX个int型内存空间全初始化为零
memset(c, 0, MAX*sizeof(int));//将c数组中的MAX个int型内存空间全部初始化为零
for (int i = 0; i < m; i++)
{
visit[i] = false;// 将节点未访问标记为没访问
for (int j = 0; j < m; j++)
{
a[i][j] = 0;
c[i][j] = 0;
}
}
}
int main()
{
while (1)//无限循环
{
cout << "请输入节点的个数" << endl;//最后输出空格
cin >> m;
cout << "请输入边的个数" << endl;
cin >> n;
while(n>(m*(m - 1) / 2)) //判断边数是否输入正确，若要满足有向图定义即 n<m*(m-1) ,无向图即要满足n <m*(m-1)/2
{
cout << "输入边数过大，请重新输入：" << endl;
cin >> m >> n;
}
randcreat();
if (judge_connect())
cout << "随机生成的图是一个带权有向连通图！" << endl;
else
{
cout << "该随机生成的图不是连通图" << endl;
clearmap();
continue;
}
ff = true;
clearmap();
cout << endl << endl << endl;
cout << "请进行你的下一次输入：\n";
}
return 0;
}
void randcreat() //随机生成图,计算各结点的度,并输出矩阵
{
int ra, rb; //两个随机数，用于记录各节点的度
int count = 0; //只有m条边，count来记录当前生成的边数
srand(time(0));//按照当前的时间值种下随机种子数，使得任意时刻产生的随机数都是不同的
while (count<n)
{
ra = rand() % m;//生成数组随机位置
rb = rand() % m;
while (ra == rb)
rb = rand() % m;//这两个随机数必须是不相等
if (!a[ra][rb])
{
a[ra][rb] = a[rb][ra] = rand() %9 + 1;//对称生成邻接矩阵,随机生成权值，
count++;
b[ra]++;
b[rb]++;
}
}
for (int i = 0; i<m; i++)
{
for (int j = 0; j<m; j++){
if(a[i]
