python 数据结构篇
在众多编程语言里，数据结构与算法都可以说是至关重要的基础。但是对于python而言，因为其本身就是用C实现的，其速度和效率本身较低，因而pyhon没有像其他语言那样那么重视数据结构与算法（python最引以为傲的应该是其功能强大而丰富的各种库和模块）。对于很多像我一样的新手小白，时间复杂度似乎也不是硬要求，实现功能就行了。本节我们主要介绍用python实现数据结构。
对于数据结构，我们将采用以下的思路进行学习：
一、定义对象、节点
1.线性结构：
数组、链表、队列、栈
2.非线性结构：
树、堆、图
二、实现节点之间的互联
在节点属性中增加指针
三、对象由某一节点处开始的遍历
1.线性结构
1）单向遍历
2）双向遍历
2.非线性结构
1）DFS（深度优先搜索）
2）BFS（广度优先搜索）
四、基本操作方法
1.增加节点
2.返回节点数量
3.由遍历结果构建对象
目录
一、线性数据结构（一对一）
1.数组
python使用其内置的模块array实现数组，python的数组就和C语言一样精简而高效。
1）构造一个数组对象
array.array(typecode[, initializer])
# 例：构造一个空的int类型数组
arr = array('i')
arr = array('i', [0, 1, 2, 3, 4, 6, 7, 8, 9, 100])由于python没有对于变量声明的要求，所以在创建数组时需要一个类型代码字符标识该数组的数据类型，这样数组才能像C语言里的数组一样操作。
2）查找数组信息
array.typecode用于创建数组的类型代码字符。
array.typecodes包含所有可用类型代码的字符串。即'bBuhHiIlLqQfd'
array.itemsize内部表示中一个数组项的字节长度。
array.index(x)方法返回x 在数组中第一次出现的下标, 下标从零开始,如果没有找到该元素会报异常.
array.buffer_info() 返回一个表示当前数组存储信息的元组(address, length)
array.count(x)返回 x 在数组中出现的次数,没有该元素则返回03）删除操作
array.remove(element)
element 是要删除的元素, 该方法会删除第一次出现的元素, 如果有多次出现, 不会删除。
如果删除的元素的不在 array 中, 则会抛异常
array.pop()
删除元素,默认删除下标-1 的元素, 也可以指定删除的位置,并返回被删除的元素4）添加操作
array.insert (i,v)
i 是索引位置, v 是插入的元素
array.append(x)
默认从末尾追加元素, 在数组尾部添加元素x
array.extend(可迭代对象)
通过一个可迭代对象添加元素
array.fromlist (list)
从一个列表中添加元素到数组5）转换操作
array.tolist()
把array对象转换成list
array.frombytes(s)
把bytes转换成array对象
array.tobytes()
把array对象转换成bytes6）文件操作
array.fromfile(f, n)
从f中读取n个元素, 如果n> file中的个数,会报异常.
array.tofile(f)
把array对象写到文件f中. 7)排序
array.sorted()排序数组，参数同可迭代对象里的sorted()
array.reverse()反转数组由以上的操作方法可知，python中的数组不仅可以像C语言中的数组一样进行操作，还支持像python中的可迭代对象一样的操作，以及一些其他的方法。
但是数组只能存储相同类型的数据，而列表可以存储不同类型的数据。而数组的存储效率和访问速度要快于列表。因此读者要根据实际情况适当选择。
2.链表
链表在python中使用类（相当于C中的结构）实现链表，实现方法也同C语言一样，但是python中没有指针的概念，于是就采用嵌套的方式，将一个实例赋给指针域，效果就同指针一样。但是同C一样，这样的做法，需要实例化对象起指针的作用，这样会降低数据的存储密度。
1）单向链表
#定义结点：
#数据域：item 存储节点上的信息
#指针域：next 存储下一个节点的变量信息（可以理解为C里面的指针）
class node():
def __init__(self,item):
self.item=item
self.next=None
#定义单链表
class SingleLinkedList():
def __init__(self):
self.head=None #存储头结点（指向第一个节点）
def add(self,item):#向链表头部中加入元素item
t=node(item)
t.next=self.head
self.head=t
def append(self,item):#向链表尾部中加入元素item
t=node(item)
if self.head==None:
self.head=t
else:
m=self.head
while m.next:
m=m.next
m.next=t
def insert(self,index,item):#向链表索引为index处中加入元素item
if index==0:
self.add(item)
elif index>=self.size():
self.append(item)
else:
t=node(item)
c=self.head
i=0
while i<index-1:
c=c.next
i+=1
t.next=c.next
c.next=t
def delete(self,item):#删除链表中的元素item
m=self.head
if m==None:
return
elif m.item==item:
self.head=m.next
del m
else:
while m.next.item!=item:
m=m.next
m.next=m.next.next
def pop(self):#删除链表尾部的元素
if self.head==None:
return
else:
m=self.head
while m.next.next:
m=m.next
r=m.next.item
del m.next
m.next=None
return r
def isempty(self):#判断链表是否为空
return self.head==None
def size(self):#返回链表的元素数量
s=0
t=self.head
while t:
t=t.next
s+=1
return s
def printall(self):#遍历链表所有的元素
t=self.head
while t:
print(t.item,end=" ")#遍历操作：打印该元素
t=t.next2）双向链表
由于单向链表只能访问当前节点的下一个节点，于是引出双向链表，便于访问上一个节点。同样，这样会增加实例化对象，进一步降低存储密度。
#定义节点：
class node():
def __init__(self,item):
self.item=item#数据域
self.next=None#指针域：指向下一个节点
self.prev=None#指针域：指向上一个节点
#定义双向链表
class DLinkList():
def __init__(self):
self.head=None#头结点
def size(self):#返回链表中元素数量
s=0
m=self.head
while m.next:
s+=1
m=m.next
return s
def isempty(self):#判断链表是否为空
return self.head==None
def append(self,item):#在链表尾部添加元素item
t=node(item)
m=self.head
if m==None:
self.head=t
return
else:
while m.next:
m=m.next
m.next=t
t.prev=m
def add(self,item):#在链表头部添加元素item
t=node(item)
m=self.head
if m==None:
self.head=t
return
else:
t.next=m
m.prev=t
self.head=t
def insert(self,index,item):#在链表索引index处添加元素item
t=node(item)
m=self.head
if m==None:
self.head=t
return
elif index+1>self.size():
self.append(item)
else:
i=0
while i<index:
m=m.next
i+=1
t.next=m
t.prev=m.prev
if i==0:
m.prev=t
self.head=t
else:
m.prev.next=t
m.prev=t
def pop(self):#删除链表尾部的元素
m=self.head
if m==None:
return
while m.next.next:
m=m.next
r=m.next
m.next=None
return r.item
def delete(self,item):#删除链表中的item元素
m=self.head
if m==None:
return
elif m.next==None:
self.head=None
else:
while m.item!=item:
m=m.next
if m.next==None:
m.prev.next=None
elif m.prev==None:
self.head=m.next
else:
m.next.prev=m.prev
m.prev.next=m.next
del m
def find(self,item):#查找链表中item的索引位置
m=self.head
s=0
while m:
if m.item==item:
s+=1
m=m.next
return s
def printall(self):#遍历所有节点
m=self.head
while m:
print(m.item,end=" ")#遍历操作：打印
m=m.next3）双向循环链表
上面的双向链表同样也只能从头到尾的或者从尾到头的访问，这样会增加访问的时间复杂度。为了提高访问效率，设置双向循环链表，存储密度同双向链表一样，但是会增加函数定义时的麻烦。
双向循环链表的实现基本同双向链表一样，不同的是双向循环链表的头结点需要和尾节点相连，这样才能达到循环的作用。（部分方法在实现时，可以利用循环的特点简化操作）
#定义节点：同双向链表
class node():
def __init__(self,item):
self.item=item
self.prev=None
self.next=None
#定义双向循环链表（除局部方法改进外，大部分同双向链表一样）
class doublelist():
def __init__(self):
self.head=None
def size(self):
s=0
m=self.head
if m:
s+=1
m=m.next
while m!=self.head:
s+=1
m=m.next
return s
def isempty(self):
return self.head==None
def append(self,item):
t=node(item)
m=self.head
if m==None:
m=t
m.next=m
m.prev=m
self.head=m
return
else:
r=m.prev
r.next=t
t.prev=r
t.next=self.head
self.head.prev=t
def add(self,item):
t=node(item)
m=self.head
if m==None:
m=t
m.next=m
m.prev=m
self.head=m
return
else:
t.next=m
t.prev=m.prev
m.prev.next=t
m.prev=t
self.head=t
def insert(self,index,item):
t=node(item)
m=self.head
if m==None:
m=t
m.next=m
m.prev=m
self.head=m
return
elif index+1>self.size():
self.append(item)
elif index==0:
self.add(item)
else:
i=0
while i<index:
m=m.next
i+=1
t.next=m
t.prev=m.prev
m.prev.next=t
m.prev=t
def pop(self):
m=self.head
if m==None:
return
else:
s=m.prev.item
r=m.prev.prev
r.next=m
m.prev=r
return s
def delete(self,item):
m=self.head
if m==None:
return
else:
while m.item!=item:
m=m.next
r=m.prev
r.next=m.next
m.next.prev=r
def find(self,item):
m=self.head
s=0
if m.item==item:
s+=1
m=m.next
while m!=self.head:
if m.item==item:
s+=1
m=m.next
return s
def printall(self):
m=self.head
if m==None:
print(None)
else:
print(m.item,end=" ")
m=m.next
while m!=self.head:
print(m.item,end=" ")
m=m.next在实现了数组和链表后，我们需要知道在实现数据结构时有顺序存储和链式存储。
顺序存储：在C里面用数组实现，所有数据项都是按照内存空间顺序存储的。在python里面一般可以用列表实现。
链式存储：用链表的形式存储数据。
3.队列（queue模块）
python在实现队列时，一般使用其内置的库queue。当然也可以使用自定义数组或者链表实现，但是对于python我们说过，但凡能使用内置方法就使用内置方法，一是方便，二是快，三是功能完善。
队列方法：（适用于所有的队列）
.qsize()：返回队列的大致大小。
注意，qsize() > 0 不保证后续的 get() 不被阻塞，qsize()<maxsize也不保证put()不被阻塞。
.empty()
如果队列为空，返回 True ，否则返回 False 。
如果 empty() 返回 True ，不保证后续调用的 put() 不被阻塞。类似的，如果 empty() 返回 False ，也不保证后续调用的 get() 不被阻塞。
.full()
如果队列是满的返回 True ，否则返回 False 。
如果 full() 返回 True 不保证后续调用的 get() 不被阻塞。类似的，如果 full() 返回 False 也不保证后续调用的 put() 不被阻塞。
.put(item, block=True, timeout=None)：将 item 放入队列。
如果可选参数 block 是 true 并且 timeout 是 None (默认)，则在必要时阻塞至有空闲插槽可用。
如果 timeout 是个正数，将最多阻塞 timeout 秒，如果在这段时间没有可用的空闲插槽，将引发 Full 异常。
反之 (block 是 false)，如果空闲插槽立即可用，则把 item 放入队列，否则引发 Full 异常 ( 在这种情况下，timeout 将被忽略)。
.put_nowait(item)：相当于 put(item, False) 。
.get(block=True, timeout=None)：从队列中移除并返回一个项目。
如果可选参数 block 是 true 并且 timeout 是 None (默认值)，则在必要时阻塞至项目可得到。
如果 timeout 是个正数，将最多阻塞 timeout 秒，如果在这段时间内项目不能得到，将引发 Empty 异常。
反之 (block 是 false) , 如果一个项目立即可得到，则返回一个项目，否则引发 Empty 异常 (这种情况下，timeout 将被忽略)。
.get_nowait()：相当于 get(False) 。
提供了两个方法，用于支持跟踪排队的任务是否被守护的消费者线程完整的处理。
.task_done()：表示前面排队的任务已经被完成。被队列的消费者线程使用。
每个 get() 被用于获取一个任务， 后续调用 task_done() 告诉队列，该任务的处理已经完成。
如果 join() 当前正在阻塞，在所有条目都被处理后，将解除阻塞
(意味着每个 put() 进队列的条目的 task_done() 都被收到)。
如果被调用的次数多于放入队列中的项目数量，将引发 ValueError 异常 。
.join()：阻塞至队列中所有的元素都被接收和处理完毕。
当条目添加到队列的时候，未完成任务的计数就会增加。每当消费者线程调用 task_done() 表示这个条目已经被回收，该条目所有工作已经完成，未完成计数就会减少。当未完成计数降到零的时候， join() 阻塞被解除。1）FIFO先入先出队列--Queue
这是最基本的队列，先输入的元素会先输出。
#创建队列对象
q = Queue(maxsize=0)#maxsize设置队列中数据上限，小于或等于0则不限制，容器中大于这个数则阻塞，直到队列中的数据被消掉
#写入队列数据
for i in range(3):
q.put(i)
#输出当前队列所有数据
print(type(q.queue),q.queue)
#队列弹出下一元素
cur = q.get()2）LIFO后入先出队列（栈）
后入先出队列，后输入的元素会先输出。
这里的后入先出队列，就是栈。（以下的后入先出队列就先用栈代表）
栈，添加移除新项总发生在同一端。这一端通常称为“顶部”。与顶部对应的端称为“底部”。
我们先给出栈的queue模块实现：
#创建后入先出队列对象
lq = LifoQueue(maxsize=0)
#队列写入数据
for i in range(3):
lq.put(i)
#输出队列所有数据
print(type(lq.queue),lq.queue)
#队列弹出下一元素
cur = lq.get()
当然，栈也可以通过顺序存储或者链式存储实现，由于栈的重要性，我们这里把这两种也实现一下。
顺序存储（列表实现）：
class Stack:
def __init__(self):#列表实现栈
self.items = []
def isEmpty(self):#判断栈是否为空
return self.items == []
def push(self, item):#将item入栈
self.items.append(item)
def pop(self):#出栈一次
return self.items.pop()
def peek(self):#返回栈顶元素
return self.items[len(self.items)-1]
def size(self):#返回栈的大小
return len(self.items)链式存储（链表实现）：
#定义节点
class note():
def __init__(self,item):
self.item=item#数据域
self.next=None#指针域
#定义栈
class stack():
def __init__(self):
self.head=None#头结点
def isempty(self):#判断栈是否为空
return self.head==None
def push(self,item):#item入栈
m=note(item)
c=self.head
m.next=c
self.head=m
def pop(self):#出栈一次
c=self.head
data=c.item
self.head=c.next
del c
return data
def peek(self):#返回栈顶元素
return self.head.item
def size(self):#返回栈的大小
c=self.head
s=0
while c:
c=c.next
s+=1
return s
def printall(self):#遍历栈中元素
c=self.head
while c:
print(c.item,end=" ")#遍历操作：打印
c=c.next3）优先级队列
优先级队列作为一种特殊的队列，会给各数据设置优先级（决定入栈和出栈的顺序）
#创建优先级队列对象
pq = PriorityQueue(maxsize=0)
#写入队列(优先级会按输入对象的第一个元素排序)
pq.put((9,'a'))
pq.put((7,'c'))
pq.put((1,'d'))
#输出队例全部数据
print(pq.queue) #[(1, 'd'), (9, 'a'), (7, 'c')]
#队列弹出下一元素(按优先级)
pq.get()
当然，通过堆（heapq库）也可以实现优先级队列，但是堆本质上还是一种完全二叉树。下面我们在树的部分会详细地解释堆。
4）双端队列
双端队列也是一种特殊的队列，其入队列和出队列可以在队列的两边同时进行，这样的队列更符合实际问题中一般的模型。
#创建双端队列对象
dq = deque(['a','b'])
dq.append('c')#增加数据到队尾
dq.appendleft('d')#增加数据到队左
dq.pop()#移除队尾
dq.popleft()#移除队左二、非线性数据结构
上述的线性数据结构都是一对一类型的结构。但实际生活中往往用到最多的是一对多或者多对多的非线性数据结构。当然，顺序存储显然是不适用于非线性数据结构，所以接下来我们将使用链式存储结构实现非线性数据结构。
1.树（一对多）
直观地看，树是数据元素（在树中称为结点）按分支关系组织起来的结构，很像自然界中的树那样。
树的一些基础概念：
节点的度：一个节点含有的子树的个数称为该节点的度；树的度：一棵树中，最大的节点的度称为树的度；
叶节点或终端节点：度为零的节点；
节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
树的高度或深度：树中节点的最大层次；
路径：对于一棵子树中的任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径
在树里面有一种特殊的树--二叉树，即每个节点最多含有两个子树的树。在数据结构占据着非常重要的地位。有些说法认为二叉树不属于树，但是这里我们暂且放到这里介绍二叉树。因为二叉树的实现，是普通的树以及森林实现的重要基础。
1）二叉树
完全二叉树：对于一颗二叉树，假设其深度为d(d>1)。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树;
1.数学性质：
1）在二叉树的第i层上至多有2^(i-1)个结点（i>0）
2）深度为k的二叉树至多有2^k - 1个结点（k>0）
3）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;
4）具有n个结点的完全二叉树的深度必为 log2(n+1)
5）对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）
2.遍历方法
1）深度遍历：沿着树的深度遍历树的节点，尽可能深的搜索树的分支
深度遍历有三种方式：
（1）先序遍历的顺序为：根节点->左子树->右子树；
（2）中序遍历为：左子树->根节点->右子树；
（3）后序遍历是：左子树->右子树->根节点；
其中的序指的是根节点相对于左右节点的遍历位置。
2）广度遍历：从树的根层级开始一层一层的遍历，遍历完上一层再遍历下一层
3.由遍历构造二叉树（至少需要两组遍历）
后序遍历的第一个字符就是根，因此只需在中序遍历中找到它，就知道左右子树的中序 和后序遍历了。
4.实现（链式存储）
#定义树的结点
class node():
def __init__(self,item,left=None,right=None):
self.item=item#数据域
self.left=left#左子树
self.right=right#右子树
#定义树
class tree():
def __init__(self,root=None):
self.root=root
#每加满一个节点，在其左节点下继续加
def add(self,item):
t=node(item)
if self.root==None:
self.root=t
return
q=[self.root]
while q:
c=q.pop()
if c.left==None:
c.left=t
return
elif c.right==None:
c.right=t
return
else:
q.append(c.right)
q.append(c.left)
#插入节点，order为插入位置，'L'为左子树，'R'为右子树
def insert(self,root,item=None,order='L'):
if root==None:
root=node(item)
return
if order=='L':
if root.left:
if root.left.item:
return
else:
root.left.item=item
else:
root.left=node(item)
elif order=='R':
if root.right:
if root.right.item:
return
else:
root.right.item=item
else:
root.right=node(item)
else:
raise ValueError("insert:order error")
#深度遍历（递归实现）
def preorder(self,root):#先序遍历
if not root:
print("",end="")
else:
print(root.item,end=" ")
self.preorder(root.left)
self.preorder(root.right)
def inorder(self,root):#中序遍历
if not root:
print("",end="")
else:
self.inorder(root.left)
print(root.item,end=" ")
self.inorder(root.right)
def postorder(self,root): #后序遍历
if not root:
print("",end="")
else:
self.postorder(root.left)
self.postorder(root.right)
print(root.item,end=" ")
#广度遍历（队列实现）
def broad(self,root):
if not root:
print("",end="")
q=[root]
while q:
for i in range(len(q)):
t=q.pop(0)
print(t.item,end=" ")
if t.left:
q.append(t.left)
if t.right:
q.append(t.right)
#根据中序遍历和后序遍历构造树，返回树根
def con(self,mid,post,root):
if mid==[]:
return None
else:
r=post[-1]
root=node(r)
n=mid.index(r)
leftmid=mid[:n]
rightmid=mid[n+1:]
leftpost=find(leftmid,post)
rightpost=find(rightmid,post)
root.left=self.con(leftmid,leftpost,root.left)
root.right=self.con(rightmid,rightpost,root.right)
return root
#返回由路径元组构成的列表
def path(self,root):
def addpath(root,list1,s):
if not root.left and not root.right:
s+=(root.item,)
list1.append(s)
else:
s+=(root.item,)
if root.left:
addpath(root.left,list1,s)
if root.right:
addpath(root.right,list1,s)
list1=[]
addpath(root,list1,())
return list1 也可以采用嵌套列表的方式实现二叉树，但形式较为复杂（数据项很少很少时可以使用），不建议使用。
5.应用：
- 排序二叉树：用于二叉排序算法
- 最优二叉树（赫夫曼树）：用于解决编码问题
- 平衡二叉树：应用较广泛，此处不作介绍
联动：二叉树与优先级队列--堆
堆（heap）是一种优先队列。本质上讲，它是一个完全二叉树，实现的时候不需要建造一个树，改用一个数组即可。若一个节点的索引为i，那么，父节点的索引为（i-1）//2，左孩子节点编号为i*2+1，右孩子节点为i*2+2。
堆的特点：
- 内部数据是有序的
- 可以弹出堆顶的元素，大根堆就是弹出最大值，小根堆就是弹出最小值
- 每次加入新元素或者弹出堆顶元素后，调整堆使之重新有序，时间复杂度O(logn)
python实现堆时使用其内置的模块heapq
heapq模块
heappush(heap, x)：将x压入堆heap中
请注意，不能将它用于普通列表，而只能用于使用各种堆函数创建的列表，
原因是元素的顺序很重要，元素的排列顺序并不像看起来那么随意。
它们虽然不是严格排序的，但必须保证一点：
位置i处的元素总是大于位置i // 2处的元素（反过来说就是小于位置2 * i和2 * i + 1处的元素）。
这是底层堆算法的基础，称为堆特征（heap property）。
heappop(heap)：从堆heap中弹出最小的元素
最小的元素总是位于索引0处，并确保剩余元素中最小的那个位于索引0处（保持堆特征）。
heapify()：让列表heap具备堆特征
通过执行尽可能少的移位操作将列表变成合法的堆（即具备堆特征）。
如果你的堆并不是使用heappush创建的，应在使用heappush和heappop之前使用这个函数。
heapreplace(heap, x)：弹出最小的元素，并将x压入堆中
相比于依次执行函数heappop和heappush，这个函数的效率更高。
nlargest(n, iter)和nsmallest(n, iter)，:分别用于找出可迭代对象iter中最大和最小的n个元素。
这种任务也可通过先排序（如使用函数sorted）再切片来完成，
但堆算法的速度更快，使用的内存更少（而且使用起来也更容易）。以上的方法都适用于最小堆，即双亲结点小于孩子节点。
对于最大堆，即双亲结点大于孩子节点的情况，该模块保留了一些方法：
_heappop_max(heap)：相当于最小堆的heappop方法
_heapify_max(heap) ：相当于最小堆的heapify方法
_heapreplace_max(heap, x)：相当于最小堆的heapreplace方法
注意：对于最大堆的操作没有_heappush_max方法
当然，给数据加负号也可以实现最小堆到最大堆的转化
2）树
实现了二叉树之后，对于树的实现就很容易了。
实现方法1：孩子双亲表示法
class TreeNode():
def __init__(self, name, parent=None):
self.name = name#数据域
self.parent = parent#双亲结点
self.child = []#用列表存储所有的子节点当然也可以使用单链表代替列表来存储子节点。
实现方法2：孩子兄弟表示法
class TreeNode():
def __init__(self, name, child,bro):
self.name = name#数据域
self.child = child#第一个孩子结点
self.bro = bro#第一个兄弟结点由孩子兄弟表示法可以发现，树是以二叉树的形式实现的，接下来要说的森林也是一样的实现方法。
3）森林
森林：由m（m>=0）棵互不相交的树的集合称为森林
实现方法：孩子兄弟表示法
树的孩子兄弟表示法里，如果根节点为空，则树就是森林。
这里我们不能发现，二叉树、树、森林之间可以互相转换。
2.图（多对多）
在推广一下树的话，就到了多对多的图了。图可以更好地拟合实际问题，但是也最为复杂。
图的基本概念：
边（弧）：两个顶点之间
路径:：通过边连接的顶点序列
周期：第一个和最后一个顶点相同的路径
入度:：顶点的度数V是以V为端点的边数
出度： 顶点的出度v是以v为起点的边的数量
度：顶点的度数是其入度和出度的总和
1）图的分类
- 无向图：两个顶点之间可以沿着边互相访问，双向连通。
- 有向图：两个顶点之间只能以弧的箭头方向进行访问，单向连通。
图的连通性：
对于无向图，其连通子图（连通分量）称为连通图
对于有向图，其连通子图（强连通分量）称为强连通图
若任意节点之间均连通，称为完全图。
2）图的实现
图的实现有四种方法：
- 邻接矩阵
- 邻接表
- 十字链表
- 邻接多重表
邻接矩阵
用具体的数值表示节点之间的关系，可以使用邻接矩阵，假设这个矩阵是A,Aij就表示第i个节点和第j个节点是否相连，为1表示相连，0表示不相连。当然，该数值也可以是边或者弧的权值。
class graph:
def __init__(self,vertex,directed=False):
vertex=list(set(vertex))
self.vertex=vertex #顶点列表
self.num_edge=0 #边的数量
self.directed=directed#是否有向图
self.matrix=[[0 for i in range(len(vertex))]for i in range(len(vertex))]#邻接矩阵
#以邻接矩阵遍历图
def draw(self):
print(' ',self.vertex)
for i in range(len(self.matrix)):
print(self.vertex[i],self.matrix[i])
#加边（权值默认为1）
def addedge(self,v,w,weight=1):
if v in self.vertex and w in self.vertex:
i=self.vertex.index(v)
j=self.vertex.index(w)
self.matrix[i][j]=weight
if self.directed==False:
self.matrix[j][i]=weight
self.num_edge+=1
else:
raise Exception("vertex not in the Graph")
#为图加入节点
def addvertex(self,v):
if v in self.vertex:
return
self.vertex.append(v)
for i in self.matrix:
i.append(0)
self.matrix.append([0]*len(self.vertex))注意：应当先加入节点，再加入边。
缺点：浪费存储空间。
优点：便于访问与遍历。
适合表示稠密图。
邻接表
对于邻接表来说，一行只代表和他相连的节点。
class vertex():
def __init__(self,item):
self.item=item
self.connect={}
class graph():
def __init__(self,v=[],directed=False):
v=list(set(v))
self.vertex={}
self.directed=directed
for i in v:
self.vertex[i]=vertex(i)
#画图
def draw(self):
for i in self.vertex.keys():
print(i,end=':')
for j,k in self.vertex[i].connect.items():
print(j,'(',k,')',sep='',end=' ')
print('')
def addvertex(self,item):
if not item in self.vertex:
self.vertex[item]=vertex(item)
def addedge(self,v,w,weight=1):
if not v in self.vertex:
self.addvertex(v)
if not w in self.vertex:
self.addvertex(w)
self.vertex[v].connect[w]=weight
if self.directed==False:
self.vertex[w].connect[v]=weight
#深度优先搜索
def DFS(self,v):
l=[]
def f(v,l):
if v in l:
return
print(v,end=' ')
l.append(v)
p=self.vertex[v].connect.keys()
for i in p:
f(i,l)
f(v,l)
print('')
#广度优先搜索
def BFS(self,v):
q=[v]
l=[v]
while q!=[]:
u=q.pop(0)
print(u,end=' ')
t=self.vertex[u].connect.keys()
for i in t:
if i in l:
continue
l.append(i)
q.append(i)这里我们不妨与二叉树的遍历作对比，发现深度遍历都是采用递归的方法，广度遍历都是采用队列的方式。其实，由此可以看出图可以用树表示出来，我们习惯上将图的极小连通子图称为生成树。
十字链表
十字链表适用于有向图，操作时也较为方便，但是结构较为复杂，整体的时间复杂度和邻接表一样。
十字链表的结点描述：
顶点结点：
- 数据域
- 两个链域指示以该顶点为弧头、弧尾的第一个弧结点
弧结点：
- 数据域指示弧的信息
- 两个链域指向弧尾相同的下一条弧和弧头相同的下一条弧
- 尾域和头域指示弧头和弧尾这两个结点在图中的位置
#定义顶点
class vertex():
def __inif__(self,data,firstin,firstout):
self.data=data#数据域
self.firstin=firstin#以该顶点为弧尾的第一个弧结点
self.firstout=firstout#以该顶点为弧头的第一个弧结点
#定义弧
class edge():
def __inif__(self,info,tailvex,headvex,hlink,tlink):
self.info=info#数据域，一般表示弧的权值
self.tailvex=tailvex#弧尾结点在图中（顶点链表）的位置
self.headvex=headvex#弧头结点在图中（顶点链表）的位置
self.hlink=hlink#弧头相同的下一条弧
self.tlink=tlink#弧尾相同的下一条弧
#定义十字链表
class crossinglink():
def __inif__(self):
self.vertex=[]#顶点列表
邻接多重表
邻接多重表适用于无向图，但其结构同十字链表一样，唯一的不同是其顶点结点的链域只有第一天依附于该节点的边（显然无向图没有弧头弧尾一说，故只需要一条边）。
由于与十字链表基本相同，这里不再赘述，读者可自行练习。
3）图的算法
我们之前有说，算法不是python的特色，这里只是简单介绍一下图里面的基本算法的思路，具体实现可以参考C语言的《数据结构与算法》。
遍历
1.深度优先搜索（DFS）--类似于树的先序遍历
2.广度优先搜索（BFS）
最小生成树
1.Prim算法
适用于求边稠密的图，时间复杂度O（n^2）
- 设置辅助数组记录并不断更新具有过程中到达不同顶点最小代价的边
- 从一个顶点开始，重复找代价最小的边，并不再考虑到达该边另一顶点，同时更新辅助数组
2.Kruskal算法
时间复杂度O(e·loge)
每个顶点先各成连通分量，再在所有边里选择代价最小的边，若该边的顶点落在不同的连通分量上，则选择该边
最短路径
1.Dijkstra算法（单源最短路径）
时间复杂度O(n^2)
- 建立一维辅助数组存储起点到各结点的最短路径的长度
- 先将起点到各点路径存入辅助数组，然后循环找到辅助数组中路径的最小值，确定起点到该点的最短路径已找到，同时更新辅助数组
2.Floyd算法（多源最短路径）
时间复杂度O(n^3)
- 建立二维辅助数组存储各结点到其他结点的最短路径的长度
- 先将各点之间路径存入辅助数组，再循环判断各个路径是否为最短路径：循环比较该路径与以其他结点为中间结点得到的路径大小，然后更新该路径值
以上便是python中数据结构的实现，可能有某些方面讲的有些问题或者不够详细，欢迎私信或者评论区提出您的意见。
感谢您的阅读！！！
