class adjMatrixGraph: # 构造方法，n个顶点m条边 def init(self,n,m): self.verNum = n #顶点数 self.edgeNum = m #边数 self.vertex = [0] * n #顶点列表 self.edge = [[0 for i in range(self.verNum)] \ for j in range(self.verNum)] #邻接矩阵二维列表 self.vis = [False] * n #顶点的访问列表，默认没访问过 def addVertex(self,ls): #添加顶点列表 self.vertex = ls def addEdge(self,fr,to):#添加边(fr,to) ifr = self.vertex.index(fr) #起点下标 ito = self.vertex.index(to) #终点下标 self.edge[ifr][ito] = self.edge[ito][ifr] = 1 #邻接矩阵 #邻接矩阵建图 def createGraph(): n,m = map(int,input().split()) #输入n个顶点和m条边 g = adjMatrixGraph(n,m) #创建无向图G g.addVertex(list(input().split())) #输入顶点列表 for i in range(m): #输入m条边 fr,to = input().split() g.addEdge(fr,to) return g 根绝上面代码编写一个求无向图度数的函数

可以编写一个名为 `degree` 的函数来求无向图的度数，该函数的参数为一个 `adjMatrixGraph` 类型的对象，返回一个包含每个顶点度数的列表。

代码如下：

def degree(graph):
    degrees = [0] * graph.verNum # 初始化每个顶点的度数为0
    for i in range(graph.verNum):
        for j in range(graph.verNum):
            if graph.edge[i][j] == 1: # 若有边相连，则度数加1
                degrees[i] += 1
    return degrees

该函数首先初始化每个顶点的度数为0，然后遍历邻接矩阵，如果有边相连，则将对应的顶点的度数加1，最后返回包含每个顶点度数的列表。

相关问题

class adjMatrixGraph: # 构造方法，n个顶点m条边 def init(self,n,m): self.verNum = n #顶点数 self.edgeNum = m #边数 self.vertex = [0] * n #顶点列表 self.edge = [[0 for i in range(self.verNum)] \ for j in range(self.verNum)] #邻接矩阵二维列表 self.vis = [False] * n #顶点的访问列表，默认没访问过 def addVertex(self,ls): #添加顶点列表 self.vertex = ls def addEdge(self,fr,to):#添加边(fr,to) ifr = self.vertex.index(fr) #起点下标 ito = self.vertex.index(to) #终点下标 self.edge[ifr][ito] = self.edge[ito][ifr] = 1 #邻接矩阵 #邻接矩阵建图 def createGraph(): n,m = map(int,input().split()) #输入n个顶点和m条边 g = adjMatrixGraph(n,m) #创建无向图G g.addVertex(list(input().split())) #输入顶点列表 for i in range(m): #输入m条边 fr,to = input().split() g.addEdge(fr,to) return g 根绝上面代码编写一个广度优先搜索得函数

以下是基于邻接矩阵的广度优先搜索算法实现：

from queue import Queue

class adjMatrixGraph:
    # 构造方法，n个顶点m条边
    def __init__(self, n, m):
        self.verNum = n  # 顶点数
        self.edgeNum = m  # 边数
        self.vertex = [0] * n  # 顶点列表
        self.edge = [[0 for i in range(self.verNum)] for j in range(self.verNum)]  # 邻接矩阵二维列表
        self.vis = [False] * n  # 顶点的访问列表，默认没访问过

    def addVertex(self, ls):
        # 添加顶点列表
        self.vertex = ls

    def addEdge(self, fr, to):
        # 添加边(fr,to)
        ifr = self.vertex.index(fr)  # 起点下标
        ito = self.vertex.index(to)  # 终点下标
        self.edge[ifr][ito] = self.edge[ito][ifr] = 1  # 邻接矩阵

    # 广度优先搜索
    def BFS(self, start):
        if start not in self.vertex:
            return None
        start_index = self.vertex.index(start)
        q = Queue()
        q.put(start_index)
        self.vis[start_index] = True
        while not q.empty():
            cur = q.get()
            print(self.vertex[cur], end=' ')
            for i in range(self.verNum):
                if self.edge[cur][i] and not self.vis[i]:
                    q.put(i)
                    self.vis[i] = True

其中，BFS方法为广度优先搜索算法实现。它首先判断起始顶点是否存在于顶点列表中，然后初始化队列并将起始顶点加入队列，将其标记为已访问。接下来，开始循环处理队列，取出队首元素，输出其对应的顶点，然后遍历该顶点的所有邻接点，将其加入队列，并标记为已访问。直到队列为空，搜索结束。

class adjMatrixGraph: # 构造方法，n个顶点m条边 def __init__(self,n,m): self.verNum = n #顶点数 self.edgeNum = m #边数 self.vertex = [0] * n #顶点列表 self.edge = [[0 for i in range(self.verNum)] \ for j in range(self.verNum)] #邻接矩阵二维列表 self.vis = [False] * n #顶点的访问列表，默认没访问过 def addVertex(self,ls): #添加顶点列表 self.vertex = ls def addEdge(self,fr,to):#添加边(fr,to) ifr = self.vertex.index(fr) #起点下标 ito = self.vertex.index(to) #终点下标 self.edge[ifr][ito] = self.edge[ito][ifr] = 1 #邻接矩阵 #邻接矩阵建图 def createGraph(): n,m = map(int,input().split()) #输入n个顶点和m条边 g = adjMatrixGraph(n,m) #创建无向图G g.addVertex(list(input().split())) #输入顶点列表 for i in range(m): #输入m条边 fr,to = input().split() g.addEdge(fr,to) return g 编写一个深度优先搜索得函数

以下是一个深度优先搜索函数的示例代码：

def DFS(graph, start):
    visited = [False] * graph.verNum  # 初始化所有顶点为未访问状态
    stack = []  # 栈用于存储待访问的顶点
    stack.append(start)  # 将起始顶点加入栈中
    while stack:
        # 取出栈顶元素作为当前访问的顶点
        cur = stack.pop()
        if not visited[cur]:
            visited[cur] = True  # 将当前顶点标记为已访问
            print(graph.vertex[cur], end=' ')  # 输出当前顶点的值
            # 将当前顶点的未访问过的邻居加入栈中
            for i in range(graph.verNum):
                if graph.edge[cur][i] == 1 and not visited[i]:
                    stack.append(i)

其中，`graph` 参数是一个 `adjMatrixGraph` 对象，`start` 参数是起始顶点的下标。该函数首先初始化所有顶点为未访问状态，然后将起始顶点加入栈中。接着进入循环，每次取出栈顶元素作为当前访问的顶点，将其标记为已访问，并输出其值。然后将当前顶点的未访问过的邻居加入栈中，继续循环直到栈为空。