Map<Node, List<Edge>> edges 解释
时间: 2023-10-31 12:05:32 浏览: 47
这是一个用于表示图中节点和边的数据结构。其中,Map<Node, List<Edge>> 表示一个映射关系,将每个节点(Node)映射到它所连接的所有边(Edge)的列表(List)。也就是说,对于每个节点,我们可以通过它所在的键(Node)在 Map 中找到一个对应的值(List<Edge>),该值包含了该节点所连接的所有边。
举个例子,如果我们有一个图 G,其中包含了节点 A、B、C,以及它们之间的边,那么 edges 可以表示为:
```java
Map<Node, List<Edge>> edges = new HashMap<>();
edges.put(A, Arrays.asList(new Edge(B), new Edge(C)));
edges.put(B, Arrays.asList(new Edge(A), new Edge(C)));
edges.put(C, Arrays.asList(new Edge(A), new Edge(B)));
```
在这个例子中,我们将 A、B、C 三个节点分别映射到它们连接的边的列表。例如,节点 A 连接了 B 和 C 两个节点,所以它对应的列表包含了两个 Edge 对象,分别表示连接 A 和 B、连接 A 和 C 的两条边。其他节点的处理方式类似。
相关问题
解释一下这段代码:while (getline(conv_reader, line)) { if (check++ > 1) { std::vector <std::string> tokens = splitLine(line, '\t'); nodes_set_str.insert(tokens[0]); //add the first interactor to the list nodes_set_str.insert(tokens[1]); //add the second interactor to the list } } conv_reader.close(); // creating a node for each labels for (auto gene : nodes_set_str) { n = (*intActGraph).new_node(); nodes_set.insert(n); nodes_map[gene] = n; (*nodes_map_rev)[index(n)] = gene; } // creating edges std::ifstream conv_reader1(file); check = 0; while (getline(conv_reader1, line)) if (check++ > 0) { std::vector <std::string> tokens = splitLine(line, '\t'); n = nodes_map[tokens[0]]; v = nodes_map[tokens[1]]; e = (*intActGraph).new_edge(n, v); edges_set.insert(e); } conv_reader1.close();
这段代码的作用是根据读取的文件内容,构建一个图(Graph)。具体地说,程序首先使用 while 循环从文件 conv_reader 中读取每一行数据,并将其存储在 line 变量中。在每次循环中,程序检查 check 变量的值是否大于 1,如果是,则执行下面的操作:
程序调用 splitLine 函数,将 line 字符串按照 '\t' 分隔符进行切割,得到一个字符串向量 tokens。然后程序将 tokens 中的第一个元素和第二个元素分别插入到 nodes_set_str 集合中。这个集合用于存储所有的节点(即参与者),它是一个字符串类型的集合,用于去重。
接着,程序关闭文件 conv_reader,然后使用 for 循环遍历 nodes_set_str 集合中的每一个元素,为每一个元素创建一个节点(Node),并将这些节点存储在 nodes_set 集合中。程序还使用 nodes_map 和 nodes_map_rev 两个映射表,将每个节点与对应的参与者名称进行映射。其中,nodes_map 的类型是 std::unordered_map<Node*, std::string>,它将每个节点与对应的参与者名称进行映射;nodes_map_rev 的类型是 std::unordered_map<int, std::string>,它将每个节点的索引号(即节点在图中的位置)与对应的参与者名称进行映射。
最后,程序再次打开文件 conv_reader1,使用 while 循环从文件中读取每一行数据,并将其存储在 line 变量中。在每次循环中,程序检查 check 变量的值是否大于 0,如果是,则执行下面的操作:
程序调用 splitLine 函数,将 line 字符串按照 '\t' 分隔符进行切割,得到一个字符串向量 tokens。然后程序使用 nodes_map 映射表,将 tokens 中的第一个元素和第二个元素分别转换为对应的节点,并将这两个节点之间创建一条边(Edge),并将这些边存储在 edges_set 集合中。
for (Edge edge : node.edges) { GraphNode nextNode = edge.to; int newDist = distMap.get(node) + edge.weight; if (newDist < distMap.get(nextNode)) { distMap.put(nextNode, newDist); prevMap.put(nextNode, node); queue.remove(nextNode); queue.offer(nextNode); } } } //构造路径 List<GraphNode> path = new ArrayList<>(); GraphNode node = endNode; while (prevMap.containsKey(node)) { path.add(0, node); node = prevMap.get(node); }这些代码分别是什么意思
这段代码是实现 Dijkstra 算法来解决最短路径问题的,具体含义如下:
1. 首先,我们需要一个队列(queue)来存储待处理的节点,以及两个 map 分别存储每个节点的最短距离(distMap)和前驱节点(prevMap)。
2. 然后,我们将起始节点加入队列中,并将其最短距离设为 0。
3. 接下来,我们开始循环处理队列中的节点,直到队列为空。对于每个节点,我们遍历其所有出边,计算出到达相邻节点的新距离,如果新距离比原来存储的距离更小,则更新该节点的最短距离和前驱节点,并将该节点重新加入队列中。
4. 最后,我们可以通过 prevMap 追溯出从起点到终点的最短路径,并将其存储在一个列表(path)中返回。
总之,这段代码实现了 Dijkstra 算法来计算图中两个节点之间的最短路径,并将路径存储在一个列表中返回。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)