基于python的Graph图的表示_python graph

图（Graph）的表示

1.图的概念

图是一种重要的数据结构，在解决实际问题中也经常用到这种数据结构，其基本表示为G=(V, E)，V(vectex)是图的顶点，E(edge)表示图的边。我们的地图在计算机中就可以表示成一个Graph，不同的标志性地点为vectex，地点之间的路表示为edge，这样就可以方便操作实际中的地图去解决一些复杂的问题，比如找两个地点之间的最短路径，旅行商问题等等。

图分为有向图和无向图，有向图指的是各个顶点之间有一定的方向，一个顶点到另一个顶点需要按照给定的方向进行移动；而无向图指的是顶点之间没有固定方向。如下图所示，第一幅图为无向图，第二幅图为有向图。在有向图中，顶点1指向顶点2，说明1可以移向2，但是2不能移向1。

2.图的表示

图的表示就是表示清楚顶点信息和边的信息。有两种表示方法，邻接链表和邻接矩阵。如上面两张图可分别表示如下：

在计算机中，我们可以使用一些数据结构来简化图的表达，比如在Python中，我们可以用下面代码来表示一个图：

graph = {
   'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}
1
2
3
4
5
6
7

graph是一个字典，其中keys是所有的vertices，values是与该顶点连接的其他顶点。如果我们需要获取所有的顶点，那么可以利用字典的keys()方法：

graph.keys()

output: dict_keys(['A', 'B', 'C', 'D', 'E', 'F'])
1
2
3

获取与某个顶点相连的其他顶点，就可直接利用字典的取值方法：

graph['A']

output: {
   'B', 'C'}
1
2
3
4

但是如果图中的每一个边有权，我们称之为有权图时，利用上述的表示方法不能很方便地得到权重信息，为此我们可以封装一个类，定义获取边，权重等相关信息的函数。

# Fall 2012 6.034 Lab 2: Search
from functools import reduce

try:
    set()
except NameError:
    from sets import Set as set, ImmutableSet as frozenset

NAME="NAME"
NODE1="NODE1"
NODE2="NODE2"
VAL="LENGTH"

class Edge:
    def __init__(self, name, node1, node2, length):
        self.name = name
        self.node1 = node1
        self.node2 = node2
        self.length = length
    def 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19