CAJ | 학술논문

以消除无向连通图中构成环路的冗余边的算法为主线，引入并介绍了图形数据结构的逻辑结构和基本概念，通过对比分析图的几个常用存储结构的优缺点，确定选用邻接矩阵存储结构来存储无向连通图。详细分析如何利用近似Prim算法得到无向连通图的最小生成树，给出了算法的设计思路以及实现的方法和步骤，并给出通过广度优先搜索遍历实现该算法的C语言描述，最后对算法从时间复杂度和空间复杂度两个方面进行了评价。
이소제무향련통도중구성배로적용여변적산법위주선，인입병개소료도형수거결구적라집결구화기본개념，통과대비분석도적궤개상용존저결구적우결점，학정선용린접구진존저결구래존저무향련통도。상세분석여하이용근사Prim산법득도무향련통도적최소생성수，급출료산법적설계사로이급실현적방법화보취，병급출통과엄도우선수색편력실현해산법적C어언묘술，최후대산법종시간복잡도화공간복잡도량개방면진행료평개。
The key of this paper is the algorithm about eliminating the redundant edges constituting a loop in undirected con?nected graph. This paper introduces the logic structure patterns and the basic concepts of graph data structure, compares and analy?zes the advantages and disadvantages of several common storage structures, and then chooses the adjacency matrix storage structure to store the undirected connected graph. The paper analyzes in detail how to compute out the spanning tree of the undirected connect?ed graph through a specific algorithm approximating to the Prim algorithm, introduces the design ideas, implementation approaches and concrete steps of the algorithm, gives the algorithm implementation description of the breadth first search traversal in C lan?guage, and finally evaluates the algorithm from the two aspects of time complexity and space complexity.