邻接矩阵的最小生成树
// : 定义控制台应用程序的入口点
//
#include ""
#include <iostream>
using namespace std;
/*用于测试
abcdef
ab
6
ac
1
ad
5
ce
6
cf
4
ef
6
be
3
df
2
bc
5
cd
5
*/
//最小生成树普里姆算法
#define MVnum 100
bool visited[100];//
class Prim {
private:
char adgvex;//记录最小边在U中的那个定点
int lowcost;//记录最小边的权值
public:
void setAdgvex(char adgvex) {
this->adgvex = adgvex;
}
void setLowcost(int lowcost) {
this->lowcost = lowcost;
}
char getAdgvex() {
return this->adgvex;
}
int getLowcost() {
return this->lowcost;
}
};
//带权值的无向图
class Graph
{
public:
Graph(int vexnum, int arcnum) {
this->arcnum = arcnum;
this->vexnum = vexnum;
cout << "请依次输入顶点信息" << endl;
for (int i = 0; i < this->vexnum; i++) {
cin >> vexs[i];
}
closedge = new Prim[100];
}
void Creat();
int Location(char v);
void DFS_AM(int v);
void MiniSpanTree(int k) {
//无向网以邻接矩阵的形式存储，从顶点U出发
//构造无向网的最小生成树T，输出T的各边
char u0,v0;//u0和v0分别存储最小边的两个顶点
for (int i = 0; i < this->vexnum; i++) {
if (i != k){
closedge[i].setAdgvex(vexs[k]);
closedge[i].setLowcost(arcs[k][i]);
}
}
/*for (int i = 0; i < this->vexnum; i++) {
cout << closedge[i].getAdgvex() << "\t";
cout << closedge[i].getLowcost() << endl;
}
for (int i = 0; i < this->vexnum; i++) {
cout << vexs[i]<<"\t";
}
cout << endl;
system("pause");*///测试
//初始化相当于标记
closedge[k].setLowcost(0);//初始化 U = {vexs[k]}
for (int i = 1; i < this->vexnum; i++) {//选择其余n-1个顶点，生成
//n-1条边
k = Min(closedge);
cout << k << endl;//测试
//求出T的下一个结点：第K个顶点，closedge[k]中存有当前最小边
u0 = closedge[k].getAdgvex();//u0为最小边的一个顶点u0属于u
v0 = this->vexs[k];//v0为最小边的另一个顶点 v0属于v-u
cout << u0 << "——>" << v0 << endl;
closedge[k].setLowcost(0);//再次加入集合
for (int j = 0; j < this->vexnum; j++) {
if (this->arcs[k][j] < closedge[j].getLowcost()) {
closedge[j].setAdgvex(vexs[k]);
closedge[j].setLowcost(this->arcs[k][j]);
}
}
}
}
int Min(Prim* cl) {
int min = INT_MAX;
int index = -1;
for (int i = 0; i < this->vexnum; i++)
{
if (closedge[i].getLowcost() < min &&
closedge[i].getLowcost() != 0)
{
min = closedge[i].getLowcost();
index = i;
}
}
return index;
}
void printGraph();
private:
char vexs[MVnum];//顶点表
int arcs[MVnum][MVnum];//邻接矩阵
int vexnum;//图的当前点数
int arcnum;//图的边数
Prim *closedge;
};
void Graph::Creat()
{
int weight;//权值
char v1, v2;
//初始化邻接矩阵
for (int i = 0; i < this->vexnum; i++) {
for (int j = 0; j < this->vexnum; j++) {
arcs[i][j] = INT_MAX;
}
}
//构造邻接矩阵
for (int k = 0; k < this->arcnum; k++) {
cout << "请输入两个顶点值及其权值" << endl;
cin >> v1 >> v2 >> weight;
int i = Location(v1);
int j = Location(v2);
arcs[i][j] = weight;
//构造无向的网或图加上
arcs[j][i] = weight;
}
}
//获取顶点元素的下标
int Graph::Location(char v)
{
for (int i = 0; i < this->vexnum; i++) {
if (vexs[i] == v)
{
return i;
}
}
}
//
void Graph::DFS_AM(int v = 0)
{
cout << vexs[v] << endl;//
visited[v] = true;//
for (int w = 0; w < vexnum; w++)
{
if ((arcs[v][w] != INT_MAX) && (!visited[w]))
{
DFS_AM(w);
}
}
}
void Graph::printGraph() {
int temp;
for (int i = 0; i < this->vexnum; i++) {
for(int j = 0;j < this->vexnum;j++){
if (this->arcs[i][j] == INT_MAX) {
temp = 0;
}
else {
temp = this->arcs[i][j];
}
cout<<temp<< "\t";
}
cout << endl;
}
}
int main()
{
Graph z(6, 10);
();
z.DFS_AM();
();
(0);
system("pause");
return 0;
}