2、建立一无向图的邻接表存储结构，并构造其对应的深度优先搜索生成树或森林（该生成树或森林以孩子兄弟链表存储），按先序遍历该二叉链表，输出得到的序列。

### 回答1：
建立无向图的邻接表存储结构，可以使用一个数组来存储每个顶点的信息，每个顶点的信息包括该顶点的编号和一个指向与该顶点相邻的顶点的链表。对于无向图，每个顶点的链表中存储的是与该顶点相邻的所有顶点。

构造深度优先搜索生成树或森林，可以使用递归的方式进行深度优先搜索，并在搜索过程中记录每个顶点的父节点和访问状态。对于无向图，生成的深度优先搜索生成树或森林是一棵或多棵以某个顶点为根节点的树，每个节点的孩子节点是该节点的所有未访问过的相邻节点。

将生成的深度优先搜索生成树或森林以孩子兄弟链表存储，可以使用一个二叉树来表示每个节点和其孩子节点。对于每个节点，其左子节点是其第一个孩子节点，右子节点是其下一个兄弟节点。按先序遍历该二叉链表，输出得到的序列即为深度优先搜索生成树或森林的先序遍历序列。

### 回答2：
无向图邻接表存储结构主要是将每个顶点作为数组的一个下标，该下标所对应的位置可以存储与该顶点相连的其他顶点，存储方式可以是链表。比如对于如下图所示的无向图：


邻接表的存储方式可以如下所示：

1 -> 2 -> 3 -> NULL
2 -> 1 -> 3 -> 4 -> NULL
3 -> 1 -> 2 -> 4 -> NULL
4 -> 2 -> 3 -> NULL

构造无向图的深度优先搜索生成树的过程，可以从任意一个顶点开始，将该顶点标记为已访问过，并将其加入生成树中，然后遍历该顶点相邻的顶点，再按照同样的方式递归遍历相邻的未被访问过的顶点。具体过程可参考如下图所示：


由于无向图可能是非连通的，因此对于每个未被访问过的顶点，也需要按照上述方式构造其所在的生成树。

生成的生成树或森林的孩子兄弟链表存储结构，每个结点除了存储其对应的顶点编号外，还需要存储其第一个孩子结点和下一个兄弟结点的指针。比如对于如下图所示的生成树：


对应的树结构可以如下所示：

1
|
2 -- 3 -- 4
|
5

其孩子兄弟链表存储结构可以如下所示：

1 - (2) - > 2 - (5) - > 5 - (NULL)
     |              |
     |            (3)
    (4)            |
     |              |
     v              v
   NULL         4 - (NULL)

通过先序遍历该二叉链表，输出得到的序列为 1 2 5 3 4。因为先序遍历的顺序是优先遍历根节点，再遍历其左子树，最后遍历其右子树。因此按照上图的链表结构，先输出1，然后进入1的左子树2，输出2，进入2的左子树5，输出5，已经到达子树的最左侧，所以返回2的右子树节点3，输出3，最后输出4。

### 回答3：
无向图的邻接表存储结构是一种非常常见的图存储方式。在邻接表中，通过一个数组来保存每个节点，每个节点都维护一个链表，用于存储与其相连的所有节点。

在深度优先搜索生成树或森林中，我们首先需要选择一个起点节点，从该节点开始遍历整个图。遍历过程中，我们记录下已经遍历过的节点，并将其添加到生成树或森林中。

在遍历过程中，若遇到一个没有访问过的节点，就将其加入到生成树或森林中，并且以该节点为起点，开始对其相邻的未访问过的节点进行深度优先搜索。整个过程可以使用递归实现。

遍历完成之后，我们得到的就是一个以孩子兄弟链表存储的生成树或森林。按照先序遍历该二叉链表，输出序列的过程可以使用递归实现。

下面是一个使用邻接表存储结构和深度优先搜索生成树的示例代码：

#include <iostream>
#include <vector>

using std::vector;

struct Node {
  int val;
  Node *child;
  Node *sibling;
  Node(int v) : val(v), child(nullptr), sibling(nullptr) {}
};

void addEdge(vector<vector<int>>& graph, int u, int v) {
  graph[u].push_back(v);
  graph[v].push_back(u);
}

Node* dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
  visited[node] = true;
  Node* cur = new Node(node);
  Node* tail = cur;
  for (int i : graph[node]) {
    if (!visited[i]) {
      Node* child = dfs(graph, visited, i);
      if (tail->child == nullptr) {
        tail->child = child;
      } else {
        tail->sibling = child;
      }
      tail = child;
    }
  }
  return cur;
}

void preOrder(Node* root) {
  if (root == nullptr) {
    return;
  }
  std::cout << root->val << " ";
  preOrder(root->child);
  preOrder(root->sibling);
}

int main() {
  vector<vector<int>> graph(6);  // 6 nodes
  addEdge(graph, 0, 1);
  addEdge(graph, 0, 2);
  addEdge(graph, 0, 4);
  addEdge(graph, 1, 3);
  addEdge(graph, 4, 5);

  vector<bool> visited(6, false);
  vector<Node*> forest;
  for (int i = 0; i < 6; ++i) {
    if (!visited[i]) {
      forest.push_back(dfs(graph, visited, i));
    }
  }

  for (Node* root : forest) {
    preOrder(root);
  }

  return 0;
}

输出结果为：0 1 3 2 4 5

其中，我们假设这张无向图有6个节点，然后将它的边加入到邻接表中。接着，我们从每个没有被访问过的节点开始进行深度优先搜索，并且将生成的树加入到森林中。最后，按照先序遍历输出所有的生成树。