简书尽然不支持LaTex公式编辑！！！！
图
有向图与无向图的区别在于边集合E是否有相，另外表示的区别在于$e = (A, B);e1 = <A, B>$
- 完全无向图：任意两点之间存在边，n个点的边数$C_n^2$
- 完全有向图：任意两点之间存在两条方向互反的边
- 子图：图G1的顶点集合和边集合均为图G2的子集则称G1位G2的子图
- 无向图顶点的度：顶点关联边的数量记为D(v)
- 有相图顶点的出度和如度D(v) = ID(v) + OD(v)
- 回路、环：把所有顶点链接的路径，第一个和最后一个顶点不重复的路径称为简单环。
- 无向图中连通图:任意两个顶点存在路径连通
- 极大连通子图
- 有向图的强连通图：任意两个顶点可达
- 连通图的生成树：极小连通子图，包含n个顶点只有n-1条边；如果有一个有向图仅有一个顶点入度0，其他顶点入度均为，则为一颗有相树。
- 图的边上加上权重则为网
图的存储结构
- 邻接矩阵
- 邻接表：边相对于顶点较少的图用矩阵表示是一种浪费，链式存储。
- 十字链表：
- 多重链表
图的遍历
- 深度优先
# encoding: utf-8
"""
@version: python3.5.2
@author: kaenlee @contact: lichaolfm@163.com
@software: PyCharm Community Edition
@time: 2017/9/28 9:04
purpose:算法复杂度，最坏情况，每个点都不可达，每个点为基础遍历其他点N^2次
"""
import numpy as np
# 有6个顶点的无向图邻接矩阵如下:0-5
graphMat = np.array([[0, 1, 0, 1, 0, 1],
[1, 0, 1, 0, 0, 1],
[0, 1, 0, 0, 1, 0],
[1, 0, 0, 0, 0, 1],
[0, 0, 1, 0, 0, 1],
[1, 1, 0, 1, 1, 0]])
# 深度优先遍历
def travel(graphMat):
n = len(graphMat)
visited = np.zeros(n)
def DFS(graphMat, startPoint):
"""
:param graphMat:
:param startPoint: 开始访问起点
:return:
"""
nonlocal visited
visited[startPoint] = 1 # 用来记录该点是否被访问
n = len(graphMat[startPoint])
for i in range(n):
# 从连通的最右边开始遍历那些没有被访问到的下一个节点
if (graphMat[startPoint][i] == 1) and (visited[i] == 0):
# 该点和startpoint为连通且没有被访问到
print('visited', i)
DFS(graphMat, i)
for j in range(n):
# 从0点开始访问, 为连通的图(即任意两点可达，概念与markov的一样)，循环之后一次就访问所有的点
print('visited***', j)
DFS(graphMat, j)
if all(visited == 1):
break
travel(graphMat)
#------------------------------------out put-----------------------------------
visited*** 0
visited 1
visited 2
visited 4
visited 5
visited 3
-
广度优先
如果说深度便是类似于数的前序遍历，那么广度就类似于层次遍历
捕获.JPG
第一层A进栈
第二BF进， A出
第三层CIG进， B出
第三层E进， F出
....
def travel_BFS(graphMat):
n = len(graphMat)
visited = np.zeros(n)
temp = [] # 创建一个空栈
for i in range(n):
# 如果连通仅仅在这里循环一遍即可
temp.append(i) # 初始进栈
visited[i] = 1
print('visited', i)
while temp:
root = temp.pop(0)
for j in range(n):
if (graphMat[root][j] == 1) and (visited[j] == 0):
temp.append(j)
visited[j] = 1
print('visited', j)
if all(visited == 1):
break
travel_BFS(graphMat)
# ---------------------------out---------------------------------
visited 0
visited 1
visited 3
visited 5
visited 2
visited 4
最小生成树
对于一个网的最小生成树：将n个顶点用n-1条边连接，且边的权重之和最小。
- 谱里姆算法：一种归并点的算法，U为需要生成树的点，在U中随机选取一个点作为初始点v0并从U中剔除v0，搜选v0的邻近点中边权重最小的v1作为最小生成树的一部分，并从U中剔除v1,。然后考虑v1和v0的所有临近点，选取边权重最小点v3并从U中剔除v3，如此下去直到U为空。参考
# encoding: utf-8
"""
@version: python3.5.2
@author: kaenlee @contact: lichaolfm@163.com
@software: PyCharm Community Edition
@time: 2017/9/30 10:44
purpose:
"""
import sys
import numpy as np
def prim(graphMat):
n = len(graphMat)
U = list(range(n))
# 以能生成的最下边为起点
start = None
value = sys.maxsize
for i in U:
for j in U:
if graphMat[i, j] < value:
value = graphMat[i][j]
start = i
print(start)
V = [start]
U.remove(start)
total = 0 # 总权重
E = [] # 保存连接点边信息
while U:
# 循环直到U为空
minWay = None
minE = sys.maxsize
minV = None
for v in V:
for u in U:
if graphMat[v][u] < minE:
minE = graphMat[v][u]
minV = u
minWay = [u, v]
E.append(minWay)
V.append(minV)
U.remove(minV)
total += minE
return total, E
graphMat = np.array([[0, 6, 1, 5, sys.maxsize, sys.maxsize],
[6, 0, 5, sys.maxsize, 3, sys.maxsize],
[1, 5, 0, 5, 6, 4],
[5, sys.maxsize, 5, 0, sys.maxsize, 2],
[sys.maxsize, 3, 6, sys.maxsize, 0, 6],
[sys.maxsize, sys.maxsize, 4, 2, 6, 0]])
print(prim(graphMat))
-----out
(15, [[2, 0], [5, 2], [3, 5], [1, 2], [4, 1]])
- 克鲁斯卡尔算法：（1）构造一个只含n个顶点，边集为空的子图。若将图中各个顶点看成一棵树的根节点，则它是一个含有n棵树的森林。（2）从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图。也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之（3）依次类推，直至森林中只有一棵树，也即子图中含有 n-1条边为止。参考
import numpy as np
import sys
from itertools import combinations
def kruskal(graphMat):
# 将矩阵转化为{边：权重， ...}并排序
n = len(graphMat)
E = {}
for i in range(n):
for j in range(n):
if (i == j):
pass
else:
E.update({str(i)+str(j): graphMat[i, j]})
E = sorted(E.items(), key=lambda x: x[1])
V = []
U = list(range(n))
saveEs = []
totol = 0
for e, w in E:
p1, p2 = int(e[0]), int(e[1])
if (p1 in V) and (p2 in V):
# 顶点p1 p2都在V中就形成了环路，不可取
pass
else:
V.extend([p1, p2])
saveEs.append([p1, p2])
totol += w
if set(U) == set(V):
break
print('return', saveEs)
# 虽然这样将所有的样本点都取到，但可能并不是一个环，没有形成回路
numOfGroups = n - len(saveEs)
# print(numOfGroups)
if numOfGroups == 1:
return totol, saveEs
else:
# 整理出分组并在每个分组，取一条边作为连接回路
def findShare(X, tag):
newtag = tag.copy()
for i in X:
if set(i) & set(tag):
newtag.extend(list(set(i) - set(tag)))
if newtag == tag:
return newtag
else:
return findShare(X, newtag)
groups = []
for i in saveEs:
if groups:
flag = 0
# 如果改点已经存在groups中不在计算
for j in groups:
if set(j) & set(i):
flag = 1
break
if flag:
continue
one = findShare(saveEs, i)
groups.append(one)
print(groups)
asset = list(combinations(groups, 2))
print('asset', asset)
# 找出链接每两个group之间的最短连接
briges = []
for g1, g2 in asset:
minBrige = sys.maxsize
brige = None
for i in g1:
for j in g2:
if graphMat[i][j] < minBrige:
minBrige = graphMat[i][j]
brige = [i, j]
briges.append(brige)
# n个group之间仅仅需要n-1个连接
maxbrige = None
value = 0
for i, j in briges:
totol += graphMat[i, j]
if graphMat[i, j] > value:
maxbrige = [i, j]
briges.remove(maxbrige)
saveEs.extend(briges)
i, j = maxbrige
return totol - graphMat[i, j], saveEs
graphMat = np.array([[0, 6, 1, 5, sys.maxsize, sys.maxsize],
[6, 0, 5, sys.maxsize, 3, sys.maxsize],
[1, 5, 0, 5, 6, 4],
[5, sys.maxsize, 5, 0, sys.maxsize, 2],
[sys.maxsize, 3, 6, sys.maxsize, 0, 6],
[sys.maxsize, sys.maxsize, 4, 2, 6, 0]])
print(kruskal(graphMat))
---out
return [[0, 2], [3, 5], [1, 4]]
[[0, 2], [3, 5], [1, 4]]
asset [([0, 2], [3, 5]), ([0, 2], [1, 4]), ([3, 5], [1, 4])]
(15, [[0, 2], [3, 5], [1, 4], [2, 5], [2, 1]])
网友评论