回 帖 发 新 帖 刷新版面

主题:[讨论]带权图的邻接矩阵与邻接表哪个好?希望参加过ACM的高手给予解答

我是新手,最近看了些图论的算法,做了几道相关的题目,发现在建带权图时,按照书上讲的方法,要按照INPUT要求的格式输入不论用邻接矩阵还是邻接表都好麻烦,不知有没有什么比较合理简单的方法,而且要考虑到时间复杂度问题。
如建立如下图:          
                        4           1 
                 A ----------- C ------- E
                 |             |
               2 |             |1
                 |             |
                 |             |
                 B             D

    
要求INPUT格式(顶点A 与A相邻的点有2个 B与A相邻 w(A,B)=2.....):
A 2 B 2 C 4
B 1 A 2
C 3 A 4 D 1 E 1
D 1 C 1
E 1 C 1     

请问这图要怎么建比较合理

回复列表 (共3个回复)

沙发

这个建邻接表不是很容易的事吗?

按顺序结点下来,每个结点有m个相邻结点,给他们建边就可以了。

板凳

用邻接表好?可邻接表建好后,在之后的使用中有时会很不方便的...

3 楼

这当然要具体问题具体分析了,各有各的优势

其实建邻接矩阵也是很容易的,只是给数组赋个值而已

我来回复

您尚未登录,请登录后再回复。点此登录或注册