有/无向图闭环的寻找

一点碎碎念

  最近这几天，在搞华为的软件精英挑战赛，虽然比赛打的不咋地，但是好在能把以前的数据结构，图论相关知识复习一下（心态还是要摆正的）。不过话说回来，参加华为软件精英挑战赛，一定要熟悉C++，其他的Python，Java，C都是弟弟，不然时间上吃大亏。今年的初赛考察的是有向图寻找闭环的知识点，既然考察了有向图，那就顺带把无向图也一块温习一遍。

图的基本分类与储存

  图的分类依据有很多种，比较重要的两种分类依据就是分为有向图和无向图，稀疏图和稠密图。如何正确的分类会直接影响之后算法的选择，其中有向图和无向图的分类是客观的，但是稀疏图和稠密图的分类相对来说是比较主观的，主要是和图的节点个数以及节点的平均出度入度有很大关系。如果仅仅看节点的出度入度是不能很好地判断。一般来说，假设节点数为N，平均出度为\lambda，如果满足\lambda^2>=N，那么基本断定这是稠密图，反之则是稀疏图。
  稠密图一般采用邻接矩阵储存，稀疏图一般采用邻接链表储存，主要目的就是访问时节省时间

DFS(Depth-First-Search)

非递归方法

以下面的无向图为例：

'''
    0——————1
   /       \
   2        7
  /\        |
 3  4       8
 /  \       |
5    6——————9
'''

采用字典形式的邻接表形式进行储存为：

Graph = {0: [1, 2],
         1: [0, 7],
         2: [0, 3, 4],
         3: [2, 5],
         4: [2, 6],
         5: [3],
         6: [4,9],
         7: [1, 8],
         8: [7, 9],
         9: [8,6]}

非递归代码为：

def DFS(root,g):
    visit=[False]*g.__len__()
    visit[root]=True
    print('Visit node %d'%root)
    s=[]
    s.append(root)
    visit[root]=True
    while s: #s不为空
        pre=s[-1] #推出栈顶元素
        flag=True
        for node in g[pre]: #对相邻节点进行遍历
            if not visit[node]: #该节点未被访问
                flag=False
                print('Visit node %d'%node)
                visit[node]=True
                s.append(node) #访问完保存该节点
                #print(s)
                break #继续访问相邻节点
        if flag: #相邻节点都被访问过
            s.pop()
    return visit

if __name__=='__main__':
    Graph = {0: [1, 2],
             1: [0, 7],
             2: [0, 3, 4],
             3: [2, 5],
             4: [2, 6],
             5: [3],
             6: [4,9],
             7: [1, 8],
             8: [7, 9],
             9: [8,6]}
    res=DFS(0,Graph)

递归方法的实现

def DFS_re_for_if(node,g,visit):
    for nd in g[node]:
        if not visit[nd]:
            visit[nd]=True
            print('Visit node %d'%nd)
            DFS_re_for_if(nd,g,visit)

def DFS_re_if_for(node,g,visit):
    if not visit[node]:
        visit[node]=True
        print('Visit node %d'%node)
        for nd in g[node]:
            DFS_re_if_for(nd,g,visit)

if __name__=='__main__':
    Graph = {0: [1, 2],
             1: [0, 7],
             2: [0, 3, 4],
             3: [2, 5],
             4: [2, 6],
             5: [3],
             6: [4,9],
             7: [1, 8],
             8: [7, 9],
             9: [8,6]}
    #res=DFS(0,Graph)
    visit=[False]*Graph.__len__()
    DFS_re_for_if(0,Graph,visit) #先for后if
    print('*'*20)
    visit = [False] * Graph.__len__()
    DFS_re_if_for(0,Graph,visit) #先if后for