采用邻接表的dfs算法

邻接表的 DFS 算法步骤如下：

1. 首先，创建一个 visited 数组，记录每个节点是否被访问过，初始值为 false。

2. 从某个点开始遍历，将该点设置为已访问。

3. 遍历该点的所有邻居节点，如果邻居节点没有被访问过，则递归访问该邻居节点。

4. 重复步骤 3，直到该节点的所有邻居节点都被访问完毕。

5. 如果还存在未被访问的节点，则从这些节点中选择一个未被访问的节点，重复步骤 2。

6. 如果所有节点都被访问过，则遍历结束。

邻接表的 DFS 算法时间复杂度为 O(V+E)，其中 V 是节点数，E 是边数。邻接表适合表示稀疏图，当图是稠密图时，邻接矩阵更适合。

相关问题

c语言邻接表dfs算法代码

邻接表是图的一种常用存储结构，DFS（深度优先搜索）算法则是解决图遍历问题的一种常用算法。下面是C语言邻接表DFS算法的示例代码：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100  // 最大顶点数

// 邻接表结构体定义
typedef struct ArcNode {
    int adjvex;             // 邻接点的位置
    struct ArcNode *next;   // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode {
    int data;               // 存储顶点的数据
    ArcNode *firstarc;      // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;       // 邻接表
    int vexnum, arcnum;     // 图的顶点数和边数
} ALGraph;

// 标记顶点是否被访问过的数组，0表示未访问，1表示已访问
int visited[MAX_VERTEX_NUM] = {0};

// DFS函数
void DFS(ALGraph *G, int v) {
    ArcNode *p;
    visited[v] = 1;
    printf("%d ", G->vertices[v].data);  // 访问顶点v
    for (p = G->vertices[v].firstarc; p; p = p->next) {
        if (!visited[p->adjvex]) {       // 如果p未被访问，则递归访问它
            DFS(G, p->adjvex);
        }
    }
}

// 创建邻接表
void CreateALGraph(ALGraph *G) {
    int i, j, k;
    ArcNode *p;
    printf("请输入图的顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    printf("请输入每个顶点的值：");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    printf("请输入每条边的两个端点：\n");
    for (k = 0; k < G->arcnum; k++) {
        scanf("%d %d", &i, &j);
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->next = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
        // 因为是无向图，所以反向也要存储一次
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->next = G->vertices[j].firstarc;
        G->vertices[j].firstarc = p;
    }
}

int main() {
    ALGraph G;
    CreateALGraph(&G);
    printf("DFS遍历结果：");
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {  // 如果该顶点未被访问，则从它开始DFS遍历
            DFS(&G, i);
        }
    }
    return 0;
}

图的遍历算法 采用邻接表的DFS算法

图的遍历算法中，DFS（深度优先搜索）是一种常见的算法，可以用于查找图中的连通分量、寻找图中的路径等问题。以下是采用邻接表表示图的 DFS 算法的 Python 代码：

# 定义节点类
class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []

# 定义 DFS 函数
def dfs(node, visited):
    # 访问当前节点
    print(node.val)
    # 标记当前节点为已访问
    visited.add(node)
    # 递归遍历节点的邻居节点
    for neighbor in node.neighbors:
        if neighbor not in visited:
            dfs(neighbor, visited)

# 创建图
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node6 = Node(6)

node1.neighbors = [node2, node3]
node2.neighbors = [node1, node4, node5]
node3.neighbors = [node1, node6]
node4.neighbors = [node2, node5]
node5.neighbors = [node2, node4]
node6.neighbors = [node3]

# 遍历图
visited = set()
dfs(node1, visited)

在这段代码中，我们定义了一个 Node 类来表示图中的节点，每个节点包含一个值（val）和一个邻居节点列表（neighbors）。我们使用邻接表来表示整个图。然后，我们定义了一个 dfs 函数来进行深度优先遍历。我们从起始节点开始遍历，并对每个节点进行访问。在访问每个节点之前，我们将其标记为已访问，以避免重复访问。接着，我们递归遍历该节点的邻居节点，并对每个邻居节点进行同样的操作。最后，我们创建了一个 visited 集合来保存已经访问过的节点，以确保每个节点只被访问一次。