用单链表存储图的顶点实现图的BFS算法和DFS算法

单链表存储图的顶点可以使用邻接表的方式，即对于每个顶点，用一个链表存储其所有的邻接点。

BFS算法的实现：

# 定义图的节点
class GraphNode:
    def __init__(self, val):
        self.val = val
        self.next = None

# 定义图
class Graph:
    def __init__(self):
        self.nodes = []

    # 添加节点
    def add_node(self, val):
        node = GraphNode(val)
        self.nodes.append(node)

    # 添加边
    def add_edge(self, src, dst):
        for node in self.nodes:
            if node.val == src:
                new_node = GraphNode(dst)
                new_node.next = node.next
                node.next = new_node
                break

    # BFS算法
    def bfs(self, start):
        queue = [start]  # 存储待遍历的节点
        visited = set()  # 存储已经访问过的节点
        while queue:
            node = queue.pop(0)
            if node not in visited:
                print(node)
                visited.add(node)
                # 将该节点的所有邻接点加入队列
                for n in self.get_neighbors(node):
                    queue.append(n)

    # 获取某个节点的所有邻接点
    def get_neighbors(self, node):
        for n in self.nodes:
            if n.val == node:
                neighbor_nodes = []
                cur = n.next
                while cur:
                    neighbor_nodes.append(cur.val)
                    cur = cur.next
                return neighbor_nodes
        return []

# 测试BFS算法
graph = Graph()
graph.add_node(1)
graph.add_node(2)
graph.add_node(3)
graph.add_node(4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(3, 4)
graph.bfs(1)

DFS算法的实现：

# 定义图的节点
class GraphNode:
    def __init__(self, val):
        self.val = val
        self.next = None

# 定义图
class Graph:
    def __init__(self):
        self.nodes = []

    # 添加节点
    def add_node(self, val):
        node = GraphNode(val)
        self.nodes.append(node)

    # 添加边
    def add_edge(self, src, dst):
        for node in self.nodes:
            if node.val == src:
                new_node = GraphNode(dst)
                new_node.next = node.next
                node.next = new_node
                break

    # DFS算法
    def dfs(self, start, visited=None):
        if visited is None:
            visited = set()
        print(start)
        visited.add(start)
        # 遍历该节点的所有邻接点
        for n in self.get_neighbors(start):
            if n not in visited:
                self.dfs(n, visited)

    # 获取某个节点的所有邻接点
    def get_neighbors(self, node):
        for n in self.nodes:
            if n.val == node:
                neighbor_nodes = []
                cur = n.next
                while cur:
                    neighbor_nodes.append(cur.val)
                    cur = cur.next
                return neighbor_nodes
        return []

# 测试DFS算法
graph = Graph()
graph.add_node(1)
graph.add_node(2)
graph.add_node(3)
graph.add_node(4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(2, 4)
graph.add_edge(3, 4)
graph.dfs(1)