使用Bag数据结构在图形实现API中相比其他数据结构（如Set或Linkedlist）有哪些优势？

Question

以下是与问题相关的示例代码。该API试图将一个邻接表表示的图实现为一个由图中每个顶点索引的Bag数组。

public class Graph{

private final int V;          //no. of vertices
private Bag<Integer>[] adj;  // A bag for each vertex to store all adjacent vertices
.
.
.
}

在这里，使用Bag相比于链表或集合有什么优势吗？我知道Bags是无序的，但为什么要选择无序列表，当它们既不能节省时间也不能节省空间呢？

- deepak

---

我认为这不是一个好的表示方式。图通常通过每个顶点的邻接矩阵或邻接表来实现。邻接表不应该有重复项，因此对于“Bag”来说并没有真正的优势，而且它可能会引入不应存在的重复项。 - RealSkeptic

Answer 1

每种数据结构都可以在不同的情况下使用： Set（特别是HashSet）可以用作无序唯一元素列表。另一方面，Bags 是多重集合（无序集合可能包含重复元素）。

至于LinkedList，它们提供更容易的链接操作，即在不同位置添加元素更加容易（常数时间）。

- nitishagar

---

只有当我们已经有指向特定位置的迭代器时，在链表中添加元素才是常数时间。很多时候，我们需要花费线性时间来迭代到所需位置。 - Steve M

@SteveM 是的，你说得对，这就是为什么我想强调更容易的链接操作 :) - nitishagar

Answer 2

一个袋子通常使用二叉搜索树或哈希表实现，这样可以使搜索时间复杂度为O(log n)或O(1)，而链表的搜索时间复杂度为O(n)。

Set只允许唯一的元素，如果需要存储重复元素则需要使用Bag。Java Collections库中的TreeSet或HashSet分别可以提供O(log n)或O(1)的搜索时间复杂度。

一般来说，当你经常需要执行搜索或删除操作时，Set或Bag接口会更适合。如果你只需要在集合末尾添加元素并迭代它，那么两者之间没有太大的区别。

- Steve M

---

这里是图形数据结构的实际代码，因为代码是由非常知名的教授编写的，所以这个问题具有重要的观察意义。我也在调查并看看是否发现了什么重要的东西。 - vivek

在 Bag 上执行 delete 操作？Bag 不支持删除元素。请参阅 https://algs4.cs.princeton.edu/13stacks/。 - Janac Meena

@JanacMeena，一些 Bag 的实现确实支持删除元素。 - Steve M

Answer 3

除了其他答案提到的内容，Bag 和其他无序数据结构（如 Set）之间的主要区别在于，一旦添加了元素，Bag 不支持删除元素。

一个例子是特殊的日志系统，我们永远不打算删除过去的插入。或者确保高并发系统中的不可变性。

请参阅 https://algs4.cs.princeton.edu/13stacks/ 以了解 Bag 与其他数据结构的准确描述和比较。

- Janac Meena

Answer 4

数据类型，如bag、queue和stack，在指定下一个要移除或检查的对象方面有所不同。

Bag是一个集合，不支持删除项目。Bag的目的是为客户提供收集项目的能力，然后迭代这些项目。

API Bag（Java）

public class Bag<Item> implements Iterable<Item>
    Bag() // creates an empty bag
    void add(Item item)
    boolean isEmpty()
    int size()

Bag.java

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Bag<Item> implements Iterable<Item> {
    private Node<Item> first;
    private int n;

    private static class Node<Item> {
        private Item item;
        private Node<Item> next;
    }

    public Bag() {
        first = null;
        n = 0;
    }

    public boolean isEmpty() {
        return first == null;
    }

    public int size() {
        return n;
    }

    public void add(Item item) {
        Node<Item> oldfirst = first;
        first = new Node<Item>();
        first.item = item;
        first.next = oldfirst;
        n++;
    }

    public Iterator<Item> iterator()  {
        return new LinkedIterator(first);
    }

    private class LinkedIterator implements Iterator<Item> {
        private Node<Item> current;

        public LinkedIterator(Node<Item> first) {
            current = first;
        }

        public boolean hasNext()  { return current != null;                     }
        public void remove()      { throw new UnsupportedOperationException();  }

        public Item next() {
            if (!hasNext()) throw new NoSuchElementException();
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}

- Sabina Orazem

---

不完全是，一个“bag”是一个多重集合。 它是一个集合，但允许多个重复项。 http://www.cs.umd.edu/class/spring2017/cmsc132-050X/projects/BagsAndDenseTrees/doc/student_classes/Bag.html#:~:text=A%20%22bag%22%20is%20a%20data,an%20element%20to%20the%20bag. - Yan Khonski