数据结构如何实现无向网结构

Question

什么事无向网，如何设计实现无向网结构，网络上搜了一些，但是没有看懂

Answer 1

该回答引用ChatGPT

无向网是一种基于图论的数据结构，它由节点和边组成。每个节点表示一个对象，每条边表示两个节点之间的连接关系，并且每条边都具有一个权值，表示连接这两个节点的代价或者距离。

---

要实现无向网结构，可以使用邻接矩阵或邻接表两种方式：

• 邻接矩阵
  邻接矩阵是一个二维数组，其中第i行第j列的元素表示节点i和节点j之间的边的权值。如果i和j之间没有边相连，则该元素的值为0。这种方式的优点是可以快速地查找两个节点之间是否有边相连，但是对于稀疏图来说，空间开销比较大。

• 邻接表
  邻接表是一种链式存储方式，每个节点都对应一个链表，链表中存储与该节点相邻的其他节点以及边的权值。这种方式的优点是可以节省空间，但是查找两个节点之间是否有边相连的时间复杂度为O(n)，其中n为节点的数量。

以下是使用 Python 语言实现无向网的示例代码，其中使用邻接表实现：

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.adj_list = {}
        for node in nodes:
            self.adj_list[node] = []
            
    def add_edge(self, u, v, weight):
        self.adj_list[u].append((v, weight))
        self.adj_list[v].append((u, weight))
        
    def get_weight(self, u, v):
        for node in self.adj_list[u]:
            if node[0] == v:
                return node[1]
        return None

在上述代码中，Graph 类表示一个无向网，其中 nodes 列表存储了所有节点的名称。在 add_edge 方法中，参数u和v分别表示两个节点的名称，weight 表示它们之间的边的权值。get_weight 方法用于获取两个节点之间的边的权值，如果它们之间没有边相连，则返回 None。