一：通用圖結構
#ifndef _GRAPH_H
#define _GRAPH_H
#include
#include
#include
#include
using namespace::std;
#define MAX_COST 0x7FFFFFFF //花費無限大設為整型最大值
///////////////////////////////////////////////////////////////////////////////////////////
//通用圖結構
template
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
bool graph::is_empty()const
{
return num_edges == 0;
}
template
bool graph::is_full()const
{
return num_vertices >= max_vertices
|| num_edges >= max_vertices*(max_vertices-1)/2; //判滿，分為頂點滿和邊滿
}
template
int graph::get_numvertices()const
{
return num_vertices;
}
template
int graph::get_numedges()const
{
return num_edges;
}
///////////////////////////////////////////////////////////////////////////////////////////
#define VERTICES_DEFAULT_SIZE graph::VERTICES_DEFAULT_SIZE
#define num_vertices graph::num_vertices
#define num_edges graph::num_edges
#define max_vertices graph::max_vertices
///////////////////////////////////////////////////////////////////////////////////////////
#endif /*graph.h*/
二：鄰接矩陣圖結構
#pragma once
#include "graph.h"
//圖的鄰接矩陣表示法
template
class graph_mtx : public graph{
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
graph_mtx::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
graph_mtx::~graph_mtx()
{
for(int i=0; i
bool graph_mtx::insert_vertex(const T& vert)
{
if(this->is_full()) //派生類函數調用父類函數，用this或加作用域
return false;
vertices_list[num_vertices++] = vert;
return true;
}
template
bool graph_mtx::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
int graph_mtx::get_firstneighbor(const T& vert)const
{
int index = get_vertex_index(vert);
if(index != -1){
for(int i=0; i
int graph_mtx::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
int graph_mtx::get_vertex_index(const T& vert)const
{
for(int i=0; i
T& graph_mtx::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
void graph_mtx::print_graph()const
{
if(this->is_empty()){
cout << "nil graph" << endl; //空圖輸出nil
return;
}
for(int i=0; i
void graph_mtx::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
void graph_mtx::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
void graph_mtx::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 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
struct _mst_edge{ //最小生成樹邊的結構體,為一組邊，cost為花費
int begin;
int end;
E cost;
};
template
int compare(const void* vp1, const void* vp2)
{
return (*(_mst_edge *)vp1).cost - (*(_mst_edge *)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
void graph_mtx::min_spantree_kruskal()
{
int num = this->get_numvertices();
_mst_edge *mst_edge = new _mst_edge[num*(num-1)/2];
int k = 0;
for(int i=0; i), compare); //調用快速排序函數
int *father = new int[num]; //初始化使所有元素的父指向自己
for(int i=0; i
void graph_mtx::min_spantree_prim(const T& vert)
{
int num = this->get_numvertices();
int *lowcost = new int[num]; //最小花費數組
int *mst = new int[num]; //起始位置數組 為一組邊，起始為mst[i]
int index = get_vertex_index(vert);
assert(index != -1);
for(int i=0; i
三：測試部分
測試用圖：
測試代碼：
#include "graph.h"
#include "graph_mtx.h"
#define VERTEX_SIZE 4
int main()
{
graph_mtx 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;
}
測試結果：
