文档章节

图论

jit-hakase
 jit-hakase
发布于 2017/09/12 21:21
字数 1479
阅读 4
收藏 0

图 论

使用邻接表和邻接矩阵中的邻接矩阵描述

图的遍历

图例如下, 0为起点.    0   /
1   2   \ / 
   3   4

深度优先搜索(DFS)

N = 5

G = [
     [ 0, 1, 1, 0, 0 ],
     [ 1, 0, 0, 1, 0 ],
     [ 1, 0, 0, 1, 1 ],
     [ 0, 1, 1, 0, 0 ],
     [ 0, 0, 1, 0, 0 ]
]

V = [False for i in range(N)]

def dfs(n):
    print(n)
    for j in range(N):
        if not V[j] and G[n][j]:
            V[j] = True
            dfs(j)

V[0] = True
dfs(0)

广度优先搜索(BFS)

from queue import Queue

N = 5

G = [
     [ 0, 1, 1, 0, 0 ],
     [ 1, 0, 0, 1, 0 ],
     [ 1, 0, 0, 1, 1 ],
     [ 0, 1, 1, 0, 0 ],
     [ 0, 0, 1, 0, 0 ]
]

V = [False for i in range(N)]

Q = Queue()

def bfs(n):
    Q.put(n)
    V[0] = True
    
    while not Q.empty():
        i = Q.get()
        print(i)
        for j in range(N):
            if not V[j] and G[i][j]:
                Q.put(j)
                V[j] = True


bfs(0)

最小生成树

问题: 将一个图的所有顶点构成树, 要求边的权值和最小. 普里姆算法:从起点开始选择边, 每次添加一个顶点(边权值和最小)并调整已添加好的顶点集与其他顶点的最短距离(边权值最小), 递归此步骤. 克鲁斯卡尔算法:每次选择最短边, 如果构成环, 则放弃这条边, 递归此步骤.

普里姆(prim)算法

X = 100

N = 6

G = [
	[ X, 6, 1, 5, X, X ],
	[ 6, X, 5, X, 3, X ],
	[ 1, 5, X, 1, 5, 4 ],
	[ 5, X, 1, X, X, 2 ],
	[ X, 3, 5, X, X, 6 ],
	[ X, X, 4, 2, 6, X ]
]

class Edge:
	def __init__(self, begin, end, lens):
		self.begin, self.end = begin, end
		self.lens = lens
	def __len__(self):
		return self.lens
		

# init edge info
E = []

for i in range(1, N):
	E.append(Edge(0, i, G[0][i]))


# set kth edge
for k in range(0, N-1):

	# find shortest edge
	minz, idx = X, -1
	for i in range(k, N-1):
		if len(E[i]) < minz:
			minz = len(E[i])
			idx = i

	# swap edge
	E[k], E[idx] = E[idx], E[k]
	v = E[k].end

	# adjust edge
	for i in range(k+1, N-1):
		d = G[v][E[i].end]
		if d < len(E[i]):
			E[i].lens = d
			E[i].begin = v


for item in E:
	print(item.begin, item.end, len(item))

克鲁斯卡尔(kruskal)算法

查找是否在相同集合来避免产生环, 集合为存放后继的顶点链.

X = 100

N = 6

G = [
	[ X, 6, 1, 5, X, X ],
	[ 6, X, 5, X, 3, X ],
	[ 1, 5, X, 1, 5, 4 ],
	[ 5, X, 1, X, X, 2 ],
	[ X, 3, 5, X, X, 6 ],
	[ X, X, 4, 2, 6, X ]
]

class Edge:
	def __init__(self, begin, end, lens):
		self.begin, self.end = begin, end
		self.lens = lens
	def __len__(self):
		return self.lens
		

# init edge info
E = []

for i in range(N):
    for j in range(i+1, N):
        if G[i][j] != X:
            E.append(Edge(i, j, G[i][j]))

E.sort(key=lambda x: x.lens)


P = [0 for i in range(N)]

# save next vertex
def find_set(f):
    while P[f] > 0:
        f = P[f]
    return f

