【C++】图的实现深度、广度遍历，普利姆算法，克鲁斯卡尔算法

根据图的抽象数据类型的定义，使用邻接矩阵或邻接表实现一个图。

    图的基本功能：

1、图的建立

3、深度优先遍历图

4、广度优先遍历图

 5、使用普里姆算法生成最小生成树

6、使用克鲁斯卡尔算法生成最小生成树

类模板的头文件：

#include<iostream>
using namespace std;

const int MAXSIZE = 10;
const int MAX = 10000;
const int MAX_VEXNUM = 6;//克鲁斯卡算法所用顶点数
const int MAX_EDGE = 9;
enum vertexType{DG,WDG,UDG,WUDG};//有向图，带权有向图，无向图，带权无向图
struct VEdge {//克鲁斯卡算法的边集数组
	int fromV;//起始顶点
	int endV;//终止顶点
	int weight;//边的权值
};
template<class T> 
class MGraph {
public:
	void Inititalize();//初始化顶点数组和邻接矩阵
	void CreateDG();
	void CreateWDG();
	void CreateUDG();
	void CreateWUDG();
	MGraph( int vertexnum, vertexType _kind);
	//对于无向图的遍历
	void DFS(int v);//从v的深度优先遍历
	void BFS(int v);//从v的广度优先遍历
	//普利姆算法
	friend void Prime(MGraph<T>& G);
	friend int SelectMin(MGraph<T>& G, int lowcost[]);
	//克鲁斯卡算法
	friend void GenSortEdge(MGraph<T> &G1, VEdge edgeList[]);//获取边集数组
	friend void Kruskal(MGraph<T> &G1, VEdge edgeList[]);//克鲁斯卡算法
private:
	T vertex[MAXSIZE];//顶点
	int arc[MAXSIZE][MAXSIZE];//矩阵
	int vertexNum;//顶点数
	int arcNum;//边数或者弧数
	vertexType kind;//图的种类
};

void GenSortEdge(MGraph<int> &G1, VEdge edgeList[]) {
	int k = 0, i, j;
	for(i=0;i<G1.vertexNum;i++)//进行边赋值
		for(j=i;j<G1.vertexNum;j++)
			if (G1.arc[i][j] != -1&& G1.arc[i][j] != 0) {
				edgeList[k].fromV = i;
				edgeList[k].endV = j;
				edgeList[k].weight = G1.arc[i][j];
				k++;
			}
	int pos = k-1;//初始值为边数
	while (pos != 0) {//使用冒泡排序的改进对边进行排序
		int bound = pos;
		pos = 0;
		for (int i = 0; i < bound; i++) {
			if (edgeList[i].weight > edgeList[i + 1].weight) {
				VEdge temp = edgeList[i];
				edgeList[i] = edgeList[i+1];
				edgeList[i+1] = temp;
				pos = i;
			}
		}
	}
}

void Kruskal(MGraph<int> &G1,VEdge edgeList[]){
	cout << "Kuruskal:"<<endl;
	int vset[MAX_VEXNUM];
	for (int i = 0; i < G1.vertexNum; i++)
		vset[i] = i;//初始化vset
	int k = 0, j = 0;
	while (k < G1.vertexNum - 1) {
		int m = edgeList[j].fromV, n = edgeList[j].endV;
		int sn1 = vset[m];
		int sn2 = vset[n];
		if (sn1 != sn2) {
			cout << "V" << m << "->V" << n << endl;
			k++;
			for (int i = 0; i < G1.vertexNum; i++) {
				if (vset[i] == sn2)
					vset[i] = sn1;//集合中sn2改为sn1
			}		
		}	
		j++;
	}
}

int SelectMin(MGraph<int> &G, int lowcost[]) {
	int min = MAX;
	int k = 0;
	for (int i = 1; i < G.vertexNum; i++) {
		if (lowcost[i] != 0 && lowcost[i] < min&&lowcost[i] != -1) {//寻找U——V的最小权值边
			min = lowcost[i];
			k = i;
		}
	}
	return k;
}

void Prime(MGraph<int>& G) {
	cout << "Prime:" << endl;
	int adjvex[MAXSIZE];//U集合中的顶点序号
	int lowcost[MAXSIZE];//U-V的最小权值边
	for (int i = 0; i < G.vertexNum; i++) {//初始化，辅助数组储存所有到Vo的边
		adjvex[i] = 0;
		lowcost[i] = G.arc[0][i];
	}
	lowcost[0] = 0;//初始化U={Vo}
	for (int i = 1; i < G.vertexNum; i++) {
		int k = SelectMin(G, lowcost);
		cout << 'V' << adjvex[k] << "->V" << k << endl;
		lowcost[k] = 0;
		for (int j = 0; j < G.vertexNum; j++) {
			if (lowcost[j] == -1) {
				lowcost[j] = G.arc[k][j];
				adjvex[j] = k;
			}
			if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {//更新U—V边权值
				lowcost[j] = G.arc[k][j];
				adjvex[j] = k;
			}
		}
	}
}
bool vistedDFS[MAXSIZE] = { 0 };//顶点的初始状态
template<class T>
void MGraph<T>::DFS(int v) {
	cout << vertex[v];
	vistedDFS[v] = 1;
	for (int j = 0; j < vertexNum; j++)//非连通图
		if (arc[v][j] != 0 && vistedDFS[j] == 0)
			DFS(j);
}

