从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。

(1)深度优先遍历

深度优先遍历类似于数的先序遍历，是树的先序遍历的推广。

  1. 从图中某个顶点v出发，访问v。

  2. 找到刚访问过得顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问的顶点没有未被访问的邻接点为止。

  3. 返回前一个访问过得且扔有未被访问的邻接点的顶点，找到该顶点的下一个未被访问的邻接点，访问该顶点。

  4. 重复步骤2，3，直至图中所有顶点都被访问过。

深度优先遍历算法的实现

为了在遍历过程中便于区分顶点是否已经被访问，需附设访问标志组visited,其初值为false，一旦某个顶点被访问，则其相应的分量置为true。

# python代码实现邻接矩阵的深度优先遍历class MGraph():    def __init__(self):        self.vertex = []        self.matrix = []        self.numNodes = 0        self.numEdges = 0        self.visited = []    def createMGraph(self):        """创建无向图的邻接矩阵表示"""        self.numNodes = int(input("请输入顶点数："))        self.numEdges = int(input("请输入边数："))        for i in range(self.numNodes):            self.vertex.append(input("请输入一个顶点："))        for i in range(self.numNodes):            self.matrix.append([])            for j in range(self.numNodes):                self.matrix[i].append(0)  # 初始化邻接矩阵        for k in range(self.numEdges):  # 读入numEdges条边，建立邻接矩阵            i = int(input("请输入边(vi,vj)上的下标i:"))            j = int(input("请输入边(vi,vj)上的下标j:"))            self.matrix[i][j] = 1            self.matrix[j][i] = self.matrix[i][j]  # 因为是无向网图，矩阵对称    def viewMGraphStruct(self):        print(self.matrix)    def DFS(self, i):        """零阶矩阵的深度优先递归算法"""        self.visited[i] = True        print(self.vertex[i])        for j in range(self.numNodes):            if self.matrix[i][j] == 1 and not self.visited[j]:                self.DFS(j)    def DFSTraverse(self):        """邻接矩阵的深度优先遍历操作"""        self.visited = [False for i in range(self.numNodes)]        for i in range(self.numNodes):            if not self.visited[i]:  # 对未访问过的顶点调用DFS，若为连通图仅执行一次                self.DFS(i)if __name__ == '__main__':    G = MGraph()    G.createMGraph()    G.viewMGraphStruct()    print("深度优先遍历结果如下：")    G.DFSTraverse()

此代码包含了无向图的邻接矩阵存储方式的创建，以及深度优先遍历算法,既能遍历连通图也能遍历非联通图。

以上面的图为例，代码运行后，我们输入图的信息创建图，生成的邻接矩阵以及深度优先遍历结果如下：

邻接矩阵：[[0, 1, 0, 0, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 0, 1, 0, 1], [0, 1, 0, 1, 0, 0, 0, 0, 1], [0, 0, 1, 0, 1, 0, 1, 1, 1], [0, 0, 0, 1, 0, 1, 0, 1, 0], [1, 0, 0, 0, 1, 0, 1, 0, 0], [0, 1, 0, 1, 0, 1, 0, 1, 0], [0, 0, 0, 1, 1, 0, 1, 0, 0], [0, 1, 1, 1, 0, 0, 0, 0, 0]]
深度优先遍历结果如下：ABCDEFGHI

python代码实现邻接表的深度优先遍历：

