首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >《python算法教程》Day2 - 图和树的基本数据结构图树

《python算法教程》Day2 - 图和树的基本数据结构图树

作者头像
billyang916
发布2018-05-02 10:27:36
1.1K0
发布2018-05-02 10:27:36
举报
文章被收录于专栏:python读书笔记python读书笔记

今天是读《python算法教程》的第2天,读书笔记内容为用python实现图和树的基本数据结构。

图的基本数据结构有两种,分别为邻接列表和邻接矩阵。 现根据下图通过python实现邻接列表和邻接矩阵,

图.jpg

代码如下:

#图的基本数据结构及python的实现形式

#邻接列表
#无权邻接列表
a,b,c,d,e,f=range(6)
#主容器、节点结构均为列表
ug1=[
    [b,c,d,f],
    [f],
    [d,e,f],
    [e],
    [f],
    [e]
]
print("在ug1中,节点a的邻接点数量为",len(ug1[a]))
print("在ug1中,节点c是邻接节点a",c in ug1[a])

#主容器为列表,节点结构为set类型
ug2=[
    {b,c,d,f},
    {f},
    {d,e,f},
    {e},
    {f},
    {e}
]
print("\n在ug2中,节点a的邻接点数量为",len(ug1[a]))
print("在ug2中,节点c是否邻接节点a",c in ug1[a])

#主要结构为字典,节点结构为set类型,此种结构无需定义索引
ug3={
    "a":{"b","c","d","f"},
    "b":{"f"},
    "c":{"def"},
    "d":{"e"},
    "e":{"f"},
    "f":{"e"}
}
print("\n在ug3中,节点a的邻接点数为",len(ug3["a"]))
print("在ug3中,节点c是否邻接节点a","c" in ug3["a"])


#加权临界列表
#主结构为列表,系节点结构为字典
wg1=[
    {b:1,c:2,d:4,f:5},
    {f:3},
    {e:2,f:3},
    {e:2},
    {f:2},
    {e:3}
]

print("\n在wg1中,节点a的邻接点数量为",len(wg1[a]))
print("在wg1中,节点c是否邻接节点a",c in wg1[a].keys())
print("在wg1中,节点a与节点f的边的权重为",wg1[a][f])


#邻接矩阵d
#无权邻接矩阵
uam=[
    [0,1,1,1,0,1],
    [0,0,0,0,0,1],
    [0,0,0,1,1,1],
    [0,0,0,0,1,0],
    [0,0,0,0,0,1],
    [0,0,0,0,1,0]
]
print("\n在uam中,节点a的邻接点数量为",sum(1 for ele in uam[a] if ele>0))
print("在uam中,节点c是否为节点a的邻接点",uam[a][c]>0)

#加权邻接矩阵,此处将没有邻接的两个节点的边的权重定义为-1
wam=[
    [-1,1,2,4,-1,5],
    [-1,-1,-1,-1,-1,3],
    [-1,-1,-1,-1,2,3],
    [-1,-1,1,-1,-1],
    [-1,-1,-1,-1,-1,2],
    [-1,-1,-1,-1,3,-1]
]
print("\n在wam中,节点a的邻接点数量为",sum(1 for ele in wam[a] if ele>-1))
print("s在wam中,节点c的是否为节点a的邻接点",wam[a][c]>-1)

树可视为图的一种特殊结构,但图也有其特殊性。 以下通过python实现树的数据结构

#树的基本数据结构及python的实现形式

#套嵌列表,每一层的节点索引按从上到下的顺序从0开始进行编号

t1=[
    ["e","f"],
    ["h","i",["l","m"]],
    ["k"]
]


#自定义类:多路搜索树
class tree:
    def __init__(self,value,child=None,next=None):
        self.value=value
        self.child=child
        self.next=next
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018.04.05 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档