|
_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;
}
|
