深度优先遍历邻接矩阵
时间: 2024-06-05 09:04:46 浏览: 22
深度优先遍历邻接矩阵是一种图的遍历算法,它从某个顶点出发,沿着一条路径遍历图,直到不能继续为止,然后返回之前的顶点,再从另一条路径继续遍历,直到所有顶点都被访问到。该算法的实现可以借助栈这种数据结构,每次访问一个未被访问过的邻接顶点时,将其入栈,然后递归遍历该顶点的邻接顶点。当某个顶点没有未被访问的邻接顶点时,回溯到上一个顶点,从栈中弹出该顶点并继续遍历它的其他未被访问的邻接顶点。深度优先遍历邻接矩阵的时间复杂度为O(V^2),其中V是顶点数。
相关问题
深度优先遍历邻接矩阵代码
深度优先遍历(Depth First Search, DFS)是一种用于遍历或搜索树或图的算法。在遍历时,从起点开始,尽可能深地搜索图的分支,直到没有未访问的节点为止,然后回溯到上一个节点,继续搜索下一个分支。邻接矩阵是一种表示图的常见方式,下面是深度优先遍历邻接矩阵的代码实现:
```
#include <iostream>
using namespace std;
const int MAXSIZE = 100;
class Graph {
private:
int vertex[MAXSIZE]; // 存储节点信息
int arc[MAXSIZE][MAXSIZE]; // 存储边信息
bool visited[MAXSIZE]; // 标记节点是否被访问过
int vertex_num, arc_num; // 节点数和边数
public:
Graph(int vnum, int anum) : vertex_num(vnum), arc_num(anum) {
for (int i = 0; i < vertex_num; ++i) {
for (int j = 0; j < vertex_num; ++j) {
arc[i][j] = 0;
}
}
}
~Graph() {}
void createGraph() {
cout << "请输入节点信息:" << endl;
for (int i = 0; i < vertex_num; ++i) {
cin >> vertex[i];
}
cout << "请输入边信息:" << endl;
for (int i = 0; i < arc_num; ++i) {
int vi, vj;
cin >> vi >> vj;
arc[vi][vj] = 1;
arc[vj][vi] = 1; // 如果是有向图,则只存储arc[vi][vj] = 1即可
}
}
void DFS(int v) {
visited[v] = true;
cout << vertex[v] << " ";
for (int i = 0; i < vertex_num; ++i) {
if (arc[v][i] == 1 && !visited[i]) {
DFS(i);
}
}
}
};
int main() {
int vnum, anum;
cout << "请输入节点数和边数:" << endl;
cin >> vnum >> anum;
Graph graph(vnum, anum);
graph.createGraph();
cout << "深度优先遍历序列为:" << endl;
for (int i = 0; i < vnum; ++i) {
if (!graph.visited[i]) {
graph.DFS(i);
}
}
return 0;
}
```
深度优先遍历邻接矩阵邻接矩阵转化为邻接链表
深度优先遍历是一种图遍历算法,它从某个顶点开始,递归地访问该顶点的所有邻接顶点,直到所有顶点都被访问为止。具体实现可以使用栈来存储访问过的节点,每次取出栈顶元素并将其未访问的邻居节点入栈,直到栈为空。
邻接矩阵是一种表示图的数据结构,它是一个二维数组,数组元素表示两个节点之间是否有边相连。邻接链表是另一种表示图的数据结构,它由若干个链表组成,每个链表表示一个节点以及与它相连的所有边。将邻接矩阵转化为邻接链表可以通过遍历邻接矩阵,将每个节点以及与它相连的边添加到对应的链表中。
具体步骤如下:
1. 创建一个包含n个链表的数组,n为图的节点数。
2. 遍历邻接矩阵的每个元素,如果元素值为1,则将其对应的节点和与之相连的节点添加到对应的链表中。
3. 重复步骤2直到遍历完整个邻接矩阵。