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

今天是读《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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏mathor

搜索(2)

1334
来自专栏开发与安全

算法:图的广度优先遍历(Breadth First Search)

图的遍历和树的遍历类似,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traverse Graph)。 图...

25510
来自专栏数据结构与算法

P1888 三角函数

题目描述 输入一组勾股数a,b,c(a≠b≠c),用分数格式输出其较小锐角的正弦值。(要求约分。) 输入输出格式 输入格式: 一行,包含三个数,即勾股数...

2877
来自专栏小樱的经验随笔

华中农业大学第五届程序设计大赛网络同步赛题解

A.Little Red Riding Hood ? B.Choosy in Food •F[i]:从第I个点到终点的期望步数 •F[i] = (F[i +...

3537
来自专栏有趣的Python

15-数据结构探险系列-图篇数据结构探险之图篇

图的存储结构:邻接矩阵(数组);邻接表(链表)有向; 十字链表(链表)有向;邻接多重表(链表)无向

1213
来自专栏决胜机器学习

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(九)——图的定义、存储与两种方式遍历 (原创内容,转载请注明来源,谢谢) 一、定义和术语 1、不同于线性结构和树,图是任意两个...

5927
来自专栏小樱的经验随笔

Gym 100952J&&2015 HIAST Collegiate Programming Contest J. Polygons Intersection【计算几何求解两个凸多边形的相交面积板子题

J. Polygons Intersection time limit per test:2 seconds memory limit per test:64 ...

2777
来自专栏数据结构与算法

洛谷P3327 [SDOI2015]约数个数和(莫比乌斯反演)

题目描述 设d(x)为x的约数个数,给定N、M,求 \sum^N_{i=1}\sum^M_{j=1}d(ij)∑i=1N​∑j=1M​d(ij) 输入输出格式 ...

2724
来自专栏专知

Numpy教程第2部分 - 数据分析的重要功能

【导读】Numpy是python数据分析和科学计算的核心软件包。 上次介绍了numpy的一些基础操作。例如如何创建一个array,如何提取array元素,重塑(...

4479
来自专栏编程

python学习笔记第三天:python之numpy篇!

此图只是为了封面而已,并非python女友 接下来要给大家介绍的系列中包含了Python在量化金融中运用最广泛的几个Library: numpy scipy p...

2515

扫码关注云+社区

领取腾讯云代金券