首页使用c++实现(1)、实现图的邻接表或邻接矩阵表示，并创建图； (2)、对邻接表或邻接矩阵表示的图实现深度优先遍历

使用c++实现(1)、实现图的邻接表或邻接矩阵表示，并创建图； (2)、对邻接表或邻接矩阵表示的图实现深度优先遍历

时间: 2024-12-29 13:33:50 浏览: 73

在C++中实现图的数据结构通常有邻接表和邻接矩阵两种方式： **1. 邻接表表示：** 邻接表是一种稀疏存储的图数据结构，它用一个数组（或者动态vector）存储每个节点的所有邻居。对于每个节点i，我们有一个链表或数组`adj[i]`，其中包含所有与节点i直接相连的节点。 ```cpp #include <iostream> #include <unordered_map> using namespace std; // 图节点 struct Node { int value; vector<Node*> neighbors; }; class GraphAdjacencyList { public: void addEdge(int src, int dest); void dfs(int start); private: unordered_map<int, Node*> nodes; // 存储节点及其值 }; ``` 实现添加边的方法`addEdge()` 和深度优先搜索`dfs()`: ```cpp void GraphAdjacencyList::addEdge(int src, int dest) { if (!nodes.count(src)) { nodes[src] = new Node{src}; } nodes[src]->neighbors.push_back(&nodes[dest]); } void GraphAdjacencyList::dfs(int start) { Node* curr = nodes[start]; cout << start << " "; for (Node* neighbor : curr->neighbors) { if (neighbor != &nodes[start]) { // 避免环路影响 dfs(*neighbor); } } } ``` **2. 邻接矩阵表示：** 邻接矩阵是一个二维数组，大小为n x n，其中n是节点的数量。如果节点i和j之间有一条边，则`matrix[i][j]`为1；反之则为0。 ```cpp class GraphAdjacencyMatrix { public: void addEdge(int src, int dest); void dfs(int start); private: bool matrix[100][100]; // 假设最多100个节点 }; void GraphAdjacencyMatrix::addEdge(int src, int dest) { matrix[src][dest] = true; } void GraphAdjacencyMatrix::dfs(int start) { // ...类似邻接表的dfs方法，通过索引访问矩阵元素 } ``` 以上代码展示了基本的邻接表和邻接矩阵的表示以及深度优先遍历的实现。

阅读全文