Reference: www.bilibili.com/video/BV1E4…

Python implementation

Class Graph: def __init__(self, num): "" vertexList: store the vertexList: store the matrix of the Graph's vertices numOfEdges: Number of edges isVisited: whether the vertices are accessed num: Self. VertexList = [] self. Edges = [] for I in range(num): self.edges.append([0 for x in range(num)]) self.numOfEdges = 0 self.isVisited = [False for x in range(num)] self.limit =  num def showGraph(self): for line in self.edges: print(line) def getNumOfEdges(self): Def getWeight(self, x, y) def getWeight(self, x, y): Edges [x][y] def insertVertex(self, vertex): if len(self. VertexList) <= self. Self.vertexlist. Append (vertex) else: print("vertexList ") def insertEdges(self, x, y, weight): self.edges[x][y] = weight self.edges[y][x] = weight self.numOfEdges += 1 def getValueByIndex(self, index): return self.vertexList[index] def getFirstVertex(self, index): for j in range(0, len(self.edges)): if self.edges[index][j] > 0: return j return -1 def getNextVertex(self, x, y): for j in range(y + 1, len(self.vertexList)): if self.edges[x][j] > 0: return j return -1 def _dfs(self, index): print(self.getValueByIndex(index), end="->") self.isVisited[index] = True n = self.getFirstVertex(index) while n ! = -1: if not self.isVisited[n]: self._dfs(n) n = self.getNextVertex(index, n) def dfs(self): for i in range(len(self.vertexList)): if not self.isVisited[i]: self._dfs(i) def _bfs(self, index): queue = [] print(self.getValueByIndex(index), end="->") queue.append(index) self.isVisited[index] = True while len(queue) ! = 0: u = queue.pop(0) w = self.getFirstVertex(u) while w ! = -1: if not self.isVisited[w]: print(self.getValueByIndex(w), end="->") self.isVisited[w] = True queue.append(w) w = self.getNextVertex(u, w) def bfs(self): for i in range(len(self.vertexList)): if not self.isVisited[i]: self._bfs(i) graph = Graph(5) vertexList = ["A", "B", "C", "D", "E"] for vertex in vertexList: graph.insertVertex(vertex) print(graph.vertexList) graph.insertEdges(0, 1, 1) graph.insertEdges(0, 2, 1) graph.insertEdges(1, 2, 1) graph.insertEdges(1, 3, 1) graph.insertEdges(1, 4, 1) for line in graph.edges: print(line) # graph.dfs() graph.bfs()Copy the code