邻接表和邻接矩阵实现拓扑排序

邻接表的实现

这个实现比某些C/C++数据结构书上的简洁, 我没有看别的代码, 只针对够用的需求;邻接表的实现使用了模板，用non-type template技巧塞入图的结点个数，为的不想用一个常量或者宏定义最大的vertex个数, 然后声明静态数组;用模板实现, 类的member method等成员定义需要放在.h文件中, 与类的声明放在一起. 这个地方我结结实实的摔了一跤，详见踩坑部分;拓扑排序算解释: 设定in_degree数组, 从边集和中, 设定好每个结点入度;对vertex number循环 查找入度为0的结点, 作为当前节点 若失败, 退出排序, 说明非DAG, 存在环; 处理当前节点出边影响到的节点的入度, 在in_degree数组中更新计数;= #ifndef __ADJ_GRAPH__ #define __ADJ_GRAPH__ #include <iostream> #include <vector> // 邻接表的边结点 struct ArchNode { int adj_vertex; // 和vertex node连接的点; ArchNode* next; }; // 邻接表的顶点结点 struct VertexNode { int vertex_id; ArchNode* first; ArchNode* tail; }; struct Arch { int beg_vnode_idx, end_vnode_idx; int weight; Arch(int i, int j, int w): beg_vnode_idx(i), end_vnode_idx(j), weight(w) {} Arch(const Arch& other) { if (this != &other) { beg_vnode_idx = other.beg_vnode_idx; end_vnode_idx = other.end_vnode_idx; weight = other.weight; } } std::pair<int, int> GetPair() { return std::make_pair(beg_vnode_idx, end_vnode_idx); } int GetWeight() { return weight; } }; enum GraphType { UDG, // 无向图; DG // 有向图; }; template <unsigned T> class AdjacentListGraph { public: AdjacentListGraph(GraphType graph_type, int e, int n = T); AdjacentListGraph(GraphType graph_type, int e, const std::vector<Arch>& arch_list); void CreateAdjacentList(GraphType g); void AddToArchList(Arch* arch) { arch_list_.push_back(arch); } void InsertArch(int vertex_idx, int adjacent_node_idx); void MakeArchList(const std::vector<Arch>& arch_list); void MakeArchList(const std::pair<int, int>*, size_t); bool TopologicalSort(); private: VertexNode* vertex_nodes_; std::vector<Arch*> arch_list_; int vertex_num_; int arch_num_; GraphType graph_type_; }; template <unsigned T> AdjacentListGraph<T>::AdjacentListGraph(GraphType graph_type, int e, int n) : vertex_num_(n), arch_num_(e), graph_type_(graph_type) { vertex_nodes_ = new VertexNode[vertex_num_]; for (int i = 0; i < vertex_num_; ++i) { vertex_nodes_[i].vertex_id = i + 1; vertex_nodes_[i].first = nullptr; vertex_nodes_[i].tail = nullptr; } if (arch_num_ <= 0) return; std::cout << "input the arch data: (v1, v2, weight)" << std::endl; int i, j, w; int count = 0; while (count++ < arch_num_) { std::cin >> i >> j >> w; Arch* arch = new Arch(i, j, w); AddToArchList(arch); } CreateAdjacentList(graph_type_); } template <unsigned T> AdjacentListGraph<T>::AdjacentListGraph(GraphType graph_type, int e, const std::vector<Arch>& arch_list) : vertex_num_(T), arch_num_(e), graph_type_(graph_type) { vertex_nodes_ = new VertexNode[vertex_num_]; for (int i = 0; i < vertex_num_; ++i) { vertex_nodes_[i].vertex_id = i + 1; vertex_nodes_[i].first = nullptr; vertex_nodes_[i].tail = nullptr; } if (arch_num_ <= 0) return; MakeArchList(arch_list); CreateAdjacentList(graph_type_); } template <unsigned T> void AdjacentListGraph<T>::MakeArchList(const std::vector<Arch>& arch_list) { for (auto archItem : arch_list) { auto arch = new Arch(archItem); AddToArchList(arch); } } template <unsigned T> void AdjacentListGraph<T>::MakeArchList(const std::pair<int, int>* arch_list, size_t size) { for (unsigned int i = 0; i < size; ++i) { auto arch = new Arch(arch_list[i].first, arch_list[i].second, 0); AddToArchList(arch); } } template <unsigned T> void AdjacentListGraph<T>::CreateAdjacentList(GraphType t) { for (auto arch : arch_list_) { auto pair = arch->GetPair(); // std::cout << "pair.first=" << pair.first << ", pair.second=" << pair.second; int head = pair.first, end = pair.second; InsertArch(head, end); if (t == UDG) { InsertArch(end, head); } } } template <unsigned T> void AdjacentListGraph<T>::InsertArch(int vertex_idx, int adjacent_node_idx) { ArchNode* a = new ArchNode{adjacent_node_idx, nullptr}; VertexNode& v = vertex_nodes_[vertex_idx - 1]; v.tail == nullptr ? v.first = a : v.tail->next = a; v.tail = a; } template <unsigned T> bool AdjacentListGraph<T>::TopologicalSort() { const size_t n = vertex_num_; int in_degree[n] = {0}; std::vector<int> result; // 设置in_degree数组, 设定每个点的入度 for (int i = 0; i < vertex_num_; ++i) { auto& m = vertex_nodes_[i]; ArchNode* x = m.first; if (x == nullptr) continue; int j = x->adj_vertex; ++in_degree[j - 1]; while ((x = x->next)) { j = x->adj_vertex; ++in_degree[j - 1]; } } int count = 0; while (count++ < vertex_num_) { // 查找入度为0的结点; int start_idx = -1; for (int j = 0; j < vertex_num_; ++j) { if (in_degree[j] == 0) { start_idx = j; break; } } if (start_idx == -1) break; result.push_back(start_idx); // 处理对当前结点出边影响的结点; ArchNode* a = vertex_nodes_[start_idx].first; while (a) { in_degree[a->adj_vertex - 1]--; a = a->next; } // 标记当前结点已经处理过; in_degree[start_idx] = -1; } if (count < vertex_num_) { std::cout << "不能完成拓扑排序, 存在环" << std::endl; return false; } std::cout << "Topological sort result is:"; for (auto it : result) { int k = it; std::cout << k + 1 << " "; } std::cout << std::endl; return true; } #endif

