【学习笔记】Algorithms in Python - Graphs and Trees

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

1. Implementing Graphs
The two most well-know representations:

• adjacency lists
• adjacency matrices
  

+ Adjacency Lists
list/array or set
a, b, c, d, e, f, g, h = range(8)
N = [
    {b: 2, c: 3, d: 4, e: 1, f: 5},      # a
    {c, e},                   # b
    {d},                       # c
    ...
]

or
N = {
    'a': set('bcdef'),   # or 'bcdef' - use string instead of set, lower overhead but only useful for iteration only use cases
    'b': set('ce'),
    ...
}

+ Adjacency Matrices
Instead of listing all neighbors for each node, have a row (an array) with one position for each possible (that is, one for each node in the graph), and store a value, such as True or False. The simplest implementation is achieved using nested lists.

a, b, c, d, e, f, g, h = range(8)
# a b c d e f g h
N = [
    [0,1,1,1,1,1,0,0],    # a
    [0,0,1,0,1,0,0,0],    # b
    [0,0,0,1,0,0,0,0],    # c
    [0,0,0,0,1,0,0,0],    # d
    [0,0,0,0,0,1,0,0],    # e
    [0,0,1,0,0,0,1,1],    # f
    [0,0,0,0,0,1,0,1],    # g
    [0,0,0,0,0,1,1,0]    # h
]

# check neighborhood membership
N[a]

# Degree
sum(N[f])

• Useful properties for adjacency matrices
  
  • the diagonal is all false (0) if we don't allow the self-loops
  • the adjacency matrix for an undirected graph will be symmetric
    
• use weight instead of True/False for weighted graph
  
  • use infinite weight for nonexistent edges for practical reasons
  • or use illegal weight values such as None or -1
    

a, b, c, d, e, f, g, h = range(8)
inf = float('inf')

W = [
    [0, 2, 1, 3, 4, inf, inf],    #a
    ...
]

>>> W[a] < inf
# Neighborhood membership
True
>>> W[c][e] < inf
# Neighborhood membership
False
>>> sum(1 for w in W[a] if w < inf) - 1 # Degree
5

• special purpose arrays with numpy
  

import numpy as np
N = np.zeros([10, 10])

2. Implement Trees

• could represent that tree with lists of lists, like this:
  

>>> T = [["a", "b"], ["c"], ["d", ["e", "f"]]]
>>> T[0][1]
'b'
>>> T[2][1][0]
'e'

• A Binary Tree Class
  

class Tree:
    def __init__(self, left, right):
        self.left = left
        self.right = right

You can use the Tree class like this:
>>> t = Tree(Tree("a", "b"), Tree("c", "d"))
>>> t.right.left
'c'

• A Multiway Tree Class
  
  • A common way of implementing trees, especially in languages that don’t have built-in lists, is the “first child, next sibling” representation. Here, each tree node has two “pointers,” or attributes referencing other nodes, just like in the binary tree case. However, the first of these refers to the first child of the node, while the second refers to its next sibling, as the name implies. In other words, each tree node refers to a linked list of siblings (its children), and each of these siblings refers to a linked list of its own.
    

class Tree:
    def __init__(self, kids, next=None):
        self.kids = self.val = kids
        self.next = next

>>> t = Tree(Tree("a", Tree("b", Tree("c", Tree("d")))))
>>> t.kids.next.next.val
'c'

===
THE BUNCH PATTERN [This pattern isn’t useful only when building trees, of course. You could use it for any situation where you’d want a flexible object whose attributes you could set in the constructor.]
When prototyping or even finalizing data structures such as trees, it can be useful to have a flexible class that
will allow you to specify arbitrary attributes in the constructor. In these cases, the Bunch pattern (named by Alex
Martelli in the Python Cookbook) can come in handy. There are many ways of implementing it, but the gist of it is
the following:

class Bunch(dict):
    def __init__(self, *args, **kwds):
        super(Bunch, self).__init__(*args, **kwds)
        self.__dict__ = self

• There are several useful aspects to this pattern. First, it lets you create and set arbitrary attributes by supplying them as command-line arguments:
  

>>> x = Bunch(name="Jayne Cobb", position="Public Relations")
>>> x.name
'Jayne Cobb'

• Second, by subclassing dict , you get lots of functionality for free, such as iterating over the keys/attributes or easily checking whether an attribute is present. Here’s an example:
  

>>> T = Bunch
>>> t = T(left=T(left="a", right="b"), right=T(left="c"))
>>> t.left
{'right': 'b', 'left': 'a'}
>>> t.left.right
'b'
>>> t['left']['right']
'b'
>>> "left" in t.right
True
>>> "right" in t.right
False

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏4 回帖

关键词：Algorithms Algorithm Graphs python Trees

为您点赞！

点赞！

厉害！

来看看。。。。

谢谢分享

点赞

感谢分享，向您学习，为您点赞