头歌实训作业答案c++图的邻接矩阵存储及遍历操作

头歌实训作业中的C++图数据结构通常使用邻接矩阵来表示，它是一个二维数组，其中行代表起点，列表示终点，值为边的存在与否（0或1）。以下是邻接矩阵存储的基本概念：

1. 存储：邻接矩阵是以二维数组的形式存在的，如果图是有向图，则矩阵是对称的（即A[i][j] = A[j][i]），无向图则非对称（A[i][j]和A[j][i]独立表示两个方向的边）。每个元素A[i][j] = 1 表示节点i到节点j有边相连，0表示没有。

2. 遍历操作：
- **广度优先搜索(BFS)**：从给定源节点开始，逐层扩展访问节点。可以使用队列来辅助实现，初始化队列为源节点，然后不断出队并添加其未访问过的相邻节点。

   void bfs(int start) {
       queue<int> q;
       vector<bool> visited(V, false);
       q.push(start);
       visited[start] = true;
       
       while (!q.empty()) {
           int u = q.front(); q.pop();
           // 访问u的所有邻居并标记为已访问
           for (int v : adj[u]) {
               if (!visited[v]) {
                   visited[v] = true;
                   q.push(v);
               }
           }
       }
   }

- **深度优先搜索(DFS)**：从给定源节点开始，尽可能深地探索路径。可以使用栈或递归实现，先访问当前节点的所有相邻节点，然后再回溯。

   void dfs(int start) {
       vector<bool> visited(V, false);
       dfs_util(start, visited);
   }
   void dfs_util(int node, vector<bool>& visited) {
       visited[node] = true;
       // 探索所有相邻节点
       for (int neighbor : adj[node]) {
           if (!visited[neighbor])
               dfs_util(neighbor, visited);
       }
   }