菜单
×
   ❮   
HTML CSS JAVASCRIPT SQL PYTHON JAVA PHP HOW TO W3.CSS C C++ C# BOOTSTRAP REACT MYSQL JQUERY EXCEL XML DJANGO NUMPY PANDAS NODEJS R TYPESCRIPT ANGULAR GIT POSTGRESQL MONGODB ASP AI GO KOTLIN SASS VUE DSA GEN AI SCIPY AWS CYBERSECURITY DATA SCIENCE
     ❯   

DSA 图的实现


一个基本的图实现

在我们可以对图运行算法之前,我们必须先以某种方式实现它。

为了实现图,我们将使用一个 邻接矩阵,如下面的示例所示。

A B C D A B C D A B C D 1 1 1 1 1 1 1 1
一个无向图
及其邻接矩阵

为了存储每个顶点的数据,在本例中是字母 A、B、C 和 D,数据被放入一个单独的数组中,该数组与邻接矩阵中的索引匹配,如下所示

vertexData = [ 'A', 'B', 'C', 'D']

对于无向且非加权的图,如上图所示,顶点 ij 之间的边存储的值为 1。它存储在 (j,i)(i,j) 的两个位置,因为边是双向的。如你所见,对于这种无向图,矩阵变成对角对称的。

让我们看一些更具体的内容。在上图的邻接矩阵中,顶点 A 位于索引 0,顶点 D 位于索引 3,因此我们在位置 (0,3)(3,0) 中得到顶点 A 和 D 之间的边,存储为值 1,因为边是双向的。

下面是上面图片中无向图的一个基本实现。

示例

Python

vertexData = ['A', 'B', 'C', 'D']

adjacency_matrix = [
    [0, 1, 1, 1],  # Edges for A
    [1, 0, 1, 0],  # Edges for B
    [1, 1, 0, 0],  # Edges for C
    [1, 0, 0, 0]   # Edges for D
]

def print_adjacency_matrix(matrix):
    print("\nAdjacency Matrix:")
    for row in matrix:
        print(row)

print('vertexData:',vertexData)
print_adjacency_matrix(adjacency_matrix)
运行示例 »

这个实现基本上只是一个二维数组,但为了更好地了解图中顶点如何通过边连接,我们可以运行这个函数

示例

Python

def print_connections(matrix, vertices):
    print("\nConnections for each vertex:")
    for i in range(len(vertices)):
        print(f"{vertices[i]}: ", end="")
        for j in range(len(vertices)):
            if matrix[i][j]:  # if there is a connection
                print(vertices[j], end=" ")
        print()  # new line
运行示例 »

使用类实现图

存储图的更合适的方法是添加一个使用类的抽象层,这样图的顶点、边以及相关方法(如我们稍后将实现的算法)都可以集中在一个地方。

像 Python 和 Java 这样具有内置面向对象功能的编程语言,比 C 这样没有内置功能的语言更容易实现基于类的图。

A B C D A B C D A B C D 1 1 1 1 1 1 1 1
一个无向图
及其邻接矩阵

下面是上面无向图如何使用类实现的示例。

示例

Python

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[0] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size  

    def add_edge(self, u, v):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = 1
            self.adj_matrix[v][u] = 1

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def print_graph(self):
        print("Adjacency Matrix:")
        for row in self.adj_matrix:
            print(' '.join(map(str, row)))
        print("\nVertex Data:")
        for vertex, data in enumerate(self.vertex_data):
            print(f"Vertex {vertex}: {data}")

g = Graph(4)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_edge(0, 1)  # A - B
g.add_edge(0, 2)  # A - C
g.add_edge(0, 3)  # A - D
g.add_edge(1, 2)  # B - C

g.print_graph()
运行示例 »

在上面的代码中,我们为无向图获得的矩阵对称性在第 9 和 10 行中处理,这为我们在第 29-32 行初始化图中的边节省了一些代码。


有向图和加权图的实现

要实现一个有向且加权的图,我们只需要对前面无向图的实现做一些修改。

要创建有向图,我们只需删除前面示例代码中的第 10 行,这样矩阵就不再自动对称了。

我们需要做的第二个更改是向 add_edge() 方法添加一个 weight 参数,这样,我们就不再仅仅使用值 1 来表示两个顶点之间存在边,而是使用实际的权重值来定义边。

A B 1 3 C 4 2 D A B C D A B C D 3 2 1 4
一个有向且加权的图,
及其邻接矩阵。

下面是上面有向加权图的实现。

示例

Python

class Graph:
    def __init__(self, size):
        self.adj_matrix = [[None] * size for _ in range(size)]
        self.size = size
        self.vertex_data = [''] * size  

    def add_edge(self, u, v, weight):
        if 0 <= u < self.size and 0 <= v < self.size:
            self.adj_matrix[u][v] = weight
            self.adj_matrix[v][u] = weight

    def add_vertex_data(self, vertex, data):
        if 0 <= vertex < self.size:
            self.vertex_data[vertex] = data

    def print_graph(self):
        print("Adjacency Matrix:")
        for row in self.adj_matrix:
            print(' '.join(map(lambda x: str(x) if x is not None else '0', row)))
        print("\nVertex Data:")
        for vertex, data in enumerate(self.vertex_data):
            print(f"Vertex {vertex}: {data}")

g = Graph(4)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_edge(0, 1, 3)  # A -> B with weight 3
g.add_edge(0, 2, 2)  # A -> C with weight 2
g.add_edge(3, 0, 4)  # D -> A with weight 4
g.add_edge(2, 1, 1)  # C -> B with weight 1

g.print_graph()
运行示例 »

第 3 行:所有边最初都设置为 None

第 7 行:现在可以通过附加的 weight 参数将权重添加到边。

第 10 行:通过删除第 10 行,图现在可以设置为有向的。

在下一页,我们将学习如何遍历图,在接下来的几页中,我们将了解可以在图数据结构上运行的不同算法。


DSA 练习

通过练习来测试自己

练习

图中的边是如何实现的?

The edges, and edge weights, 
in a graph are normally 
implemented in an  matrix.

开始练习



×

联系销售

如果您想将 W3Schools 服务用于教育机构、团队或企业,请发送电子邮件给我们
sales@w3schools.com

报告错误

如果您想报告错误,或想提出建议,请发送电子邮件给我们
help@w3schools.com

W3Schools 经过优化,旨在方便学习和培训。示例可能经过简化,以提高阅读和学习体验。教程、参考资料和示例会不断审查,以避免错误,但我们无法保证所有内容的完全正确性。使用 W3Schools 即表示您已阅读并接受我们的使用条款Cookie 和隐私政策

版权所有 1999-2024 Refsnes Data。保留所有权利。W3Schools 由 W3.CSS 提供支持