图

简单来说，图是由一组点和相对应边组成的，可以表示为G=<V,E>,V为Vertex(点集)，E为Edge(边集)。细分下来根据点集之间的对等关系又可以分为，有向图(又可分为带权和无权有向图)，无向图，混合图。图中点包含的另外一个的重要信息就是各自的出度(outdeg)和入度(indeg)，表示了以该点作为出边和入边的个数。

图的复杂度

对于无向图而言，所有点的度之和为sum(deg)=2*|E|，度之和为边的数目的两倍。对于有向图而言，所有点的入度之和自然等于出度之和，也会等于边的数目，毕竟每一条边存在源点和终点。

稀疏图和稠密图及其储存方式

没有明确的界定公式表明什么是稠密图什么是稀疏图，一般而言如果边的数目远小于完全图的边数目的一半，那么认为是稀疏图。远大于则认为是稠密图。稀疏图适合使用使用邻接表储存，稠密图适合使用邻接矩阵储存。

拓扑排序

拓扑排序是对有向无环图的顶点的一种排序，可以使得如果存在一条从vi到vj的路径，那么vj一定排在vi后面。拓扑排序常见于工程的调度排班问题，子任务之间存在先后依赖关系。对有向图的拓扑排序算法伪代码如下

Graph=[...] # 初始化图的储存，使用邻接矩阵或者邻接表；
indegs=[deg0,deg1,deg2....] # 储存所有的点的入读
stack=[node0, node1...] # 使用栈stack储存所有入度为0的点；
ans=[] # 储存拓扑排序结果
while stack:
    topNode=stack.pop(0) # 取出第一个出度为0的点，从图中直接抹去
    ans.append(topNode)
    for u in Graph[topNode]: # 遍历取出的点所连接的点
        indegs[u]-=1 # 对应连接到的点入度减1
        if indegs[u]==0:
            stack.append(u) # 判断入度是否为0

实际代码为：

from collections import defaultdict

# 构建邻接表的有向图
N=7
graph={0:[1,5],
       1:[4],
       2:[4,6],
       3:[2,4],
       4:[5,6],
       5:[],
       6:[]}
# 计算每个点的入读
indegs=defaultdict(int)
for k,v in graph.items():
    for node in v:
        indegs[node]+=1
# 记录所有入度为0的起始点
stack=[]
for i in range(N):
    if i not in indegs:
        stack.append(i)
# 惊喜拓扑排序
ans=[] # 排序结果
while stack:
    topNode=stack.pop(0)
    ans.append(topNode)
    for v in graph[topNode]:
        indegs[v]-=1
        if indegs[v]==0:
            stack.append(v)
# 输出结果
print(ans)

最短路径算法

最短路径算法解决的是从给定的点开始求解到其他点的最短路径(边可以带权或者不带权值)。

无权边的最短路径算法

这种情况下可以认为边的权值为1，如果权值为1，那么这个问题可以简化为BFS搜索问题(或者DFS递归搜索问题)，也就是寻找达到各个节点的最短路径。

Graph=[...] # 初始化图的储存，使用邻接矩阵或者邻接表；
stack=[(initNode,0)] # 初始节点入栈，一并记录最短路径
dist={} # 记录源点到达各个点的最短距离，除开源点之外其他的初始值设置为inf
visited=set() # 记录已经访问过的点
while stack:
    cur=stack.pop(0) # 取出一个节点
    for v in graph[cur]:
        # 遍历下一层节点