数据结构 图 最小子树C/C++ 普里姆算法（Prime）

最小子树有两个最常用的方法

1、Prime算法

2、克鲁斯卡尔算法

这里，小编就先介绍 Prime算法

思路：

将 图存入 邻接表中，这时 创建一个额外空间，是一个结构体数组

取一个点为树根，开始，每次找出最小权值

这中算法是  树一点点长大，从根，开始，直至最后整个树建立

// 数组+链表 图.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include "pch.h"
#include "Linked.h"
#include "Graph.h"

const int INFTY = 10000;

typedef struct List {
	int closeVex;	// 前一个结点 index
	int lowWeight;	// 权值 ，初始值为 INYFTY
	bool flag;		//标记当前下标是否被使用
}List;

// 初始化 图，即 将图中的信息存入
void intiGraph(Graph<int>);
//初始化三元组 一维数组，closeVex = -1，lowWeight = INFTY,flag = false
void initList(List [],int);
// 输出三元组 数组
void outputList(List[], int);
// 普里姆算法 排序
void prim(int ,List [],int,Graph<int>);
// 通过给定最小权值，遍历 其 有效连接结点，比较权值，最小值默认为 0
int primTraverse(List list[],int length,int index, Linked<int> linked);
// 求 最下权值 index
int min(List list[], int length);
/*
0：5 2 1
1：3 5 0
2：4 0
3：4 5 1
4：3 5 2
5：4 3 1 0
*/
int main(void)
{
	//cout << "请输入数组的长度：";
	int length  = 6;
	//cin >> length;
	Graph<int> graph = Graph<int>(length);
	intiGraph(graph);
	graph.print();
	List * list = new List[length];
	initList(list,length);
	prim(0,list,length,graph);
	//cout << "fital resutl:" << endl;
	outputList(list, length);

	return 0;
}

int min(List list[], int length) {
	int index;
	for (int i = 0; i < length; i++)
	{
		if (!list[i].flag)
		{
			index = i;
			break;
		}
	}
	int min = list[index].lowWeight;
	for (int i = 0; i < length; i++)
	{
		if (min > list[i].lowWeight && list[i].flag==false) {
			//cout << "min = " << min << "  list[i].lowWeight=" << list[i].lowWeight << endl;
			index = i;
			min = list[i].lowWeight;
		}
	}
	return index;
}

int primTraverse(List list[],int length,int index, Linked<int> linked) {
	//cout << "打印当前链表："; linked.print();
	Node<int> * tmpPtr = linked.head.next;
	while (tmpPtr)
	{
		if (!list[tmpPtr->data].flag)
		{
			//cout <<"list[tmpPtr->data].lowWeight="<< list[tmpPtr->data].lowWeight << "   tmpPtr->weight="<< tmpPtr->weight << endl;
			if (list[tmpPtr->data].lowWeight > tmpPtr->weight)
			{
				list[tmpPtr->data].lowWeight = tmpPtr->weight;
				list[tmpPtr->data].closeVex = tmpPtr->data;
			}
		}
		tmpPtr = tmpPtr->next;
	}
	//outputList(list, length);
	//cout << "\n####################"<<endl;
	int small = min(list, length);
	//cout << "small = " << small << endl;
	return small;
}

void prim(int k,List list[],int length, Graph<int> graph) {
	
	int index = 0;
	for (int i = 0; i < length - 1; i++)	// 默认从第一个结点开始
	{
		list[index].flag = true;
		//cout << "index = " << index << endl;
		index = primTraverse(list,length, index, graph.list[index]);
	}
}

void outputList(List list[], int length) {
	for (int i = 0; i < length; i++)
	{
		cout <<i<<":\t" <<list[i].closeVex << "\t"<< list[i].lowWeight<<  "\t"<<list[i].flag << endl ;
	}
}

void initList(List list[],int length) {
	for (int i = 0; i < length; i++)
	{
		list[i].closeVex = -1;
		list[i].lowWeight = INFTY;
		list[i].flag = false;
	}
}

void intiGraph(Graph<int> graph) {
	graph.put(0, 1, 7);
	graph.put(0, 2, 10);
	graph.put(0, 5, 4);

	graph.put(1, 0, 7);
	graph.put(1, 5, 6);
	graph.put(1, 3, 8);

	graph.put(2, 0, 10);
	graph.put(2, 4, 2);

	graph.put(3, 1, 8);
	graph.put(3, 5, 5);
	graph.put(3, 4, 9);

	graph.put(4, 2, 2);
	graph.put(4, 5, 7);
	graph.put(4, 3, 9);

	graph.put(5, 0, 4);
	graph.put(5, 1, 6);
	graph.put(5, 3, 5);
	graph.put(5, 4, 7);
}


