一个红包引发的惨案

 · 2022-8-15 · 次阅读

一个红包引发的惨案

故事起源于隔壁一个吹水群的某天中午，可能是想增加点乐趣，群主发了两个红包。恰好是一笔画红包。而一笔画红包涉及到数据结构图论的相关知识，所以在此进行总结，并贴出相关的代码。

简介

一笔画红包

一笔画红包是QQ红包的一种形式。挑战者需要完成一笔画挑战之后才能领取红包

欧拉图

欧拉图是一种特殊的图，定义如下：

欧拉图是指通过图（无向图或有向图）中所有边且每边仅通过一次通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。

对于欧拉图，有以下几条性质：

  1. 一个无向图存在欧拉回路，当且仅当该图有 0 个或 2 个奇数度数的顶点，且该图是连通图。

  2. 一个无向图存在欧拉回路，当且仅当该图所有顶点度数都为偶数，且该图是连通图。

  3. 一个有向图存在欧拉回路，所有顶点的入度等于出度且该图是连通图。

  4. 一个有向图存在欧拉回路：图连通，所有节点的出度等于入度；或者除两个节点以外的其余节点的入度和出度都相等，且这两个节点一个满足出度 - 入度 ==1，另一个满足入度 – 出度 ==1。

对于QQ红包的场景，明显其为有向图。如果我们能获取到每条边的信息，就能使用深度优先算法求解欧拉路径。理论存在，实践开始

实践

获取边的信息

获取边的信息很简单，直接手机代理链接电脑上的fiddler，开启抓包即可。

image.png

右下角就是TX返回的包体了。connects数组包含了所有的边，而vertexes保存了所有的顶点。

对包体进行处理

这里使用了python对包进行处理，将包体的字符串变成我们熟悉的邻接矩阵：

# 构建邻接矩阵
def PreProcess(package):
    global versum
    package = package.replace("\\", "")
    package = package.replace("\"[", "[")
    package = package.replace("]\"", "]")
    package = json.loads(package)['data']		# 到这里为止是字符串的预处理
    con = package['connects']
    for i in con:
        sx = (i['x1'] - 75) / 150
        sy = (i['y1'] - 75) / 150
        ex = (i['x2'] - 75) / 150
        ey = (i['y2'] - 75) / 150		# 根据像素计算顶点序号
        s = int(sy * 5 + sx)
        e = int(ey * 5 + ex)
        versum = versum + 1				# 统计边的条数
        m[s][e] = m[s][e] + 1			# 设置邻接矩阵

计算起始顶点和终止顶点

根据欧拉图的性质，对于任意一个合法的欧拉图，只可能出现两种情况：

  1. 有2个奇数度的顶点，此时这两个奇数度的顶点分别为起点和终点
  2. 没有奇数度的顶点，此时任意一个顶点都能作为起点和终点

根据性质，写出代码即可

求解欧拉路径

这里使用深度优先算法。欧拉图可能有多解，选择其中的一个解即可：

# now 的初始调用值为上面确定的起点
def DFS(now):
    for i in range(25):
        if m[now][i] == 1:
            m[now][i] = m[now][i] - 1
            DFS(i)
    path.append(now + 1)

完整代码

下面是完整代码：

import json

m = [[0 for j in range(25)] for i in range(25)]
s = 0
e = 0
versum = 0
path = []

# 构建邻接矩阵
def PreProcess(package):
    global versum
    package = package.replace("\\", "")
    package = package.replace("\"[", "[")
    package = package.replace("]\"", "]")
    print(package)
    package = json.loads(package)['data']
    print(package["vertexes"])
    con = package['connects']
    for i in con:
        sx = (i['x1'] - 75) / 150
        sy = (i['y1'] - 75) / 150
        ex = (i['x2'] - 75) / 150
        ey = (i['y2'] - 75) / 150
        s = int(sy * 5 + sx)
        e = int(ey * 5 + ex)
        versum = versum + 1
        m[s][e] = m[s][e] + 1


# 判断起始和终止点
def GetStartAndEnd():
    global s, e
    du = []
    se = []
    for i in range(25):
        t = sum(m[i])
        t = t + sum([m[j][i] for j in range(25)])
        du.append(t)
    print("顶点的度：", du)
    for i in du:
        if i % 2 == 1:
            se.append(du.index(i))
    if len(se) == 0:
        for i in du:
            if 1 != 0:
                se.append(du.index(i))
                se.append(du.index(i))
                break
    s = se[0]
    e = se[1]


def DFS(now):
    for i in range(25):
        if m[now][i] == 1:
            m[now][i] = m[now][i] - 1
            DFS(i)
    path.append(now + 1)
    pass


if __name__ == '__main__':
    package = input("input package: \n")

    PreProcess(package)

    print("邻接矩阵：")
    for i in range(25):
        print(m[i])

    GetStartAndEnd()
    print("以下为分析结果：\n")
    print('起点：', s + 1, '终点：', e + 1, '边数：', versum)
    DFS(s)
    path.reverse()
    print("参考路径：")
    for i in range(len(path)):
        print(path[i], end=' ')
        if (i+1) % 5 == 0:
            print()

运行截图：

1

希望能通过这个小小的例子，体会欧拉图在生活中的应用。

赏