题目1：建立一个具有n个结点的无向图的邻接矩阵和邻接表。 （1）、设计一个将邻接矩阵转换为邻接表的算法 （2）、设计一个将邻接表转换为邻接矩阵的算法 （3）、设计以邻接表为存储结构的图的广度优先搜索算法。 （4）、设计以邻接矩阵为存储结构的图的深度优先搜索算法。

1. 建立邻接矩阵和邻接表

我们可以用一个二维数组来表示邻接矩阵，其中 $adj[i][j]=1$ 表示结点 $i$ 和结点 $j$ 之间有一条边，$adj[i][j]=0$ 表示没有边。用一个链表数组来表示邻接表，其中邻接表的第 $i$ 个链表存储与结点 $i$ 相邻的结点。

下面是用 C++ 实现的代码：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX = 100;

// 邻接矩阵转邻接表
void AdjMatrixToList(int adj[][MAX], int n, int head[], int ver[], int nxt[], int tot) {
  tot = 0;
  memset(head, -1, sizeof(head));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (adj[i][j] == 1) {
        ver[++tot] = j;
        nxt[tot] = head[i];
        head[i] = tot;
      }
    }
  }
}

// 邻接表转邻接矩阵
void AdjListToMatrix(int head[], int ver[], int nxt[], int adj[][MAX], int n) {
  memset(adj, 0, sizeof(adj));
  for (int i = 1; i <= n; i++) {
    for (int j = head[i]; j != -1; j = nxt[j]) {
      adj[i][ver[j]] = 1;
    }
  }
}

// 图的广度优先搜索
void BFS(int head[], int ver[], int nxt[], int n, int s) {
  int q[MAX], vis[MAX] = {0}, front = 0, rear = 0;
  vis[s] = 1;
  q[++rear] = s;
  while (front < rear) {
    int u = q[++front];
    cout << u << " ";
    for (int i = head[u]; i != -1; i = nxt[i]) {
      int v = ver[i];
      if (!vis[v]) {
        vis[v] = 1;
        q[++rear] = v;
      }
    }
  }
}

// 图的深度优先搜索
void DFS(int adj[][MAX], int n, int u, int vis[]) {
  vis[u] = 1;
  cout << u << " ";
  for (int i = 1; i <= n; i++) {
    if (adj[u][i] && !vis[i]) {
      DFS(adj, n, i, vis);
    }
  }
}

int main() {
  int n, m;
  int adj[MAX][MAX], head[MAX], ver[MAX * 2], nxt[MAX * 2], tot = 0;

  // 输入节点数和边数
  cout << "请输入节点数和边数: ";
  cin >> n >> m;

  // 初始化邻接矩阵和邻接表
  memset(adj, 0, sizeof(adj));
  memset(head, -1, sizeof(head));

  // 输入边的信息
  for (int i = 0; i < m; i++) {
    int u, v;
    cout << "请输入第" << i + 1 << "条边的两个端点: ";
    cin >> u >> v;
    adj[u][v] = 1;
    adj[v][u] = 1; // 无向图邻接矩阵对称
    ver[++tot] = v;
    nxt[tot] = head[u];
    head[u] = tot;
    ver[++tot] = u;
    nxt[tot] = head[v];
    head[v] = tot;
  }

  // 输出邻接矩阵
  cout << "邻接矩阵: " << endl;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cout << adj[i][j] << " ";
    }
    cout << endl;
  }

  // 输出邻接表
  cout << "邻接表: " << endl;
  for (int i = 1; i <= n; i++) {
    cout << i << ": ";
    for (int j = head[i]; j != -1; j = nxt[j]) {
      cout << ver[j] << " ";
    }
    cout << endl;
  }

  // 广度优先搜索
  cout << "广度优先搜索结果: ";
  BFS(head, ver, nxt, n, 1);
  cout << endl;

  // 深度优先搜索
  cout << "深度优先搜索结果: ";
  int vis[MAX] = {0};
  DFS(adj, n, 1, vis);
  cout << endl;

  return 0;
}

2. 邻接矩阵转邻接表

我们可以遍历邻接矩阵，将每条边的两个端点在邻接表中对应的链表中加入一个新的结点。具体来说，我们可以遍历邻接矩阵中所有非零元素，将邻接矩阵中第 $i$ 行第 $j$ 列的元素 $adj[i][j]$ 对应的邻接表中的结点 $ver$ 加入 $j$，并将 $ver$ 插入到链表头 $head[i]$ 中。这里需要注意的是，因为是无向图，所以对于每条边，我们需要在邻接表中同时插入两个结点，分别对应这条边的两个端点。

下面是用 C++ 实现的代码：

void AdjMatrixToList(int adj[][MAX], int n, int head[], int ver[], int nxt[], int tot) {
  tot = 0;
  memset(head, -1, sizeof(head));
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (adj[i][j] == 1) {
        ver[++tot] = j;
        nxt[tot] = head[i];
        head[i] = tot;
      }
    }
  }
}

3. 邻接表转邻接矩阵

我们可以遍历邻接表，将每条边的两个端点在邻接矩阵中对应的元素设为 $1$。具体来说，我们可以遍历邻接表中的所有结点，对于每个结点 $ver_i$，遍历以 $ver_i$ 为起点的所有边，将邻接矩阵中第 $i$ 行第 $j$ 列的元素设为 $1$。

下面是用 C++ 实现的代码：

void AdjListToMatrix(int head[], int ver[], int nxt[], int adj[][MAX], int n) {
  memset(adj, 0, sizeof(adj));
  for (int i = 1; i <= n; i++) {
    for (int j = head[i]; j != -1; j = nxt[j]) {
      adj[i][ver[j]] = 1;
    }
  }
}

4. 图的广度优先搜索

广度优先搜索（BFS）使用队列来实现，每次取出队列的头结点，遍历它的所有相邻结点，将未访问的结点入队，并标记为已访问。下面是用 C++ 实现的代码：

void BFS(int head[], int ver[], int nxt[], int n, int s) {
  int q[MAX], vis[MAX] = {0}, front = 0, rear = 0;
  vis[s] = 1;
  q[++rear] = s;
  while (front < rear) {
    int u = q[++front];
    cout << u << " ";
    for (int i = head[u]; i != -1; i = nxt[i]) {
      int v = ver[i];
      if (!vis[v]) {
        vis[v] = 1;
        q[++rear] = v;
      }
    }
  }
}

5. 图的深度优先搜索

深度优先搜索（DFS）使用递归或栈来实现。下面是用递归实现的代码：

void DFS(int adj[][MAX], int n, int u, int vis[]) {
  vis[u] = 1;
  cout << u << " ";
  for (int i = 1; i <= n; i++) {
    if (adj[u][i] && !vis[i]) {
      DFS(adj, n, i, vis);
    }
  }
}