• 大小: 5KB
    文件类型: .cpp
    金币: 1
    下载: 0 次
    发布日期: 2021-06-07
  • 语言: C/C++
  • 标签: 数据结构  C++  图论  

资源简介

无向图 破圈法求最小生成树 WIN32控制台应用程序 VS2010以上编译运行成功 数据结构上机作业 图用的是邻接矩阵表示方法

资源截图

代码片段和文件信息

#include
#include
#define INF 9999
#define UNVIS 0
#define VIS 1
using namespace std;
class node{
public:
char value;
node()
{

}
};
class graph{
public:
int save_i;
bool stop_push_vector;
bool  find_flag;
vector myvec;
int ** matrix;
bool ** edge_flag;
bool * mark;
node *  nodes;
int length;
bool haveloop()
{
myvec.clear();
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length; j++)
{
if(i==j)
edge_flag[i][j]=VIS;
else
edge_flag[i][j]=UNVIS;
}
}
if(DFS_search()==true)//有环
{
//删除最大的边  在myvec中有记录



return true;
}
else
return false;
}

graph(int num=5)
{
length=num;
mark = new bool[length];
nodes = new node[length];
matrix = new int*[length];
edge_flag=new bool*[length];
for (int i = 0; i < length; i++)
{
edge_flag[i]=new bool[length];
}
for (int i = 0; i < length; i++)
{
matrix[i]=new int[length];
}
//初始化
for (int i = 0; i < length; i++)
{
mark[i]=UNVIS;
}
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length; j++)
{
if(i==j)
matrix[i][j]=0;
else 
matrix[i][j]=INF;


}
}
//输入顶点value
cout<<“输入“< for (int i = 0; i < length; i++)
{

cin>>nodes[i].value;
}

}

int get_su(char value)
{
for (int i = 0; i < length; i++)
{
if(nodes[i].value==value)
return i;
}
cout<<“erro“;
return -1;
}
void setedge(char ichar jint weight)
{
matrix[get_su(i)][get_su(j)]=weight;
matrix[get_su(j)][get_su(i)]=weight;
}
bool DFS_search()
{
//重置标记
find_flag=false;//没找到环
stop_push_vector=false;
for (int i = 0; i < length; i++)
{
mark[i]=UNVIS;
}
for (int i = 0; i < length; i++)
{
if(find_flag==false &&mark[i]==UNVIS)
DFS_S(i);
}

if(find_flag==true)
{
//找到并删除存储在myvec中最大的边
vector::iterator i;
node * p1*p2;
p1=*(myvec.begin());
p2=*(myvec.begin()+1);
int max_edge = matrix[get_su(p1->value)][get_su(p2->value)];//前2个点的边的长

for (i = myvec.begin()+1; (i+1) != myvec.end(); i++)//从第(23)个边开始 到end-1end
{
if( matrix[get_su((*i)->value)][get_su((*(i+1))->value)]  > max_edge)
{
max_edge =  matrix[get_su((*i)->value)][get_

评论

共有 条评论