class Vertex(object):    """创建Vertex类，用来存放顶点信息（包括data和firstEdge）"""    def __init__(self, data=None):        self.data = data        self.firstEdge = Noneclass EdgeNode(object):    """ 创建Edge类，用来存放边信息（包括adjVex和next）；"""    def __init__(self, adjVex):        self.adjVex = adjVex        self.next = Noneclass ALGraph():    """无向图类"""    def __init__(self):        self.numNodes = 0        self.numEdges = 0        self.adjList = []        self.visited = []    def createALGraph(self):        self.numNodes = int(input("输入顶点数："))        self.numEdges = int(input("输入边数："))        for i in range(self.numNodes):  # 读入顶点信息，建立顶点表            v = Vertex()            self.adjList.append(v)            self.adjList[i].data = input("请输入顶点数据：")        for k in range(self.numEdges):  # 建立边表            i = int(input("请输入边(vi,vj)上的下标i:"))            j = int(input("请输入边(vi,vj)上的下标j:"))            e = EdgeNode(j)  # 实例化边节点            e.next = self.adjList[i].firstEdge  # 将e的指针指向当前顶点指向的节点            self.adjList[i].firstEdge = e  # 将当前顶点的指针指向e            e = EdgeNode(i)  # 实例化边节点            e.next = self.adjList[j].firstEdge  # 将e的指针指向当前顶点指向的节点            self.adjList[j].firstEdge = e  # 将当前顶点的指针指向e    def DFS(self, i):        """邻阶表的深度优先递归算法"""        self.visited[i] = True        print(self.adjList[i].data)        p = self.adjList[i].firstEdge        while p:            if not self.visited[p.adjVex]:                self.DFS(p.adjVex)            p = p.next    def DFSTraverse(self):        """邻接表的深度优先遍历操作"""        self.visited = [False for i in range(self.numNodes)]        for i in range(self.numNodes):            if not self.visited[i]:  # 对未访问过的顶点调用DFS，若为联通图仅执行一次                self.DFS(i)if __name__ == '__main__':    G = ALGraph()    G.createALGraph()    G.DFSTraverse()

遍历结果如下：

AFGHEDICB

(2)广度优先遍历

图的广度优先遍历就类似于树的层序遍历。

  1. 从图中某个顶点v出发，访问v。

  2. 依次访问v的各个未被访问过得邻接点。

  3. 分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。重复步骤3，直至图中所有已被访问的顶点的邻接点都被访问到。

广度优先遍历连通图

  1. 从图中某个顶点v出发，访问v，并置visited[v]的值为true，然后将v进队。
  2. 只要队列不为空，则重复下述操作：
  • 队头顶点u出队。
  • 依次检查u的所有邻接点w，如果visited[w]的值为false，则访问w,并置visited[w]的值为true。然后将w进队。

python实现邻接矩阵的广度优先遍历：

class Queue():    """队列类"""    def __init__(self):        self.queue = []    def Enqueue(self, data):        """入队操作"""        self.queue.append(data)    def Dequeue(self):        """出队操作"""        return self.queue.pop(0)    def isEmpty(self):        """判断队列是否为空"""        if len(self.queue) == 0:            return True        else:            return Falseclass MGraph():    def __init__(self):        self.vertex = []        self.matrix = []        self.numNodes = 0        self.numEdges = 0        self.visited = []    def createMGraph(self):        """创建无向图的邻接矩阵表示"""        self.numNodes = int(input("请输入顶点数："))        self.numEdges = int(input("请输入边数："))        for i in range(self.numNodes):            self.vertex.append(input("请输入一个顶点："))        for i in range(self.numNodes):            self.matrix.append([])            for j in range(self.numNodes):                self.matrix[i].append(0)  # 初始化邻接矩阵        for k in range(self.numEdges):  # 读入numEdges条边，建立邻接矩阵            i = int(input("请输入边(vi,vj)上的下标i:"))            j = int(input("请输入边(vi,vj)上的下标j:"))            self.matrix[i][j] = 1            self.matrix[j][i] = self.matrix[i][j]  # 因为是无向网图，矩阵对称    def viewMGraphStruct(self):        print(self.matrix)    def BFSTraverse(self):        """邻接矩阵的广度优先遍历操作"""        self.visited = [False for i in range(self.numNodes)]  # 初始化所有顶点状态为未访问状态        Q = Queue()  # 实例化队列Q        for i in range(self.numNodes):            if not self.visited[i]:  # 对未访问过的顶点进行处理                self.visited[i] = True  # 将当前顶点标记为已访问                print(self.vertex[i])  # 打印此顶点                Q.Enqueue(i)  # 将此顶点入队列                while not Q.isEmpty():  # 若队列不为空                    i = Q.Dequeue()  # 将队首元素出队列，赋值给i                    for j in range(self.numNodes):                        if self.matrix[i][j] == 1 and not self.visited[j]:  # 判断其他顶点，若与当前顶点存在边且未访问过                            self.visited[j] = True  # 将找到的此顶点标记为已访问                            print(self.vertex[j])  # 打印此顶点                            Q.Enqueue(j)  # 将此顶点入队列if __name__ == '__main__':    G = MGraph()    G.createMGraph()    G.viewMGraphStruct()    print("广度优先遍历结果如下：")    G.BFSTraverse()

