# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # 图论  Grahp Theory
#
# ## 节点Vertex
# ## 变Edge
#
# ## 有向图
# ## 无向图
#
# ## 有权图
# ## 无权图
#
# ## 邻接矩阵
# ## 邻接表

# # 使用邻接矩阵来表示稠密图 Dense

class DenseGraph:
    def __init__(self, n, directed=False):
        """
        构造稠密图
        n: 节点数
        directed: 是否有向
        """
        # 存储节点数
        self.__n=n
        
        # 存储边数， 初始化为 0
        self.__m=0
        
        # 存储是否有向
        self.__directed=directed
        
        # 邻接矩阵， (n, n)，表示节点的是否连接，初始化为False
        self.__g= [ [False for i in range(n)] for i in range(n)]
        
        # 用来判断 两个节点是否相连
        # 能够相连的节点，其对应的id属性值一样
        self.__id=[-1 for i in range(self.__n)]
    
    def V(self):
        """
        图中有多少个节点
        """
        return self.__n
    
    def E(self):
        """
        图中有多少个边
        """
        return self.__m
    
    def hasEdge(self, v, w):
        """
        判断节点是否存在边
        v：节点索引
        w：节点索引
        返回bool
        """
        assert v>=0 and v<self.__n and w>=0 and w<self.__n
        
        return self.__g[v][w]
    
    def traverse(self, v):
        """
        遍历节点v的相邻节点
        """
        res=[]
        for i in range(self.__n):
            if self.__g[v][i]==1:
                res.append(i)
        return res
    
    def addEdge(self, v, w):
        """
        添加边
        v：节点索引
        w：节点索引
        """
        assert v>=0 and v<=self.__n and w>=0 and w<self.__n
        
        # 先判断该边是否已经存在
        if self.hasEdge(v,w):
            return
        
        self.__g[v][w]=True
        if not self.__directed:
            # 无向图
            self.__g[w][v]=True
        self.__m+=1
    
    def getComponents(self):
        # 记录节点是否被访问
        # 初始化为false，表示都没有被访问
        self.__visited=[False for i in range(self.__n)]
        # 记录联通分量数
        self.__ccount=0
        
        for i in range(self.__n):
            if not self.__visited[i]:
                # 如果没有访问，则进行深度优先遍历
                self.__dfs(i)
                self.__ccount+=1
        return self.__ccount
    
    def __dfs(self, v):
        """
        以v为初始节点，进行深度优先遍历
        """
        self.__visited[v]=True
        
        # 重点
        # 实际上，它的意思是： 用于区分每个元素 属于那个连通区
        self.__id[v]=self.__ccount
        
        adjacents=self.traverse(v)
        for w in adjacents:
            if not self.__visited[w]:
                self.__dfs(w)
    
    def isConnected(self, v, w):
        """
        判断两个节点是否连通
        """
        return self.__id[v]==self.__id[w]
    
    def getIds(self):
        return self.__id
    
    
    def path(self, source):
        """
        从source开始，到任意点的路径
        """
        self.__s = source
        # 记录
        self.__visited=[False for i in range(self.__n)]
        self.__from=[-1 for i in range(self.__n)]


# # 使用邻接表来表示稀疏图 Sparse

class SparseGraph:
    def __init__(self, n ,directed=False):
        """
        构造稀疏图
        n：节点数
        directed：是否有向
        """
        self.__n=n
        self.__m=0
        self.__directed=directed
        self.__g=[[] for i in range(n)]
        self.__id=[-1 for i in range(n)]
        
    def V(self):
        return self.__n
    def E(self):
        return self.__m
    
    def hasEdge(self, v, w):
        """
        判断v和w是否连接
        复杂度 O(N)
        """
        for i in range(len(self.__g[v])):
            if self.__g[v][i]==w:
                return True
        return False
    
    def traverse(self, v):
        """
        遍历节点v的相邻节点
        """
        assert v>=0 and v<self.__n
        
        res=[]
        for i in range(len(self.__g[v])):
            res.append(self.__g[v][i])
        return res
    
    def addEdge(self, v, w):
        """
        新增边
        """
        assert v>=0 and v<self.__n and w>=0 and w<self.__n
        
        # 每次添加边，都要判断是否存在
        # 这样，添加操作的复杂度也是 O（N）
        # 常见的做法是，先允许添加重复（也就是说，允许平行边）
        # 最后，添加完毕后，再批处理，去掉平行边
        if self.hasEdge(v, w):
            return
        
        self.__g[v].append(w)
        if not self.__directed and v!=w:
            # 无向图
            self.__g[w].append(v)
        self.__m+=1
    
    def getComponents(self):
        # 记录节点是否被访问
        # 初始化为false，表示都没有被访问
        self.__visited=[False for i in range(self.__n)]
        # 记录联通分量数
        self.__ccount=0
        
        for i in range(self.__n):
            if not self.__visited[i]:
                # 如果没有访问，则进行深度优先遍历
                self.__dfs(i)
                self.__ccount+=1
        return self.__ccount
    
    def __dfs(self, v):
        """
        以v为初始节点，进行深度优先遍历
        """
        self.__visited[v]=True
        
        self.__id[v]=self.__ccount
        
        adjacents=self.traverse(v)
        for w in adjacents:
            if not self.__visited[w]:
                self.__dfs(w)
    
    def isConnected(self, v, w):
        return self.__id[v]==self.__id[w]
    
    def getIds(self):
        return self.__id


# +
def test_graph(G, n, m):
    g=G(n)
    
    import random
    for i in range(m):
        a=random.randint(0, n-1)
        b=random.randint(0, n-1)
        g.addEdge(a, b)
        
    for i in range(n):
        print(i," has edges:",g.traverse(i))
    
    # 要先调用这个方法
    # 才会记录连通数
    print("components:", g.getComponents())
    
    print(g.getIds())
    for i in range(5):
        a=random.randint(0, n-1)
        b=random.randint(0, n-1)
        print(a," and ", b, " is connected? ", g.isConnected(a, b))
    
    
# -

# %%time
test_graph(SparseGraph, 10, 10)

# %%time
test_graph(DenseGraph, 10, 10)



StarcoderdataJupyterScriptsDedupFiltered