一、图的定义和基本术语

数据结构和算法 七、图_bashendixie5的博客-CSDN博客图（Graph）结构也是一种非线性数据结构，图结构在实际生活中具有丰富的例子。例如，通信网络、交通网络、人际关系网络等都可以归结为图结构。图结构的组织形式要比树结构更为复杂，因此，图结构对存储和遍历等操作具有更高的要求。图是一种善于处理关系型数据的数据结构，使用它可以很轻松地表示数据之间是如何关联的。图论是专门研究图结构的一个理论工具。https://blog.csdn.net/bashendixie5/article/details/123410182

二、图的存储结构

1、邻接矩阵

        邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。

         用邻接矩阵表示法表示图，除了一个用于存储邻接矩阵的二维数组外，还需要用一个一维数组来存储顶点信息。

2、邻接表

        邻接表（Adjacency List）是图的一种链式存储结构。在邻接表中，对图中每个顶点vi建立一个单链表，把与vi相邻接的顶点放在这个链表中。邻接表中每个单链表的第一个结点存放有关顶点的信息，把这一结点看成链表的表头，其余结点存放有关边的信息，这样邻接表便由两部分组成：表头结点表和边表。

3、十字链表

        十字链表（Orthogonal List）是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也有一个结点。

4、邻接多重表

        邻接多重表的结构和十字链表类似。在邻接多重表中，每一条边用一个结点表示，它由如下图所示的6个域组成。其中，mark为标志域，可用以标记该条边是否被搜索过；ivex和jvex为该边依附的两个顶点在图中的位置；ilink指向下一条依附于顶点ivex的边；jlink指向下一条依附于顶点jvex的边，info为指向和边相关的各种信息的指针域。

三、图的遍历

1、理解最短路径

        路径是介于起点和终点之间的所有节点构成的序列，同一个节点不会在同一条路径上出现两次。也就是说，路径表示起点和终点之间的路线，它是连接起点和终点的顶点集p，在p中没有重复的顶点。

        路径的长度是通过对组成路径的边进行计数完成计算的，在所有的路径中，长度最短的路径称为最短路径。最短路径的计算在图论算法中广泛使用，但并不总是直接计算。有多种算法可以用来寻找起始节点和结束节点之间的最短路径，其中一个最流行的算法是狄克斯特拉（Dijkstra）算法。

        狄克斯特拉算法用于每条边都有关联数字的图，这些数字称为权重（weight）。

        狄克斯特拉算法包含4个步骤

        (1) 找出最便宜的节点，即可在最短时间内前往的节点。

        (2) 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。

        (3) 重复这个过程，直到对图中的每个节点都这样做了。

        (4) 计算最终路径。

        以下面的图为例

        python代码示例

# 构建这个十分简单的图
graph = {}
graph["start"] = {}
graph["start"]["a"] = 6
graph["start"]["b"] = 2

graph["a"] = {}
graph["a"]["fin"] = 1

graph["b"] = {}
graph["b"]["a"] = 3
graph["b"]["fin"] = 5

graph["fin"] = {}

# 构建花费表
infinity = float("inf")
costs = {}
costs["a"] = 6
costs["b"] = 2
costs["fin"] = infinity

# 构建parent表
parents = {}
parents["a"] = "start"
parents["b"] = "start"
parents["fin"] = None

processed = []

def find_lowest_cost_node(costs):
    lowest_cost = float("inf")
    lowest_cost_node = None
    # 循环每一个节点
    for node in costs:
        cost = costs[node]
        # 如果是目前为止成本最低的，还没有处理...
        if cost < lowest_cost and node not in processed:
            # 将其设置为新的最低成本节点。
            lowest_cost = cost
            lowest_cost_node = node
    return lowest_cost_node

# 找到您尚未处理的成本最低的节点。
node = find_lowest_cost_node(costs)
# 如果您已经处理了所有节点，那么这个 while 循环结束
while node is not None:
    cost = costs[node]
    # Go through all the neighbors of this node.
    neighbors = graph[node]
    for n in neighbors.keys():
        new_cost = cost + neighbors[n]
        # 如果通过这个节点到达这个邻居更便宜
        if costs[n] > new_cost:
            # 更新此节点的成本。
            costs[n] = new_cost
            # 该节点成为该邻居的新父节点。
            parents[n] = node
    # 标记节点已经被处理了
    processed.append(node)
    # 寻找下一个没处理的节点
    node = find_lowest_cost_node(costs)

print("Cost from the start to each node:")
print(costs)

2、深度优先搜索(DFS)

        深度优先查找（Depth-First Search，DFS）算法也称为深度优先搜索算法，有点类似于前序遍历法，因为查找的过程也是遍历的过程，所以也习惯叫深度优先遍历。从图的某一顶点开始遍历，被访问过的顶点就做上已访问的记号，接着遍历此顶点的所有相邻且未访问过的顶点中的任意一个顶点，并做上已访问的记号，再以该点为新的起点继续进行深度优先搜索。

        深度优先查找算法（或深度优先遍历）是使用堆栈和递归的技巧来遍历图的。

        遍历过程如下示例：

        Visited：包含所有已访问的节点。Queue：包含尚未访问的节点。

        python代码示例

# 使用字典定义图
graph={   'Amin'  : {'Wasim', 'Nick', 'Mike'},
         'Wasim' : {'Imran', 'Amin'}, 
         'Imran' : {'Wasim','Faras'}, 
         'Faras' : {'Imran'},
         'Mike':{'Amin'}, 
         'Nick':{'Amin'}}

# 定义深度优先搜索函数
def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    return visited

# 从Amin开始搜索
dfs(graph,'Amin')

3、广度优先搜索(BFS)

        广度优先查找（Breadth-First Search，BFS）算法则是使用队列和递归的技巧来查找的。当我们所处理的图aGraph存在层次的概念时，BFS的效果最好。

        广度优先查找算法（或广度优先遍历）是从图的某一顶点开始遍历，被访问过的顶点就做上已访问的记号，接着遍历此顶点的所有相邻且未访问过的顶点中的任意一个顶点，并做上已访问的记号，再以该点为新的起点继续进行广度优先遍历。

        BFS假设在给定图中遍历每条边的代价相同，而在Dijkstra算法中，遍历图中各条边的代价则可以是不同的，这就需要将代价纳入算法设计中，进而将BFS修改为Dijkstra算法。

        遍历过程如下示例：

        Visited：包含所有已访问的节点。Queue：包含尚未访问的节点。

        python代码示例

# 定义图
graph={   'Amin'  : {'Wasim', 'Nick', 'Mike'},
         'Wasim' : {'Imran', 'Amin'}, 
         'Imran' : {'Wasim','Faras'}, 
         'Faras' : {'Imran'},
         'Mike':{'Amin'}, 
         'Nick':{'Amin'}}

# 定义广度优先搜索
def bfs(graph, start):
    visited = []
    queue = [start]
 
    while queue:
        node = queue.pop(0)
        if node not in visited:
            visited.append(node)
            neighbours = graph[node]
            for neighbour in neighbours:
                queue.append(neighbour)
    return visited

# 从Amin开始搜索
bfs(graph,'Amin')