一：通用图结构
#ifndef _GRAPH_H
#define _GRAPH_H
#include <iostream>
#include <string.h>
#include <assert.h>
#include <queue>
using namespace::std;
#define MAX_COST 0x7FFFFFFF //花费无限大设为整型最大值
///////////////////////////////////////////////////////////////////////////////////////////
//通用图结构
template <typename T, typename E>
class graph{
public:
bool is_empty()const;
bool is_full()const;
int get_numvertices()const; //当前顶点数
int get_numedges()const; //当前边数
public:
virtual bool insert_vertex(const T&) = 0; //插入顶点
virtual bool insert_edge(const T&, const T&, E) = 0; //插入边
virtual int get_firstneighbor(const T&)const = 0; //得到第一个邻接顶点
virtual int get_nextneighbor(const T&, const T&)const = 0; //某邻接顶点的下一个邻接顶点
virtual void print_graph()const = 0;
virtual int get_vertex_index(const T&)const = 0; //得到顶点序号
virtual void depth_first(const T&) = 0;
virtual void broad_first(const T&) = 0;
virtual void min_spantree_kruskal() = 0;
virtual void min_spantree_prim(const T&) = 0;
protected:
static const int VERTICES_DEFAULT_SIZE = 10; //默认图顶点数
int max_vertices;
int num_vertices;
int num_edges;
};
template <typename T, typename E>
bool graph<T, E>::is_empty()const
{
return num_edges == 0;
}
template <typename T, typename E>
bool graph<T, E>::is_full()const
{
return num_vertices >= max_vertices
|| num_edges >= max_vertices*(max_vertices-1)/2; //判满，分为顶点满和边满
}
template <typename T, typename E>
int graph<T, E>::get_numvertices()const
{
return num_vertices;
}
template <typename T, typename E>
int graph<T, E>::get_numedges()const
{
return num_edges;
}
///////////////////////////////////////////////////////////////////////////////////////////
#define VERTICES_DEFAULT_SIZE graph<T, E>::VERTICES_DEFAULT_SIZE
#define num_vertices graph<T, E>::num_vertices
#define num_edges graph<T, E>::num_edges
#define max_vertices graph<T, E>::max_vertices
///////////////////////////////////////////////////////////////////////////////////////////
#endif /*graph.h*/
二：邻接矩阵图结构
#pragma once
#include "graph.h"
//图的邻接矩阵表示法
template <typename T, typename E>
class graph_mtx : public graph<T, E>{
public:
graph_mtx(int);
~graph_mtx();
public:
bool insert_vertex(const T&);
bool insert_edge(const T&, const T&, E);
int get_firstneighbor(const T&)const;
int get_nextneighbor(const T&, const T&)const;
int get_vertex_index(const T&)const;
T& get_vertex_symbol(const int)const;
void print_graph()const;
void depth_first(const T&);
void broad_first(const T&);
void min_spantree_kruskal();
void min_spantree_prim(const T&);
protected:
void depth_first(const T&, bool *);
private:
T* vertices_list; //顶点线性表
E **edge; //内部矩阵
};
template <typename T, typename E>
graph_mtx<T, E>::graph_mtx(int sz = VERTICES_DEFAULT_SIZE)
{
max_vertices = sz > VERTICES_DEFAULT_SIZE ? sz
: VERTICES_DEFAULT_SIZE;
vertices_list = new T[max_vertices];
edge = new int*[max_vertices]; //动态申请二维数组
for(int i=0; i<max_vertices; ++i){
edge[i] = new int[max_vertices];
}
for(int i=0; i<max_vertices; ++i)
for(int j=0; j<max_vertices; ++j){
if(i != j)
edge[i][j] = MAX_COST;
else
edge[i][j] = 0;
}
num_vertices = 0;
num_edges = 0;
}
template <typename T, typename E>
graph_mtx<T, E>::~graph_mtx()
{
for(int i=0; i<max_vertices; ++i)
delete []edge[i]; //分别析构，再总析构
delete edge;
delete []vertices_list;
}
template <typename T, typename E>
bool graph_mtx<T, E>::insert_vertex(const T& vert)
{
if(this->is_full()) //派生类函数调用父类函数，用this或加作用域
return false;
vertices_list[num_vertices++] = vert;
return true;
}
template <typename T, typename E>
bool graph_mtx<T, E>::insert_edge(const T& vert1, const T& vert2, E cost = MAX_COST)//由于权值存在默认值，get_neighbor的操作需判断是否等于MAX_COST，否则不能正常取得邻接顶点
{
if(this->is_full()) //判满
return false;
int index_v1 = get_vertex_index(vert1); //得到顶点序号
int index_v2 = get_vertex_index(vert2);
if(index_v1 == -1 || index_v2 == -1 )
return false;
edge[index_v1][index_v2] = edge[index_v2][index_v1] = cost; //无向图
++num_edges;
return true;
}
template <typename T, typename E>
int graph_mtx<T, E>::get_firstneighbor(const T& vert)const
{
int index = get_vertex_index(vert);
if(index != -1){
for(int i=0; i<num_vertices; ++i){
if(edge[index][i] != 0 && edge[index][i] != MAX_COST) //加上判断MAX_COST
return i;
}
}
return -1;
}
template <typename T, typename E>
int graph_mtx<T, E>::get_nextneighbor(const T& vert1, const T& vert2)const
{
int index_v1 = get_vertex_index(vert1);
int index_v2 = get_vertex_index(vert2);
if(index_v1 != -1 && index_v2 != -1){
for(int i=index_v2+1; i<num_vertices; ++i){
if(edge[index_v1][i] != 0 && edge[index_v1][i] != MAX_COST)
return i;
}
}
return -1;
}
template <typename T, typename E>
int graph_mtx<T, E>::get_vertex_index(const T& vert)const
{
for(int i=0; i<num_vertices; ++i){
if(vertices_list[i] == vert)
return i;
}
return -1;
}
template <typename T, typename E>
T& graph_mtx<T, E>::get_vertex_symbol(const int index)const
{
assert(index >= 0 && index < this->get_numvertices());
//assert(index >= 0 && index < num_vertices); //error，由于num_vertices本身是我们用宏替换父类该元素，在这里使用会出现双重宏
return vertices_list[index];
}
template <typename T, typename E>
void graph_mtx<T, E>::print_graph()const
{
if(this->is_empty()){
cout << "nil graph" << endl; //空图输出nil
return;
}
for(int i=0; i<num_vertices; ++i){
cout << vertices_list[i] << " ";
}
cout << endl;
for(int i=0; i<num_vertices; ++i){
for(int j=0; j<num_vertices; ++j){
if(edge[i][j] != MAX_COST)
cout << edge[i][j] << " ";
else
cout << '@' << " "; //若权值无限大，以@代替
}
cout << vertices_list[i] << endl;
}
}
template <typename T, typename E>
void graph_mtx<T, E>::depth_first(const T& vert) //深度优先，认准一条路往死走，无路可走再回退
{
int num = this->get_numvertices();
bool *visited = new bool[num];
memset(visited, 0, sizeof(bool)*num); //首先全部赋值为假，遍历过后为真，防止图死循环
depth_first(vert, visited);
cout << "end.";
delete []visited;
}
template <typename T, typename E>
void graph_mtx<T, E>::depth_first(const T& vert, bool *visited)
{
cout << vert << "-->";
int index = get_vertex_index(vert);
visited[index] = true;
int neighbor_index = get_firstneighbor(vert);
while(neighbor_index != -1){
if(!visited[neighbor_index])
depth_first(get_vertex_symbol(neighbor_index), visited); //递归
neighbor_index = get_nextneighbor(vert,
get_vertex_symbol(neighbor_index));
}
}
template <typename T, typename E>
void graph_mtx<T, E>::broad_first(const T& vert)
{
int num = this->get_numvertices();
bool *visited = new bool[num];
int index = get_vertex_index(vert);
assert(index != -1);
memset(visited, 0, sizeof(bool)*num);
queue<int> que; //通过队列，将元素以次入队
que.push(index);
cout << vert << "-->";
visited[index] = true;
while(!que.empty()){
int index_tmp = que.front();
que.pop();
int neighbor_index = get_firstneighbor(get_vertex_symbol(index_tmp));
while(neighbor_index != -1){
if(!visited[neighbor_index]){
cout << get_vertex_symbol(neighbor_index) << "-->";
visited[neighbor_index] = true; //遍历过后为真，防止图死循环
que.push(neighbor_index);
}
neighbor_index = get_nextneighbor(get_vertex_symbol(index_tmp),
get_vertex_symbol(neighbor_index));
}
}
cout << "end.";
delete []visited;
}
//////////////////////////////////////////////////////////////////
//min_spactree_kruskal
template <typename T, typename E>
struct _mst_edge{ //最小生成树边的结构体,<begin, end>为一组边，cost为花费
int begin;
int end;
E cost;
};
template <typename T, typename E>
int compare(const void* vp1, const void* vp2)
{
return (*(_mst_edge<T, E> *)vp1).cost - (*(_mst_edge<T, E> *)vp2).cost;
}
bool _is_same(int *father, int begin, int end) //判断是否在同一张子图中
{
while(father[begin] != begin)
begin = father[begin];
while(father[end] != end)
end = father[end];
return begin == end; //以最后一个元素是否存在父子关系判断
}
void mark_same(int *father, int begin, int end)
{
while(father[begin] != begin)
begin = father[begin];
while(father[end] != end)
end = father[end];
father[end] = begin; //让最后一个元素连接起来，使它们成为同一子图的元素
}
template <typename T, typename E>
void graph_mtx<T, E>::min_spantree_kruskal()
{
int num = this->get_numvertices();
_mst_edge<T, E> *mst_edge = new _mst_edge<T, E>[num*(num-1)/2];
int k = 0;
for(int i=0; i<num; ++i)
for(int j=i+1; j<num; ++j){ //建立有效边结构体数组，从i+1开始，直接统计矩阵1/2边数，不会产生重复
if(edge[i][j] != MAX_COST){
mst_edge[k].begin = i;
mst_edge[k].end = j;
mst_edge[k].cost = edge[i][j];
++k;
}
}
qsort(mst_edge, k, sizeof(_mst_edge<T, E>), compare<T, E>); //调用快速排序函数
int *father = new int[num]; //初始化使所有元素的父指向自己
for(int i=0; i<num; ++i)
father[i] = i;
for(int i=0; i<num; ++i)
if(!_is_same(father, mst_edge[i].begin, mst_edge[i].end)){ //判断是否在同一张子图中
cout << get_vertex_symbol(mst_edge[i].begin) << "-->"
<< get_vertex_symbol(mst_edge[i].end)
<< ":" << mst_edge[i].cost << endl;
mark_same(father, mst_edge[i].begin, mst_edge[i].end); //加入后做标记
}
delete []father;
delete []mst_edge;
}
//////////////////////////////////////////////////////////////////
//min_spantree_prim
template <typename T, typename E>
void graph_mtx<T, E>::min_spantree_prim(const T& vert)
{
int num = this->get_numvertices();
int *lowcost = new int[num]; //最小花费数组
int *mst = new int[num]; //起始位置数组 <mst[i], i> 为一组边，起始为mst[i]
int index = get_vertex_index(vert);
assert(index != -1);
for(int i=0; i<num; ++i){ //初始化使每个元素默认花费是以起始边为vert作为基准，所以mst[i]对应下标即为vert的下标index
if(edge[index][i] != 0){
lowcost[i] = edge[index][i];
mst[i] = index;
}
else
lowcost[i] = 0;
}
for(int i=0; i<num-1; ++i){ //循化，num个元素共有num-1条边
int min = MAX_COST;
int min_index = -1;
for(int j=0; j<num; ++j){
if(lowcost[j] != 0 && lowcost[j] < min){ //找出最小花费
min = lowcost[j];
min_index = j;
}
}
cout << get_vertex_symbol(mst[min_index]) << "-->"
<< get_vertex_symbol(min_index) << ":" << min << endl;
lowcost[min_index] = 0; //花费为0，相当于加入已生成树中
for(int j=0; j<num; ++j){ //循环，如果某元素到新元素的花费比默认花费小，那么就更新它，
int cost = edge[min_index][j];//下次再循环到上面找最小花费时，就可能找到更新的这个最小花费，这就相当于每次加入新元素后
if(cost < lowcost[j]){ //其他顶点挑出与已生成树所有顶点的花费最小值，并更新
lowcost[j] = cost;
mst[j] = min_index;
}
}
}
delete []lowcost;
delete []mst;
}
三：测试部分
测试用图：
测试代码：
#include "graph.h"
#include "graph_mtx.h"
#define VERTEX_SIZE 4
int main()
{
graph_mtx<char, int> gm;
gm.insert_vertex('A');
gm.insert_vertex('B');
gm.insert_vertex('C');
gm.insert_vertex('D');
gm.insert_vertex('E');
gm.insert_vertex('F');
gm.insert_edge('A', 'B', 6);
gm.insert_edge('A', 'C', 1);
gm.insert_edge('A', 'D', 5);
gm.insert_edge('B', 'C', 5);
gm.insert_edge('B', 'E', 3);
gm.insert_edge('C', 'D', 5);
gm.insert_edge('C', 'F', 4);
gm.insert_edge('D', 'F', 2);
gm.insert_edge('E', 'F', 6);
gm.insert_edge('C', 'E', 6);
gm.print_graph();
cout << "depth_first traverse:" << endl;
gm.depth_first('A');
cout << endl;
cout << "broad_first traverse:" << endl;
gm.broad_first('A');
cout << endl;
cout << "min_spantree_kruskal :" << endl;
gm.min_spantree_kruskal();
cout << "min_spantree_prim :" << endl;
gm.min_spantree_prim('A');
return 0;
}
测试结果：