邻接矩阵如下：

[[0, 1, 0, 0, 0, 1, 0, 0, 0], [1, 0, 1, 0, 0, 0, 1, 0, 1], [0, 1, 0, 1, 0, 0, 0, 0, 1], [0, 0, 1, 0, 1, 0, 1, 1, 1], [0, 0, 0, 1, 0, 1, 0, 1, 0], [1, 0, 0, 0, 1, 0, 1, 0, 0], [0, 1, 0, 1, 0, 1, 0, 1, 0], [0, 0, 0, 1, 1, 0, 1, 0, 0], [0, 1, 1, 1, 0, 0, 0, 0, 0]]

遍历结果如下：

ABFCGIEDH

python实现邻接表的广度优先遍历：

class Queue():    """队列类"""    def __init__(self):        self.queue = []    def Enqueue(self, data):        """入队操作"""        self.queue.append(data)    def Dequeue(self):        """出队操作"""        return self.queue.pop(0)    def isEmpty(self):        """判断队列是否为空"""        if len(self.queue) == 0:            return True        else:            return Falseclass Vertex(object):    """创建Vertex类，用来存放顶点信息（包括data和firstEdge）"""    def __init__(self, data=None):        self.data = data        self.firstEdge = Noneclass EdgeNode(object):    """ 创建Edge类，用来存放边信息（包括adjVex和next）；"""    def __init__(self, adjVex):        self.adjVex = adjVex        self.next = Noneclass ALGraph():    """无向图类"""    def __init__(self):        self.numNodes = 0        self.numEdges = 0        self.adjList = []        self.visited = []    def createALGraph(self):        self.numNodes = int(input("输入顶点数："))        self.numEdges = int(input("输入边数："))        for i in range(self.numNodes):  # 读入顶点信息，建立顶点表            v = Vertex()            self.adjList.append(v)            self.adjList[i].data = input("请输入顶点数据：")        for k in range(self.numEdges):  # 建立边表            i = int(input("请输入边(vi,vj)上的下标i:"))            j = int(input("请输入边(vi,vj)上的下标j:"))            e = EdgeNode(j)  # 实例化边节点            e.next = self.adjList[i].firstEdge  # 将e的指针指向当前顶点指向的节点            self.adjList[i].firstEdge = e  # 将当前顶点的指针指向e            e = EdgeNode(i)  # 实例化边节点            e.next = self.adjList[j].firstEdge  # 将e的指针指向当前顶点指向的节点            self.adjList[j].firstEdge = e  # 将当前顶点的指针指向e    def BFSTraverse(self):        """邻接表的深度优先遍历操作"""        self.visited = [False for i in range(self.numNodes)]        Q = Queue()        for i in range(self.numNodes):            if not self.visited[i]:  # 对未访问过的顶点进行处理                self.visited[i] = True  # 将当前顶点标记为已访问                print(self.adjList[i].data)  # 打印此顶点                Q.Enqueue(i)  # 将此顶点入队列                while not Q.isEmpty():  # 若队列不为空                    i = Q.Dequeue()  # 将队首元素出队列，赋值给i                    p = self.adjList[i].firstEdge  # 找到当前顶点的边表链的表头指针                    while p:                        if not self.visited[p.adjVex]:  # 若此顶点未被访问                            self.visited[p.adjVex] = True                            print(self.adjList[p.adjVex].data)                            Q.Enqueue(p.adjVex)  # 将此顶点入队列                        p = p.next  # 指针指向下一邻接点if __name__ == '__main__':    G = ALGraph()    G.createALGraph()    G.BFSTraverse()

遍历结果：

AFBGEICHD

本文部分概念内容来自：https://www.jianshu.com/p/d9ca383e2bd8，其余均为自创。