# set kth edge
cnt_edge = 0
for i in range(len(E)):
    
    # find set
    n = find_set(E[i].begin)
    m = find_set(E[i].end)

    # if no circle
    if n != m:
        # add next vertex for vertex n
        P[n] = m
        print(E[i].begin, E[i].end, len(E[i]))

        # N-1 edges finish
        cnt_edge += 1
        if cnt_edge == N-1:
            break

最短路径

问题: 计算一个顶点到其他所有顶点的最短路径. 迪杰斯特拉算法: 设置一个起点, 先确定一个最短路径顶点v(第一次确定是相邻的顶点), 再将v作为中间点, 调整起点与各顶点的距离, 递归此步骤.

迪杰斯特拉(dijkstra)算法

INF = 400

N = 5

G = [
	[   0,  10, INF,  30, 100 ],
	[ INF,   0,  50, INF, INF ],
	[ INF, INF,   0, INF,  10 ],
	[ INF, INF,  20,   0,  60 ],
	[ INF, INF, INF, INF,   0 ]
]


# init S & D & P
# S(Set for Vertex)
# D(Distance for vertex 0 to others)
# P(Prev vertex for vertex)

S, D, P = [], [], []
S.append(0)

for i in range(N):
    D.append(G[0][i])
    P.append(0)


# set kth vertex
for k in range(1, N):

    # select shortest edge
    minz = INF
    for i in range(N):
        if not i in S:
            if D[i] < minz:
                minz = D[i]
                v = i
    
    # add new vertex to S
    S.append(v)

    # adjust D(distance)
    for i in range(N):
        if not i in S:
            if D[i] > D[v]+G[v][i]:
                D[i] = D[v]+G[v][i]
                P[i] = v


# show shortest distance
print(D)

# show shortest path
for i in range(1, N):
    prev = P[i]
    print(i, end='')
    while prev != 0:
        print('<--%d' % prev, end='')
        prev = P[prev]
    print('<--%d' % 0)

网络流

二分图匹配问题 问题: 求二分图的最大边匹配(最小点覆盖). 匈牙利算法: 依次匹配, 遇到点已经被匹配的情况下, 尝试能否让被匹配的点的对点匹配其他点(寻找增广路径), 递归此步骤. 二分图待配对情况: 0 <=> 0, 1 1 <=> 1, 2 2 <=> 0 3 <=> 2

匈牙利(Hungary)算法

N = 4

G = [
    [ 1, 0, 1, 0 ],
    [ 1, 1, 1, 0 ],
    [ 0, 1, 0, 1 ],
    [ 0, 0, 0, 0 ]
]

R = [-1 for i in range(N)]

def find_path(n):
    for j in range(N):
        if not V[j] and G[n][j]:
            V[j] = True
            if R[j]==(-1) or find_path(R[j]):
                R[j] = n
                return True
    return False


cnt = 0

for i in range(N):
    V = [False for i in range(N)]
    if find_path(i):
        cnt += 1

print(cnt)
for i in range(N):
    if R[i] != (-1):
        print('%d <==> %d' % (i, R[i]))

最大流问题 问题: 起点s, 终点t, 途中经过的管道(边)都有一个最大流量, s到t的最大水流量是多少? 定义: 残量网络 => 当前管道还可以容纳的水量(随着搜索变化), 加入反向边, 如果寻找到的增广路是错误路径, 可以通过反向边修正. 增广路算法: BFS找最短的增广路径, 修改这条路径流量值(修改残量网络边权), 递归此步骤.

增广路(Ford-Fulkerson)算法

import copy
from queue import Queue

INF = 400

N = 6

G = [
    [ 0, 5, 5, 0, 0, 0],
    [ 0, 0, 0, 5, 5, 0],
    [ 0, 0, 0, 5, 0, 0],
    [ 0, 0, 0, 0, 0, 5],
    [ 0, 0, 0, 0, 0, 5],
    [ 0, 0, 0, 0, 0, 0]
]

def find_path(R, P):
    V = [False for i in range(N)]
    Q = Queue()
    Q.put(S)
    V[S] = True

    # BFS find_path
    while not Q.empty():
        top = Q.get()
        for i in range(N):
            if not V[i] and R[top][i]>0:
                Q.put(i)
                V[i] = True
                P[i] = top

    # if find vertex T
    return V[T] == True


