建立一个图的邻接表，在实现图的深度优先遍历序列

好的，以下是建立图的邻接表和深度优先遍历序列的示例代码（使用Python语言实现）：

# 建立图的邻接表
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# 深度优先遍历序列
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=' ')
    for next_node in graph[start]:
        if next_node not in visited:
            dfs(graph, next_node, visited)

# 从起点A开始进行深度优先遍历
dfs(graph, 'A')

输出结果为：`A B D E F C`，表示图的深度优先遍历序列为 A → B → D → E → F → C。

相关问题

建立一个图的邻接表，再实现图的深度优先遍历序列

建立图的邻接表可以使用一个字典来表示，其中字典的键为节点，值为该节点所连接的其他节点的列表。

例如，对于以下的无向图：

A — B — C
|   |   |
D — E — F

可以用以下的邻接表来表示：

{
    "A": ["B", "D"],
    "B": ["A", "C", "E"],
    "C": ["B", "F"],
    "D": ["A", "E"],
    "E": ["B", "D", "F"],
    "F": ["C", "E"]
}

下面是一个实现图的深度优先遍历序列的 Python 代码：

def dfs(graph, start):
    visited = set()
    stack = [start]
    result = []
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            result.append(node)
            stack.extend(reversed(graph[node]))
    return result

该函数接受两个参数：邻接表 `graph` 和起始节点 `start`。它使用一个集合 `visited` 来跟踪已经访问过的节点，使用一个栈 `stack` 来存储待访问的节点，使用一个列表 `result` 来存储遍历序列。

在每次迭代中，从栈中弹出一个节点 `node`。如果该节点没有被访问过，则将其添加到 `visited` 集合中，并将其添加到遍历序列 `result` 中。然后将该节点所连接的其他节点按相反的顺序压入栈中，以便下一次访问。这个过程一直持续到栈为空。

以下是使用上述代码对上面的图进行深度优先遍历的示例：

graph = {
    "A": ["B", "D"],
    "B": ["A", "C", "E"],
    "C": ["B", "F"],
    "D": ["A", "E"],
    "E": ["B", "D", "F"],
    "F": ["C", "E"]
}

print(dfs(graph, "A"))  # 输出: ['A', 'D', 'E', 'F', 'C', 'B']

C语言基于邻接表建立一个图，对图进行深度优先遍历及广度优先遍历。

好的，下面是C语言基于邻接表建立一个图，对图进行深度优先遍历及广度优先遍历的代码实现。

首先我们需要定义一个邻接表的结构体，用来存储图：

#define MAX_VERTEX_NUM 100

// 邻接表节点的结构体
typedef struct ArcNode {
    int adjvex;             // 邻接节点的编号
    struct ArcNode *next;   // 指向下一个邻接节点的指针
} ArcNode;

// 顶点节点的结构体
typedef struct {
    int data;               // 顶点的数据
    ArcNode *firstarc;      // 指向第一个邻接节点的指针
} VNode;

// 邻接表的结构体
typedef struct {
    VNode vertices[MAX_VERTEX_NUM];    // 顶点数组
    int vexnum;                         // 顶点数
    int arcnum;                         // 边数
} ALGraph;

然后我们需要实现一个初始化邻接表的函数：

// 初始化邻接表
void InitGraph(ALGraph *G)
{
    int i;
    G->vexnum = 0;
    G->arcnum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertices[i].data = 0;
        G->vertices[i].firstarc = NULL;
    }
}

接下来，我们需要实现添加边的函数：

// 添加边
void AddArc(ALGraph *G, int v, int w)
{
    ArcNode *p;
    p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = w;
    p->next = G->vertices[v].firstarc;
    G->vertices[v].firstarc = p;
    G->arcnum++;
}

然后，我们需要实现深度优先遍历的函数：

