无向图的邻接表的DFS代码实现
时间: 2023-11-05 18:12:17 浏览: 56
下面是无向图邻接表的DFS代码实现,其中假设图用邻接表存储,visited数组记录每个节点是否被访问过:
```
void DFS(vector<int> adjList[], int start, bool visited[]) {
visited[start] = true;
cout << start << " ";
for (int i = 0; i < adjList[start].size(); i++) {
int v = adjList[start][i];
if (!visited[v]) {
DFS(adjList, v, visited);
}
}
}
```
其中,`adjList`是邻接表,`start`是起始节点,`visited`数组记录每个节点是否被访问过。在每次访问一个节点时,将其标记为已访问,并输出节点值。然后递归访问所有与该节点相邻的未访问过的节点。
相关问题
无向图的邻接表的代码实现
无向图的邻接表可以使用一个数组来表示,数组中的每个元素都是一个链表,链表中存储了与该顶点相邻的所有顶点。可以使用 STL 中的 vector 和 list 来实现。以下是一个简单的 C++ 代码示例:
```cpp
#include <iostream>
#include <vector>
#include <list>
using namespace std;
// 无向图邻接表的实现
class Graph {
public:
Graph(int V) {
this->V = V;
adjList.resize(V);
}
// 添加边
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u);
}
// 打印邻接表
void printAdjList() {
for (int i = 0; i < V; ++i) {
cout << i << ": ";
for (auto v : adjList[i]) {
cout << v << " ";
}
cout << endl;
}
}
private:
int V; // 顶点数
vector<list<int>> adjList; // 邻接表
};
int main() {
Graph g(6);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(2, 5);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.printAdjList();
return 0;
}
```
输出结果为:
```
0:
1: 2 3
2: 1 4 5
3: 1 4
4: 2 3 5
5: 2 4
```
其中,每行的第一个数字表示顶点的编号,后面的数字表示与该顶点相邻的顶点编号。
无向图的邻接表的代码实现(不使用STL)
如果不使用 STL,可以使用指针数组和动态数组来实现无向图的邻接表。以下是一个不使用 STL 的 C++ 代码示例:
```cpp
#include <iostream>
using namespace std;
// 邻接表中链表的节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int v) : val(v), next(nullptr) {}
};
// 无向图邻接表的实现
class Graph {
public:
Graph(int V) {
this->V = V;
adjList = new ListNode*[V];
for (int i = 0; i < V; ++i) {
adjList[i] = nullptr;
}
}
// 添加边
void addEdge(int u, int v) {
// 在 u 的邻接表中添加 v
ListNode* node1 = new ListNode(v);
node1->next = adjList[u];
adjList[u] = node1;
// 在 v 的邻接表中添加 u
ListNode* node2 = new ListNode(u);
node2->next = adjList[v];
adjList[v] = node2;
}
// 打印邻接表
void printAdjList() {
for (int i = 0; i < V; ++i) {
cout << i << ": ";
ListNode* node = adjList[i];
while (node != nullptr) {
cout << node->val << " ";
node = node->next;
}
cout << endl;
}
}
private:
int V; // 顶点数
ListNode** adjList; // 邻接表
};
int main() {
Graph g(6);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(2, 5);
g.addEdge(3, 4);
g.addEdge(4, 5);
g.printAdjList();
return 0;
}
```
输出结果与使用 STL 的实现相同:
```
0:
1: 3 2
2: 1 5 4
3: 1 4
4: 3 5 2
5: 4 2
```
其中,每行的第一个数字表示顶点的编号,后面的数字表示与该顶点相邻的顶点编号。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)