11-2打卡

今天学习了prim算法最小生成树

#include<iostream>
#define MAX 1000000
using namespace std;

struct graph
{
	char* vex;
	int vexnum;
	int** arc;
};

struct Edge
{
	char vex;
	int weight;
};


//若edge[i]为0则代表已加入u集合（最小生成树集合）
Edge* initedge(graph* g, int index) {
	Edge* edge = new Edge[g->vexnum];
	for (int i = 0; i < g->vexnum; ++i) {
		edge[i].vex = g->vex[index];//edge[i].vex为起始节点，g.vex[i]为目标顶点,edge[i].weight为他们之间的权值若为0则已加入u集合
		edge[i].weight = g->arc[index][i];
	}
	return edge;
}

int getMinVex(graph* g,Edge* edge) {
	int min = MAX;
	int index;
	for (int i = 0; i < g->vexnum; ++i) {
		if (edge[i].weight && min > edge[i].weight) {
			min = edge[i].weight;
			index = i;
		}
	}
	return index;
}

void prim(graph* g) {
	Edge* edge = initedge(g, 0);
	for (int i = 0; i < g->vexnum - 1; ++i) {
		int min = getMinVex(g,edge);
		cout << 'V' << edge[min].vex << "->" << 'V' << g->vex[min] << ' ' << "weight="<<edge[min].weight << endl;
		edge[min].weight = 0;//g.vex[min]加入u集合则置min为0
		for (int j = 0; j < g->vexnum; ++j) {
			if (g->arc[min][j] < edge[j].weight && g->arc[min][j]) {
				edge[j].vex = g->vex[min];
				edge[j].weight = g->arc[min][j];
			}
		}
	}
}

void initgraph(graph*& g, int n)
{

	g->vexnum = n;
	g->vex = new char[n];
	g->arc = new int* [n];
	for (int i = 0; i < n; i++)
	{
		g->arc[i] = new int[n];
	}
}

void creatgraph(graph* g, char* vex, int* nums)
{
	for (int i = 0; i < g->vexnum; ++i)
	{
		g->vex[i] = vex[i];
	}
	for (int i = 0; i < g->vexnum; i++)
	{
		for (int j = 0; j < g->vexnum; j++)
		{
			g->arc[i][j] = *(nums + i * g->vexnum + j);
		}
	}
}

void Dfs(graph* g, int index, int* vexindex) {
	cout << g->vex[index];
	vexindex[index] = 1;
	for (int i = 0; i < g->vexnum; ++i) {
		if (g->arc[index][i] && !vexindex[i] && g->arc[index][i]!=MAX)
			Dfs(g, i, vexindex);
	}
}

//void Bfs(graph* g, int* vexindex)
//{
//	queue<int>a;
//	a.push(0);
//	cout << g->vex[0];
//	vexindex[0] = 1;
//	while (!a.empty())
//	{
//		int j = a.front();
//		a.pop();
//		for (int i = 0; i < g->vexnum; i++) {
//			if (g->arc[j][i] && !vexindex[i])
//			{
//				a.push(i);
//				cout << g->vex[i];
//				vexindex[i] = 1;
//			}
//		}
//	}
//}

int main()
{
	graph* g = new graph;
	initgraph(g, 6);
	char vex[6] = { '1','2','3','4','5','6'};
	int arc[6][6] = {
		0,6,1,5,MAX,MAX,
		6,0,5,MAX,3,MAX,
		1,5,0,5,6,4,
		5,MAX,5,0,MAX,2,
		MAX,3,6,MAX,0,6,
		MAX,MAX,4,2,6,0
	};
	creatgraph(g, vex, (int*)arc);
	int vexindex[6] = { 0 };
	prim(g);
	cout << endl;
	Dfs(g, 0, vexindex);
	//memset(vexindex, 0, sizeof(vexindex));
	//Bfs(g, vexindex);
	return 0;
}