// 深度优先遍历
void DFS(ALGraph *G, int v, int visited[])
{
    ArcNode *p;
    visited[v] = 1;                 // 标记节点为已访问
    printf("%d ", G->vertices[v].data);  // 访问节点
    p = G->vertices[v].firstarc;
    while (p != NULL) {
        if (!visited[p->adjvex]) {  // 如果邻居节点未被访问过，则递归访问
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

最后，我们需要实现广度优先遍历的函数：

// 广度优先遍历
void BFS(ALGraph *G, int v)
{
    int visited[MAX_VERTEX_NUM] = {0};  // 标记数组，记录节点是否被访问过
    int q[MAX_VERTEX_NUM];              // 队列
    int front = 0, rear = 0;            // 队头和队尾指针
    int i, j;
    ArcNode *p;
    q[rear++] = v;                      // 将起点节点入队
    visited[v] = 1;                     // 标记起点节点为已访问
    while (front < rear) {
        i = q[front++];                 // 取出队首节点
        printf("%d ", G->vertices[i].data);  // 访问该节点
        p = G->vertices[i].firstarc;
        while (p != NULL) {
            j = p->adjvex;
            if (!visited[j]) {          // 如果邻居节点未被访问过，则将其入队
                q[rear++] = j;
                visited[j] = 1;
            }
            p = p->next;
        }
    }
}

完整的代码如下：

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

#define MAX_VERTEX_NUM 100

// 邻接表节点的结构体
typedef struct ArcNode {
    int adjvex;             // 邻接节点的编号
    struct ArcNode *next;   // 指向下一个邻接节点的指针
} ArcNode;

// 顶点节点的结构体
typedef struct {
    int data;               // 顶点的数据
    ArcNode *firstarc;      // 指向第一个邻接节点的指针
} VNode;

// 邻接表的结构体
typedef struct {
    VNode vertices[MAX_VERTEX_NUM];    // 顶点数组
    int vexnum;                         // 顶点数
    int arcnum;                         // 边数
} ALGraph;

// 初始化邻接表
void InitGraph(ALGraph *G)
{
    int i;
    G->vexnum = 0;
    G->arcnum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertices[i].data = 0;
        G->vertices[i].firstarc = NULL;
    }
}

// 添加边
void AddArc(ALGraph *G, int v, int w)
{
    ArcNode *p;
    p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = w;
    p->next = G->vertices[v].firstarc;
    G->vertices[v].firstarc = p;
    G->arcnum++;
}

// 深度优先遍历
void DFS(ALGraph *G, int v, int visited[])
{
    ArcNode *p;
    visited[v] = 1;                 // 标记节点为已访问
    printf("%d ", G->vertices[v].data);  // 访问节点
    p = G->vertices[v].firstarc;
    while (p != NULL) {
        if (!visited[p->adjvex]) {  // 如果邻居节点未被访问过，则递归访问
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

// 广度优先遍历
void BFS(ALGraph *G, int v)
{
    int visited[MAX_VERTEX_NUM] = {0};  // 标记数组，记录节点是否被访问过
    int q[MAX_VERTEX_NUM];              // 队列
    int front = 0, rear = 0;            // 队头和队尾指针
    int i, j;
    ArcNode *p;
    q[rear++] = v;                      // 将起点节点入队
    visited[v] = 1;                     // 标记起点节点为已访问
    while (front < rear) {
        i = q[front++];                 // 取出队首节点
        printf("%d ", G->vertices[i].data);  // 访问该节点
        p = G->vertices[i].firstarc;
        while (p != NULL) {
            j = p->adjvex;
            if (!visited[j]) {          // 如果邻居节点未被访问过，则将其入队
                q[rear++] = j;
                visited[j] = 1;
            }
            p = p->next;
        }
    }
}

int main()
{
    ALGraph G;
    int n, m, i, v, w;
    int visited[MAX_VERTEX_NUM] = {0};  // 标记数组，记录节点是否被访问过
    printf("请输入顶点数和边数：\n");
    scanf("%d%d", &n, &m);
    InitGraph(&G);
    G.vexnum = n;
    printf("请输入顶点的数据：\n");
    for (i = 0; i < n; i++) {
        scanf("%d", &G.vertices[i].data);
    }
    printf("请输入每条边的起点和终点：\n");
    for (i = 0; i < m; i++) {
        scanf("%d%d", &v, &w);
        AddArc(&G, v, w);
    }
    printf("深度优先遍历结果为：\n");
    DFS(&G, 0, visited);
    printf("\n");
    printf("广度优先遍历结果为：\n");
    BFS(&G, 0);
    printf("\n");
    return 0;
}

在这个代码中，我们通过读入顶点数和边数，然后按照邻接表的方式存储图，并对图进行深度优先遍历和广度优先遍历，输出访问的节点序列。