C++实现图的邻接矩阵、邻接表及深度广度优先遍历

#include <iostream> #include <vector> #include <queue> using namespace std; void printMatrix(vector<vector<int>>& matrix) { for (int i = 0; i < matrix.size(); i++) { for (int j = 0; j < matrix[i].size(); j++) { cout << matrix[i][j] << " "; } cout << endl; } } void printAdjList(vector<vector<int>>& adjList) { for (int i = 0; i < adjList.size(); i++) { cout << i << ": "; for (int j = 0; j < adjList[i].size(); j++) { cout << adjList[i][j] << " "; } cout << endl; } } void dfs(vector<vector<int>>& adjList, vector<bool>& visited, int node) { visited[node] = true; cout << node << " "; for (int i = 0; i < adjList[node].size(); i++) { if (!visited[adjList[node][i]]) { dfs(adjList, visited, adjList[node][i]); } } } void bfs(vector<vector<int>>& adjList, vector<bool>& visited) { queue<int> q; q.push(0); while (!q.empty()) { int node = q.front(); q.pop(); visited[node] = true; cout << node << " "; for (int i = 0; i < adjList[node].size(); i++) { if (!visited[adjList[node][i]]) { q.push(adjList[node][i]); visited[adjList[node][i]] = true; } } } } int main() { vector<vector<int>> matrix = {{0, 5, 0, 7, 0, 0}, {0, 0, 4, 0, 0, 0}, {8, 0, 0, 0, 0, 9}, {0, 0, 5, 0, 0, 6}, {0, 0, 0, 5, 0, 0}, {3, 0, 0, 0, 1, 0}}; printMatrix(matrix); cout << endl; vector<vector<int>> adjList(matrix.size()); for (int i = 0; i < matrix.size(); i++) { for (int j = 0; j < matrix[i].size(); j++) { if (matrix[i][j] != 0) { adjList[i].push_back(j); } } } printAdjList(adjList); cout << endl; vector<bool> visited(matrix.size(), false); cout << "dfs: "; dfs(adjList, visited, 0); cout << endl << endl; cout << "bfs: "; fill(visited.begin(), visited.end(), false); bfs(adjList, visited); return 0; } ######[AI写代码神器 | 1517点数解答 | 2024-11-25 16:18:26]