(标签-深度优先|关键词-无向图)

Question

建立一无向图的邻接表存储结构，并构造其对应的深度优先搜索生成树或森林（该生成树或森林以children兄弟链表存储），按先序遍历该二叉链表，输出得到的序列。

Answer 1

当要建立一个无向图的邻接表存储结构时，可以使用数据结构来表示图中的每个顶点以及它们之间的边。在邻接表中，每个顶点都用一个链表来表示与其相邻的顶点。下面是一个示例，展示了如何建立无向图的邻接表存储结构，并构造深度优先搜索生成树。

假设我们有以下无向图：

       A---B
      /     \
     C-------D
    / \     / \
   E---F---G---H

我们可以用邻接表存储结构来表示这个图：

A: B
B: A
C: D, E, F
D: C, G, H
E: C, F
F: C, E
G: D, H
H: D, G

每个顶点都对应一个链表，链表中存储与该顶点直接相邻的顶点。

接下来，我们可以使用深度优先搜索算法来构建生成树。生成树是由图中的顶点和边组成的一个子图，其中包含了从根节点开始访问其他节点的路径。

首先，选择一个起始顶点作为根节点。然后，从根节点开始进行深度优先搜索，访问与当前节点相邻且未被访问过的节点，并将其添加到生成树中。这个过程将递归地进行，直到所有节点都被访问过。

对于上述无向图，我们选择顶点A作为根节点，可以构建以下深度优先搜索生成树：

A
└── B
C
├── D
│   ├── G
│   └── H
└── E
    └── F

最后，按照先序遍历二叉链表的方式，输出生成树的节点序列为：A, B, C, D, G, H, E, F。

要使用C语言实现无向图的邻接表存储结构和深度优先搜索生成树，你可以定义适当的数据结构和编写相应的算法。以下是一个简单的示例代码，展示了如何在C语言中实现这一功能：

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

// 邻接表中的顶点
typedef struct Vertex {
    int data;
    struct Vertex* next;
} Vertex;

// 图的邻接表表示
typedef struct Graph {
    int numVertices;
    Vertex** adjLists;
    int* visited;
} Graph;

// 创建图
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;

    graph->adjLists = (Vertex**)malloc(numVertices * sizeof(Vertex*));
    graph->visited = (int*)malloc(numVertices * sizeof(int));

    for (int i = 0; i < numVertices; i++) {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }

    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    // 从src到dest的边
    Vertex* newNode = (Vertex*)malloc(sizeof(Vertex));
    newNode->data = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 从dest到src的边
    newNode = (Vertex*)malloc(sizeof(Vertex));
    newNode->data = src;
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

// 深度优先搜索
void DFS(Graph* graph, int vertex) {
    graph->visited[vertex] = 1;
    printf("%d ", vertex);

    Vertex* adjList = graph->adjLists[vertex];
    while (adjList != NULL) {
        int connectedVertex = adjList->data;
        if (graph->visited[connectedVertex] == 0) {
            DFS(graph, connectedVertex);
        }
        adjList = adjList->next;
    }
}

// 构建深度优先搜索生成树
void DFSTree(Graph* graph, int vertex) {
    graph->visited[vertex] = 1;

    Vertex* adjList = graph->adjLists[vertex];
    while (adjList != NULL) {
        int connectedVertex = adjList->data;
        if (graph->visited[connectedVertex] == 0) {
            printf("%d -> %d\n", vertex, connectedVertex);
            DFSTree(graph, connectedVertex);
        }
        adjList = adjList->next;
    }
}

// 主函数
int main() {
    int numVertices = 8;
    Graph* graph = createGraph(numVertices);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 3);
    addEdge(graph, 2, 4);
    addEdge(graph, 3, 5);
    addEdge(graph, 3, 6);
    addEdge(graph, 4, 6);
    addEdge(graph, 5, 7);
    addEdge(graph, 6, 7);

    printf("DFS traversal: ");
    DFS(graph, 0);
    printf("\n");

    printf("DFS Tree:\n");
    for (int i = 0; i < numVertices; i++) {
        if (graph->visited[i] == 0) {
            DFSTree(graph, i);
        }
    }

    return 0;
}

在上面的示例代码中，我们首先定义了Vertex和Graph两个结构体来表示邻接表和图。然后，我们实现了一系列函数来创建图、添加边、进行深度优先搜索以及构建深度优先搜索生成树。在主函数中，我们创建了一个包含8个顶点的图，并添加了边。然后，我们调用DFS函数进行深度优先搜索，并调用DFSTree函数构建深度优先搜索生成树。