数据结构 算法 图的存储、遍历 深度优先搜索 广度优先搜索

#!/usr/bin/env python
# -*- coding:utf-8 -*-
import copy

graphNodeList = [] #图存储节点信息
graphAdjMatrix = [] #图邻接矩阵
searchNodeInfo = [] #深度优先搜索已经查找过的节点索引
searchResult = [] #深度优先搜索的结果
searchPath = []


#str切分后给列表赋值格式
def acquireNode():
    node_list = input("请输入途中所有的点，以空格分隔：")
    for nodeInfo in node_list.strip().split(" "):
        graphNodeList.append(nodeInfo)

#根据输入信息填写邻接矩阵
def acquireSideUndig():
    print("请输入图的所有边信息，格式为边的两个顶点，使用空格分隔。 eg:a b,如果全部信息输入完毕请输入end")
    while True:
        tempSide = input(">:")
        if tempSide.strip().lower() == "end":
            print("输入结束")
            break
        tempNodeList = tempSide.strip().split(" ")
        if len(tempNodeList) == 2:
            if tempNodeList[0] in graphNodeList and tempNodeList[1] in graphNodeList:
                createUndigraphAdjMatrix(tempNodeList[0], tempNodeList[1])
            else:
                print("边信息输入有误，请重新输入")
            continue
        else:
            print("输入有误请重新输入")
            continue

def acquireSideDig():
    print("请输入图的所有边信息，格式为边的两个顶点，使用空格分隔。 eg:a b,如果全部信息输入完毕请输入end")
    while True:
        tempSide = input(">:")
        if tempSide.strip().lower() == "end":
            print("输入结束")
            break
        tempNodeList = tempSide.strip().split(" ")
        if len(tempNodeList) == 2:
            if tempNodeList[0] in graphNodeList and tempNodeList[1] in graphNodeList:
                createDigraphAdjMatrix(tempNodeList[0], tempNodeList[1])
            else:
                print("边信息输入有误，请重新输入")
            continue
        else:
            print("输入有误请重新输入")
            continue

#初始化邻接矩阵;注意多维数组初始化格式以及数据的浅拷贝坑
def initGraphAdjMatrix(nodeNum):
    for row in range(nodeNum):
        tempList = []
        for column in range(nodeNum):
            tempList.append(0)
        graphAdjMatrix.append(tempList)

#根据输入顶点信息完成邻接表
def createUndigraphAdjMatrix(node0, node1):
    tempIndex1 = graphNodeList.index(node0)
    tempIndex2 = graphNodeList.index(node1)
    graphAdjMatrix[tempIndex1][tempIndex2] = 1
    graphAdjMatrix[tempIndex2][tempIndex1] = 1

def createDigraphAdjMatrix(node0, node1):
    tempIndex1 = graphNodeList.index(node0)
    tempIndex2 = graphNodeList.index(node1)
    graphAdjMatrix[tempIndex1][tempIndex2] = 1

#pRINT输出空格和换行的写法
def printAdjMatrix(nodeNum):
    for row in range(nodeNum):
        for column in range(nodeNum):
            print(graphAdjMatrix[row][column], end=" ")
        print("")

def mainUndigAdjMat():
    acquireNode()
    initGraphAdjMatrix(len(graphNodeList))
    acquireSideUndig()
    #printAdjMatrix(len(graphNodeList))

#递归调用需要记录每次调用过程中的临时变量就需要使用容器接收，
def graphDps(root):
    #每个搜索过的索引加入已搜索过的列表
    startIndex = graphNodeList.index(root)
    searchNodeInfo.append(startIndex)
    #每次搜索路径记录列表，记录每一个最终节点整个递归过程，
    searchPath.append(root)
    #遍历根节点的所有邻接点
    for index, value in enumerate(graphAdjMatrix[startIndex]):
        #如果邻接点未被搜索则递归调用，如果有邻接点搜索过则循环下一个邻接点
        if value == 1 and index not in searchNodeInfo:
            graphDps(graphNodeList[index])
    #满足深度搜索终止条件时将该节点的搜索路径存储在全局列表中，不满足则递归会持续调用深度搜索不会走到此处，并在搜索路径弹出该节点，因为该节点已经搜索过了递归调用也会返回上一个调用
    tempResult = copy.copy(searchPath)
    searchPath.pop()
    searchResult.append(tempResult)
    #直到有一个节点所有邻接点都是搜索过的节点，此时不再压栈递归，返回这个值


if __name__ == "__main__":
    mainUndigAdjMat()
    graphDps("1")
    searchResult.reverse()
    #print(searchResult)
    for i in searchResult:
        print(i, end=" ")