用代码编写用邻接矩阵实现DFS
时间: 2023-04-06 08:03:05 浏览: 59
好的,以下是用邻接矩阵实现DFS的代码:
```python
def dfs(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited
# 示例
graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}
print(dfs(graph, 'A'))
```
希望能对你有所帮助!
相关问题
用代码编写用邻接矩阵实现DFS和BFS
可以的,以下是用邻接矩阵实现DFS和BFS的代码:
DFS:
```
void DFS(int v, bool visited[], int** graph, int n) {
visited[v] = true;
cout << v << " ";
for (int i = 0; i < n; i++) {
if (graph[v][i] && !visited[i]) {
DFS(i, visited, graph, n);
}
}
}
void DFS(int start, int** graph, int n) {
bool* visited = new bool[n];
for (int i = 0; i < n; i++) {
visited[i] = false;
}
DFS(start, visited, graph, n);
delete[] visited;
}
```
BFS:
```
void BFS(int start, int** graph, int n) {
bool* visited = new bool[n];
for (int i = 0; i < n; i++) {
visited[i] = false;
}
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
cout << v << " ";
for (int i = 0; i < n; i++) {
if (graph[v][i
编写一个c++代码实现以邻接矩阵为图的存储结构的dfs和bfs
以下是使用邻接矩阵为图的存储结构实现DFS和BFS的C++代码:
```c++
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 100;
int n, m; // n:顶点数,m:边数
int G[MAXN][MAXN]; // 邻接矩阵存储图
bool visited[MAXN]; // 标记每个结点是否被访问过
// 深度优先遍历
void DFS(int u) {
visited[u] = true; // 标记结点u已访问过
cout << u << " "; // 输出结点u
for (int v = 0; v < n; v++) { // 枚举结点u的所有邻居
if (G[u][v] && !visited[v]) { // 如果结点v是结点u的邻居且未被访问过
DFS(v); // 递归访问结点v
}
}
}
// 广度优先遍历
void BFS(int s) {
queue<int> q; // 定义队列q
visited[s] = true; // 标记结点s已访问过
q.push(s); // 将结点s入队
while (!q.empty()) { // 当队列不为空时
int u = q.front(); // 取出队首结点u
q.pop(); // 将结点u出队
cout << u << " "; // 输出结点u
for (int v = 0; v < n; v++) { // 枚举结点u的所有邻居
if (G[u][v] && !visited[v]) { // 如果结点v是结点u的邻居且未被访问过
visited[v] = true; // 标记结点v已访问过
q.push(v); // 将结点v入队
}
}
}
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[u][v] = G[v][u] = 1; // 无向图
}
// DFS遍历
cout << "DFS: ";
for (int u = 0; u < n; u++) {
if (!visited[u]) { // 如果结点u未被访问过
DFS(u); // 从结点u开始进行DFS遍历
}
}
cout << endl;
// BFS遍历
memset(visited, false, sizeof(visited)); // 初始化visited数组
cout << "BFS: ";
for (int u = 0; u < n; u++) {
if (!visited[u]) { // 如果结点u未被访问过
BFS(u); // 从结点u开始进行BFS遍历
}
}
cout << endl;
return 0;
}
```
其中,输入格式为:
```
n m
u1 v1
u2 v2
...
um vm
```
其中n表示结点数,m表示边数,接下来m行表示每条边的两个端点u和v。
输出为DFS遍历和BFS遍历的结果。