#pragma once
#include "Linked.h"

template<class Type>
class Graph
{
	int m_size;
public:
	Linked<Type> * list;
	Graph();
	void put(int index,Type data, int weight);
	void print(int index);
	void print();
	void outputWeight(int index);
	void outputWeight();
	void inputWeight(int index);
	void inputWeight();
	Graph(int size);
	~Graph();
};

template<class Type>
inline Graph<Type>::Graph()
{
	m_size = 16;
	list = new Linked<Type>[m_size];
}

template<class Type>
inline void Graph<Type>::put(int index, Type data,int weight)
{
	if (index < 0 || index >= m_size) {
		cout << "越界" << endl;
		return;
	}
	list[index].put(data,weight);
}

template<class Type>
inline void Graph<Type>::print(int index)
{
	list[index].print();
}

template<class Type>
inline void Graph<Type>::print()
{
	cout << "打印邻接表" << endl;
	for (int i = 0; i < m_size; i++)
	{
		cout << i << "：";
		list[i].print();
	}
	cout << endl;
}

template<class Type>
inline void Graph<Type>::outputWeight(int index)
{
	cout << index << "出度：" << list[index].outputWeight() << endl;
}

template<class Type>
inline void Graph<Type>::outputWeight()
{
	cout << "出度" << endl;
	for (int i = 0; i < m_size; i++)
	{
		outputWeight(i);
	}
	cout << endl;
}

template<class Type>
inline void Graph<Type>::inputWeight(int index)
{
	int count = 0;
	for (int i = 0; i < m_size; i++)
	{
		if (i != index) {
			count += list[i].inputWeight(index);
		}
	}
	cout << index << " 入度：" << count << endl;
}

template<class Type>
inline void Graph<Type>::inputWeight()
{
	cout << "入度" << endl;
	for (int i = 0; i < m_size; i++)
	{
		inputWeight(i);
	}
	cout << endl;
}

template<class Type>
inline Graph<Type>::Graph(int size)
{
	m_size = size;
	list = new Linked<Type>[m_size];
}

template<class Type>
inline Graph<Type>::~Graph()
{
	//delete list;
}

#pragma once
template<class Type>
struct Node {
	Type data;
	int weight;
	struct Node * next;
};

template<class Type>
class Linked
{
public:
	Node<Type> head;
	void put(Type data, int weight);
	void print();
	int outputWeight();
	int inputWeight(Type data);
	Linked();
	~Linked();
};

template<class Type>
inline void Linked<Type>::put(Type data,int weight)
{
	Node<Type> * nodeTmp = new Node<Type>;
	nodeTmp->data = data;
	nodeTmp->weight = weight;
	nodeTmp->next = head.next;
	head.next = nodeTmp;
}

template<class Type>
inline void Linked<Type>::print()
{
	if (head.next == NULL) {
		cout << "NULL" << endl;
		return;
	}
	Node<Type> * tmpPtr = head.next ;
	while (tmpPtr)
	{
		cout << tmpPtr->data << " ";
		tmpPtr = tmpPtr->next;
	}
	cout << endl;
}

template<class Type>
inline int Linked<Type>::outputWeight()
{
	int count = 0;
	if (head.next == NULL) {
		return count;
	}
	Node<Type> * tmpPtr = head.next;
	while (tmpPtr)
	{
		count += tmpPtr->weight;
		tmpPtr = tmpPtr->next;
	}
	return count;
}

template<class Type>
inline int Linked<Type>::inputWeight(Type data)
{
	int count = 0;
	if (head.next == NULL) {
		return count;
	}

	Node<Type> * tmpPtr = head.next;
	while (tmpPtr)
	{
		if (tmpPtr->data == data)
		{
			count += tmpPtr->weight;
		}
		tmpPtr = tmpPtr->next;
	}
	return count;
}

template<class Type>
inline Linked<Type>::Linked()
{
	head.data = 0;
	head.weight = 1;
	head.next = NULL;
}

template<class Type>
inline Linked<Type>::~Linked()
{
	//delete head;
}