template<class T>
void MGraph<T>::BFS(int v) {
	bool visitedBFS[MAXSIZE] = { 0 };
	int queue[MAXSIZE];
	int f = 0, r = 0; //构造一个空队列
	cout << vertex[v];
	visitedBFS[v] = 1;
	queue[++r] = v;//V入队
	while (f != r) {//队列非空
		v = queue[++f];//队头元素出队
		for (int j = 0; j < vertexNum; j++) {
			if (arc[v][j] !=0 && visitedBFS[j] == 0) {//存在未访问过的临接点
				cout << vertex[j];
				visitedBFS[j] = 1;
				queue[++r] = j;//j入队 
			}
		}
	}
}

template<class T>
void MGraph<T>::Inititalize() {
	T val;
	cout << "Please enter each vertex's keywords:";
	for (int i = 0; i < vertexNum; i++) {//初始化顶点数组
		cin >> val;
		vertex[i] = val;
	}
	for (int i = 0; i < vertexNum; i++)//初始化邻接矩阵
		for (int j = 0; j < vertexNum; j++)
			arc[i][j] = 0;
 }
template<class T>
void MGraph<T>::CreateDG() {
	cout << "Enter the start and end points of each arc to build a DG:" << endl;
	int vhead, vtail;
	while (cin >> vhead >> vtail) {
		arc[vhead][vtail] = 1;
	}
}
template<class T>
void MGraph<T>::CreateWDG() {
	cout << "Enter the start and end points and weight of each arc to build a WDG:" << endl;
	int vhead, vtail, weight;
	while (cin >> vhead >> vtail >> weight) {
		arc[vhead][vtail] = weight;
	}
}
template<class T>
void MGraph<T>::CreateUDG() {
	cout << "Enter the start and end points of each arc to build an UDG:" << endl;
	int vhead, vtail;
	while (cin >> vhead >> vtail) {
		arc[vhead][vtail] = 1;
		arc[vtail][vhead] = 1;
	}
}
template<class T>
void MGraph<T>::CreateWUDG() {
	cout << "Enter the start and end points and weight of each arc to build a WUDG:" << endl;
	int vhead, vtail, weight;
	while (cin >> vhead >> vtail >> weight) {
		arc[vhead][vtail] = weight;
		arc[vtail][vhead] = weight;
	}
}
template<class T>
MGraph<T>::MGraph(int vertexnum, vertexType _kind):vertexNum(vertexnum),arcNum(9),kind(_kind){//构造函数初始化
	Inititalize();
	switch (kind){
	case DG:{
		CreateDG();    //构造一个有向图  
		break;
	}
	case WDG:{
		CreateWDG(); //构造一个带权有向图  
		break;
	}
	case UDG:{
		CreateUDG();    //构造一个无向图  
		break;
	}
	case WUDG:{
		CreateWUDG();   //构造一个带权无向图  
		break;
	}
	default:
		return;
	}
	//输出矩阵
	cout << "Print the adjacency matrix:" << endl;
	cout << "  ";
	for (int i = 0; i < vertexNum; i++)
		cout << vertex[i] << "  ";
	cout << endl;
	for (int i = 0; i < vertexNum; i++) {
		cout << vertex[i] << ' ';
		for (int j = 0; j < vertexNum; j++)
			cout << arc[i][j]<<' ';
		cout << endl;
	}
}

测试函数：

/********************************************************************************************************
1.测试函数每次只能选择一个
2.为测试方便，均采用节点为6的图，BFS和DFS测试选择t1(),最小生成图t2()
3.最小生成图测试参考数据：(未直接连通的边权值为-1）
0 1 46 0 2 19 0 3 34 0 4 -1 0 5 -1 1 2 25 1 3 -1 1 4 17 1 5 -1 2 3 -1 2 4 25 2 5 26 3 4 -1 3 5 12 4 5 38^Z
************************************************************************************************************/

#include "stdafx.h"
#include<iostream>
#include"MGraph.h"
using namespace std;
VEdge edgeList[MAX_EDGE];

void t1() {//测试DFS/BFS
	MGraph<int> m1(6, UDG);
	cout << "DFS: ";
	m1.DFS(0);
	cout << endl;
	cout << "BFS: ";
	m1.BFS(0);
	cout << endl;
}
void t2() {//测试普利姆和克鲁斯卡算法
	MGraph<int> m1(6, WUDG);
	Prime(m1);
	GenSortEdge(m1, edgeList);
	Kruskal(m1, edgeList);
}
int main(){
	int a;
	cout << "please enter 1 or 2 to choose your test's kind:";
	cin >> a;
	if (a == 1)
		t1();
	else 
		t2();
    return 0;
}

测试结果：