有向图(Directed Graph):在有向图中,边是有方向性的,从一个节点指向另一个节点。这意味着从节点 A 到节点 B 的边与从节点 B 到节点 A 的边可以是不同的,或者根本不存在。有向图通常用于表示具有方向性的关系,例如网页链接、社交关系中的关注关系等。
在社交网络中,有向图可以更详细地描述用户之间的交互关系。
关注关系:
用户A关注了用户B,但用户B并不关注用户A。这种情况下,可以在有向图中表示为从节点A指向节点B的有向边。
用户C既关注了用户D,又被用户D关注。这种情况下,可以在有向图中表示为从节点C指向节点D的有向边,并且从节点D指向节点C的另一条有向边。
以下是使用邻接表实现有向图的基本示例(使用Python的字典Dictionary来表示邻接表):
- class SocialNetwork:
- def __init__(self):
- self.graph = {}
-
- def add_user(self, user):
- if user not in self.graph:
- self.graph[user] = set() # set()是Python中的一个内置函数,用于创建一个空的集合(set)。
-
- def follow(self, follower, followee):
- if follower in self.graph and followee in self.graph:
- self.graph[follower].add(followee)
-
- # def follow(self, follower, followee):
- # 这是一个方法定义,接受三个参数:self、follower 和 followee。self 表示类的实例本身,follower 是关注者的标识符,followee 是被关注者的标识符。
- # if follower in self.graph and followee in self.graph::这是一个条件语句,检查关注者和被关注者是否都存在于社交网络中。如果关注者和被关注者都存在,则条件成立。
- # self.graph[follower].add(followee):如果条件成立,即关注者和被关注者都存在于社交网络中,那么将被关注者添加到关注者的关注集合中。
- # self.graph[follower] 表示关注者在