测试:

#include <iostream> #include <vector> #include "adj_graph.h" int main() { Arch dag_arches[] = { {1, 2, 0}, {1, 4, 0}, {2, 4, 0}, {2, 3, 0}, {3, 5, 0}, {4, 3, 0}, {4, 5, 0} }; AdjacentListGraph<5> dag(DG, sizeof(dag_arches), std::vector<Arch>(std::begin(dag_arches), std::end(dag_arches))); dag.TopologicalSort(); return 0; }

邻接矩阵的实现

使用模板需要把成员方法放在和模板声明的同一个编译单元, 不利于模块化; 邻接矩阵的实现用matrix_graph.h, matrix_graph.cc分开组织代码;

二维数组: 一个麻烦的但是可行的方法

由于需要在对象创建时刻确定vertex number; 在写代码时无法确定数组的维度, 我用void*引用vertex结点2维数组。在创建数组时用malloc返回2维int数组正确大小的内存空间, 把void* 转成int (*)[n][n]指向数组的指针，再根据边集的情况设定2维数组的每个元素(weight值); 每次使用void* 指针时, 需要把它转成int (*)[n][n], 例如在CreateADJMatrixGraph()和TopologicalSort()当中; void* matrix_ = malloc(sizeof(int) * n * n); // 转成指向二维数组的指针 int (matrix_arr*)[n][n] = static_cast<int (*)[n][n]>(matrix_arr); // *(*matrix_array + i) + j => 指到每个元素的指针; // 设定矩阵每个元素: *(*(*matrix_array + i) + j) = (archIt->second).GetWeight(); 后来在看到一本数据结构的文章时发现了一个简便的方法

二维数组第二个方法: 简便的形式

