图的定义

图（graph）是由顶点的有穷非空集合和顶点之间的集合组成，通常有三个基本元素：顶点（V）、边（E）。

通俗解释：在人际交往关系图中，一个人是一个顶点，人与人之间的联系方式就相当于一条边。
在理解图定义时需要注意的点：

• 图中的元素称为“顶点”。
• 在图结构中，不允许没有顶点。
• 任意两个顶点之间都可能有关系，顶点之间的逻辑关系可以用边来表示。

图的种类

按照边的种类划分

• 有向图
  以顶点AD之间的关系为例，AD之间的边称为弧，A是弧头，D是弧尾，使用<A,D>表示，不可调换AD之间的顺序。
  

  图1-有向图
  • 有向完全图
    在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称为有向完全图，有个顶点的有向完全图共有条边。
    图2-image.png

• 无向图
  在无向图中，各个顶点不存在方向，可以表示成(A,D)或(D,A)
  

  图3-无向图
  • 无向完全图
    在无向图中，若任意两个顶点之间都存在边，则称为完全无向图。其中，含有个顶点的完全无向图共有 条边。
    图4-完全无向图

网

在图中，如果图的边或弧有各自的数字，则将数字称为权重，具体可以表示一个顶点到另一个顶点的距离（开销）。

图5-网

图顶点与边的关系

• 无向图

  • 邻接点：无向图（图3）边(A,B)可以称为顶点A与顶点B互为邻接点
  • 度：和某一顶点相关联的边的数目，在无向图（图3）中，A的度为3。在无向图中，各个顶点度的和为边数的2倍。即在无向图（图3）中，度的数目为，边的数量为。

• 有向图

  • 度
    • 入度：以顶点v为头的弧的数目
    • 出度：以顶点v为尾的弧的数目
      顶点v的度数为入度+出度，在图1中，A的入度为2，出度为1。

通连图

在无向图中，若某一顶点能够达到其他任意顶点，则称为连通图

在计算机中，图的2种表示法

邻接矩阵

使用两个数组表示图，一个一维数组，用于存储各个节点的信息；一个二维数组用于存储各个顶点之间的关系。

• 表示无向图
  使用邻接矩阵表示无向图，则该矩阵一定是一个对称矩阵。

  • 对角线上的0值表示：不存在顶点到自身的边。
  • 一行（列）中有多少个不为0的点，该顶点就有多少度。
    图6-无向图的邻接矩阵表示法

• 表示有向图

  • 邻接矩阵并不对称
  • 行表示出度，列表示入度。

  其实很好理解，在建立图的过程中，总是先行后列。以[1, 0, 2]，从顶点1指向顶点2

  • 若某一不与其他顶点相连，则表示为。

图7-有向图的邻接矩阵表示法

边节点

//This is python
class Edge(object):
    def __init__(self, prevNode, nextNode, wieght=0):
        self.prevNode = prevNode
        self.nextNode = nextNode
        self.weight = wieght

创建图

思路：以邻接矩阵的方式存储图，本质上就是构建一个长宽均为节点长度的正方形。则对角线置0，其余位置通过两个顶点对位置进行定位。
本例中，顶点信息存储在NodeList <dict类型> 中，每次读入边信息时，在NodeList中检查首、尾顶点是否存在，若不存在，则添加顶点信息；若存在，则将对应边赋予权重。

class adjacencyMatrix(object):
    def __init__(self, nodeNum, edgeNum):
        # 存储邻接矩阵中节点的个数
        self.nodeNum = nodeNum
        # 存储邻接矩阵中节点边的数量
        self.edgeNum = edgeNum
        # 在遍历时检查节点是够被使用过
        self.visited = None
        # 记录每个节点实际对应的名字
        self.nodeNameList = ['v'+str(_) for _ in range(nodeNum)]
        # 记录每个节点下标
        self.NodeList = []
        # 记录每条边的下标，（定位权重用的）
        self.EdgeList = []
        for i in range(nodeNum):
            self.EdgeList.append([NULLFLAG] * edgeNum)

    '''
    使用邻接矩阵创建图的时候，其实就是构造一个长宽均为节点数量的正方形。
    行和列的交汇点代表边的权重
    通过 prev结点和next节点的下标，可以定位连接边的权重值。
    '''
    def createGraph(self, prevIndex, weight, nextIndex):
        if prevIndex not in self.NodeList:
            self.NodeList.append(prevIndex)
            self.EdgeList[prevIndex][prevIndex] = 0
        if nextIndex not in self.NodeList:
            self.NodeList.append(nextIndex)
            self.EdgeList[nextIndex][nextIndex] = 0
        self.EdgeList[prevIndex][nextIndex] = weight
        self.EdgeList[nextIndex][prevIndex] = weight

邻接表

• 在邻接表中，用一个一维数组存储图中所有的顶点，对于数组中的每个元素需要存储指向第一个邻接点的指针，便于查找顶点的边信息。

• 图中每个顶底的所有邻接表构成一个单链表方式存储的线性表。

  
  图8-无向图的邻接表结构

顶点与边节点的定义

//This is python

class EdgeNode(object):
    def __init__(self, index, name, weight=None, nextNode=None):
        self.index = index
        self.name = name
        self.weight = weight
        self.nextNode = nextNode

class VertexNode(object):
    def __init__(self, index, name, firstEdge=None):
        self.index = index
        self.name = name
        self.firstEdge = firstEdge

邻接表的创建

思路：同邻接矩阵类似，需要检测该顶点是否已经存在，存储在NodeList <dict类型> 中。与该顶点相邻的邻接点，采用链表插入中的头插法。

//This is python
class AdjacencyList(object):
    def __init__(self):
        self.vertex = {}
        self.visited = None

    def createGraph(self, startIndex, weight, endIndex):
        if startIndex not in self.vertex.keys():
            vertex_node = VertexNode(startIndex, 'v' + str(startIndex), None)
            self.vertex[startIndex] = vertex_node
        if endIndex not in self.vertex.keys():
            vertex_node = VertexNode(endIndex, 'v' + str(endIndex), None)
            self.vertex[endIndex] = vertex_node

        edgeNode = EdgeNode(endIndex, 'v' + str(endIndex), weight=weight, nextNode=None)
        tmp = self.vertex[startIndex].firstEdge
        edgeNode.nextNode = tmp
        self.vertex[startIndex].firstEdge = edgeNode

---

参考文献

• 《大话数据结构》