def FF():
    # R => Rest Flow Graph(Use Reverse R)
    R = copy.deepcopy(G)
    max_flow = 0

    # P => Path Of Flow
    P = [0 for i in range(N)]

    # if has path
    while find_path(R, P):
        min_flow = INF

        # find min flow
        v = T
        while v != S:
            u = P[v]
            min_flow = min(min_flow, R[u][v])
            v = P[v]
        
        # adjust R
        v = T
        while v != S:
            u = P[v]
            R[u][v] -= min_flow
            # reverse path => fix prior error path
            R[v][u] += min_flow
            v = P[v]

        # add max flow
        max_flow += min_flow

    return max_flow


S, T = 0, N-1

max_flow = FF()

print(max_flow)

© 著作权归作者所有

上一篇: jQuery(1)
下一篇: VIM
jit-hakase
粉丝 3
博文 26
码字总数 30408
作品 0
南京
程序员
私信 提问
【转】关于邦迪(J.A. Bondy)的图论教材

http://bbs.math.org.cn/viewthread.php?tid=360 我想很多学习图论的人都知道J.A. Bondy和U.S.R. Murty著的《Graph Theory with Application》(Elsevier,1976)是图论教材中的经典,时至今日,...

MtrS
2017/03/09
171
0
[概念辨析 系列 之四] 树的概念

刚做老师的时候,在考试、面试等场合发现大家对计算机科学中"树"的概念理解地非常不好,各种逻辑混乱的答案频繁出现。当时还不太理解,过了一段时间之后,对这个问题有了更全面的认识。"树"...

黄宇
2017/02/09
0
0
图论 基础篇

一. 图的介绍 说起图这个词,很多人可能首先会想到的就是图片,地图......等,但这里所说的图是一个抽象的概念。 定义:图是由一组顶点和一组能将两个顶点相连的边组成的。 图论一直以来都是...

丶legend
2017/10/20
0
0
PJ考试可能会用到的数学思维题选讲-自学教程-自学笔记

PJ考试可能会用到的数学思维题选讲 by PleiadesAntares 是学弟学妹的讲义——然后一部分题目是我弄的一部分来源于洛谷用户@ 普及组的一些数学思维题,所以可能有点菜咯别怪我 OI中的数学题—...

Pleiades_Antares
2018/10/02
0
0
2017蓝桥杯模拟赛

第二题:暴力,写的很丑,但也做个备份吧 snippetid="2309718" snippetfilename="blog201704031_7679907" name="code" class="cpp">#include include include include using namespace std;t......

hahohehehe
2017/04/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Security 自定义登录认证(二)

一、前言 本篇文章将讲述Spring Security自定义登录认证校验用户名、密码,自定义密码加密方式,以及在前后端分离的情况下认证失败或成功处理返回json格式数据 温馨小提示:Spring Security...

郑清
33分钟前
3
0
php yield关键字以及协程的实现

php的yield是在php5.5版本就出来了,而在初级php界却很少有人提起,我就说说个人对php yield的理解 Iterator接口 在php中,除了数组,对象可以被foreach遍历之外,还有另外一种特殊对象,也就是继承...

冻结not
46分钟前
4
0
servlet请求和响应的过程

本文转载于:专业的前端网站➥servlet请求和响应的过程 1.加载 Servlet类被加载到Java虚拟机中,并且实例化。在这个过程中,web容器(例如tomcat)会调用Servlet类的公开无参构造函数,产生一...

前端老手
46分钟前
4
0
golang 1.13 errors 包来了,不用写“err 气功波”代码

引 这篇是对 errors 包 的姿势挖掘 气功波错误代码 从 http.Get()返回的错误 判断 syscall.ECONNREFUSED 错误.以前要对 go 标准库 error 结构有点熟悉,才能写出下面的代码 func CmdErr(err ...

guonaihong
50分钟前
28
0
喜玛拉雅已听书单

时间倒序排 书名 作者 状态 唐砖 孑与2 进行中 死灵之书(克苏鲁神话合集) 阿卜杜拉·阿尔哈萨德 进行中 赡养人类 刘慈欣 完结 赡养上帝 刘慈欣 完结 中国太阳 刘慈欣 完结 中国太阳 刘慈欣...

Alex_Java
51分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部