|
一：通用图结构
#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 |