数据结构实验三 图的深度优先搜索

以下是数据结构实验三中图的深度优先搜索的算法实现和代码整合：

1. 数据结构

定义一个Graph类，包含顶点数目和邻接矩阵两个属性。

2. 栈操作函数

定义一个栈类，包含栈顶指针和栈元素两个属性，以及入栈、出栈、判断栈是否为空等操作函数。

3. 深度优先搜索遍历

定义一个dfs函数，以起始顶点和访问标记数组为参数，使用递归实现深度优先搜索遍历。

4. 创建图

定义一个createGraph函数，以顶点数目和邻接矩阵为参数，创建一个Graph对象。

5. 主函数及DFS主函数

定义一个main函数，以邻接矩阵为输入，调用createGraph函数创建图，并调用dfs函数进行深度优先搜索遍历。

6. 输出生成树信息

在dfs函数中，每次访问一个顶点时，将其加入生成树中，并输出生成树信息。

7. 代码整合

class Graph:
    def __init__(self, num_vertices, adj_matrix):
        self.num_vertices = num_vertices
        self.adj_matrix = adj_matrix

class Stack:
    def __init__(self):
        self.top = -1
        self.items = []

    def is_empty(self):
        return self.top == -1

    def push(self, item):
        self.top += 1
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            return None
        else:
            self.top -= 1
            return self.items.pop()

def dfs(vertex, visited, graph):
    visited[vertex] = True
    print(vertex, end=' ')
    for i in range(graph.num_vertices):
        if graph.adj_matrix[vertex][i] == 1 and not visited[i]:
            dfs(i, visited, graph)

def createGraph(num_vertices, adj_matrix):
    graph = Graph(num_vertices, adj_matrix)
    return graph

def main(adj_matrix):
    num_vertices = len(adj_matrix)
    graph = createGraph(num_vertices, adj_matrix)
    visited = [False] * num_vertices
    for i in range(num_vertices):
        if not visited[i]:
            dfs(i, visited, graph)

adj_matrix = [[0, 1, 1, 0, 0],
              [1, 0, 0, 1, 1],
              [1, 0, 0, 1, 0],
              [0, 1, 1, 0, 1],
              [0, 1, 0, 1, 0]]

main(adj_matrix)