matrix_指针int** matrix int** matrix_ = new int*[n]; for (int i = 0; i < n; i++) { matrix_[i] = new int[n]; } // 这样在使用时不需要转换类型, 可以直接使用matrix[i][j]的形式; matrix[i][j] = 1; 以下使用了第一种形式的代码 // matrix_graph.h #include <iostream> #include <unordered_map> enum GraphType { DG, // 有向图 UDG // 无向图 }; struct Arch { int beg_vertex_idx; int end_vertex_idx; int weight; Arch(int i, int j, int w): beg_vertex_idx(i), end_vertex_idx(j), weight(w) {} Arch(const Arch& other) { if (this != &other) { beg_vertex_idx = other.beg_vertex_idx; end_vertex_idx = other.end_vertex_idx; weight = other.weight; } } std::pair<int, int> GetPair() { return std::make_pair(beg_vertex_idx, end_vertex_idx); } int GetWeight() { return weight; } }; struct VertexNode { int vertex_id; }; class ADJMatrixGraph { public: ADJMatrixGraph(GraphType type, const int vertex_num, struct Arch arch_list[], const int arch_num); void print_matrix(); void TopologicalSort(); private: void AddToArchList(Arch arch) { std::pair<int, int> arch_pair = arch.GetPair(); std::string s = std::to_string(arch_pair.first - 1) + "_" + std::to_string(arch_pair.second - 1); arch_list_.insert(std::make_pair(s, arch)); } void MakeArchList(struct Arch arch_list[], size_t arch_num); void CreateADJMatrixGraph(GraphType); GraphType graph_type_; int vertex_num_; int arch_num_; VertexNode* vertex_nodes_; std::unordered_map<std::string, Arch> arch_list_; void* matrix_; }; // matrix_graph.cc #include <stdio.h> #include <vector> #include "matrix_graph.h" ADJMatrixGraph::ADJMatrixGraph(GraphType type, const int vertex_num, struct Arch arch_list[], const int arch_num): graph_type_(type), vertex_num_(vertex_num), arch_num_(arch_num), vertex_nodes_(new VertexNode[vertex_num]) { MakeArchList(arch_list, arch_num); CreateADJMatrixGraph(type); } void ADJMatrixGraph::MakeArchList(struct Arch arch_list[], size_t arch_num) { for (unsigned int i = 0; i < arch_num; ++i) { auto arch = arch_list[i]; AddToArchList(arch); if (graph_type_ == UDG) { // TODO(cangpeng): to handle symmetrics arch for UDG } } } void ADJMatrixGraph::print_matrix() { int n = vertex_num_; int (*matrix_arr)[n][n] = static_cast<int (*)[n][n]>(matrix_); for (int i = 0; i < n; ++i) { std::cout << "\ni=" << i << ":"; for (int j = 0; j < n; ++j) { std::cout << *(*(*matrix_arr + i) + j) << " "; } } std::cout << std::endl; } void ADJMatrixGraph::CreateADJMatrixGraph(GraphType type) { int n = vertex_num_; void* matrix = malloc(sizeof(int) * n * n); int (*matrix_arr)[n][n] = static_cast<int (*)[n][n]>(matrix); for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { std::string s = std::to_string(i) + "_" + std::to_string(j); auto archIt = arch_list_.find(s); if (archIt != arch_list_.end()) { *(*(*matrix_arr + i) + j) = (archIt->second).GetWeight(); } else { *(*(*matrix_arr + i) + j) = 0; } } } matrix_ = matrix; } void ADJMatrixGraph::TopologicalSort() { const size_t n = vertex_num_; int in_degree[n] = {0}; std::vector<int> result; int (*matrix)[n][n] = static_cast<int (*)[n][n]>(matrix_); // 设定in_degree数组, 设定入度; for (unsigned int i = 0; i < n; ++i) { for (unsigned int j = 0; j < n; ++j) { // std::cout << "matrix:" << i << ", " << j << ":" // << *(*(*matrix + i) + j) << ", " << matrix[i][j] << std::endl; if (*(*(*matrix + i) + j) > 0) { in_degree[j]++; } } } unsigned int count = 0; while (count++ < n) { // 查找入度为0的节点 int start_idx = -1; for (unsigned int j = 0; j < n; ++j) { if (in_degree[j] == 0) { start_idx = j; break; } } // 没有入度为0的结点, 非DAG, 可能存在环; if (start_idx == -1) break; result.push_back(start_idx); // 处理当前结点的出边 for (unsigned int k = 0; k < n; ++k) { if (*(*(*matrix + start_idx) + k) > 0) { in_degree[k]--; } } in_degree[start_idx] = -1; } if (count < n) { std::cout << "非DAG, 可能存在环" << std::endl; return false; } std::cout << "Topological sort result is:"; for (auto it : result) { int k = it; std::cout << k + 1 << " "; } std::cout << std::endl; return true; }

测试

#include "matrix_graph.h" int main() { struct Arch dag_arches[] = { {1, 2, 1}, {1, 4, 1}, {2, 4, 1}, {2, 3, 1}, {3, 5, 1}, {4, 3, 1}, {4, 5, 1} }; ADJMatrixGraph matrix_graph(DG, 5, dag_arches, 7); matrix_graph.print_matrix(); matrix_graph.TopologicalSort(); return 0; }

踩坑

用nontype template实现邻接表。 注意template的类实现，在真正出创建template实例的对象之前，不会真正实例化template类, 也就没有符号表中某些元素, 如template类的构造函数等成员函数; 只有在创建template类的定义时, 才会在.o文件中出现该符号; 忽略此点, 很容易出现不理解的undefined reference to xxx错误;

并不是常见的LD_LIBRARY等so文件搜索路径的问题;用nm看, 符号确实不出现在o文件中, 但确实源代码中却有成员定义;在调用template .h文件的外部测试文件中，有时必须将需要其他header引入, 即使在template的实现h文件中已经引入过;

由于以上此点约束, 使用template类常常只有把全部实现写在.h文件中; 这样不利于模块化代码;

邻接矩阵实现使用malloc; 在gdb中输出using过的type是有问题的; 需要使用原始的指针定义;

结果

优化

查找入度为0的节点的查找过程O(n)的, 可以最小堆, 每次在取得入度为0的节点时, 取走堆顶元素; 调整堆把下一个最小的为0的节点调整到堆顶; 增加的时间是调整堆的开销O(logN), 而查找入度0的节点则是O(1); (todo)