数据结构之图

social graph

本文我们将探讨非线性的数据结构:图。

1. 图的概念和术语
2. 图的表示
3. 广度优先搜索

图在计算机领域有着相当广泛的应用。假如你想去一个陌生的地方，通过GPS导航软件可以辅助你找到最短路径，最省时路径等。另外,有一个非常知名的理论叫做六度空间理论，讲的是世界上任何一个人与另一个人的联系，通过六层关系就可以全部实现，该理论就是基于图的概念所提出的。

概念和术语

---

什么是图?
图是一种（包含若干个节点），每个节点可以连接 0 个或多个元素
两个节点相连的部分称为边（edge）。节点也被称作顶（vertice）。

一个顶点的度（degree）是指与该顶点相连的边的条数。比如上图中，紫色顶点的度是 3，蓝色顶点的度是 1。

如果所有的边都是双向的，那我们就有了一个无向图（undirected graph）。反之如果边是有向的，我们得到的就是有向图（directed graph）。你可以将有向图和无向图想象为单行道或双行道组成的交通网。

顶点的边可以是从自己出发再连接回自己（如蓝色的顶点），拥有这样的边的图被称为自环。

当图的每条边都被分配了权重时，我们就有了一个加权图（weighted graph）。如果边的权重被忽略，那么可以将（每条边的）权重都视为 1。

图的表示

---

图的表示有两种方式：

1. 邻接表
2. 邻接矩阵

邻接表

邻接表是最常用的图表示方法。每个顶点都有一个记录着与它所相邻顶点的表。
使用一个数组来建立一个邻接表，它存储这所有的顶点。每个顶点都有一个列表，存放着与其相邻的顶点。

邻接矩阵

邻接矩阵使用二维数组（N x N）来表示图。如若不同顶点存在连接的边，就赋值两顶点交汇处为1（也可以是这条边的权重），反之赋值为 0 或者 -。

广度优先搜索

---

广度优先搜索是一种从最初的顶点开始，优先访问所有相邻顶点的搜索算法。
非常类似于树遍历的层次遍历法。

一起看看如何用代码来实现:

# Python3 Program to print BFS traversal
# from a given source vertex. BFS(int s)
# traverses vertices reachable from s.
from collections import defaultdict
 
# This class represents a directed graph
# using adjacency list representation
class Graph:
 
    # Constructor
    def __init__(self):
 
        # default dictionary to store graph
        self.graph = defaultdict(list)
 
    # function to add an edge to graph
    def addEdge(self,u,v):
        self.graph[u].append(v)
 
    # Function to print a BFS of graph
    def BFS(self, s):
 
        # Mark all the vertices as not visited
        visited = [False] * (len(self.graph))
 
        # Create a queue for BFS
        queue = []
 
        # Mark the source node as 
        # visited and enqueue it
        queue.append(s)
        visited[s] = True
 
        while queue:
 
            # Dequeue a vertex from 
            # queue and print it
            s = queue.pop(0)
            print (s, end = " ")
 
            # Get all adjacent vertices of the
            # dequeued vertex s. If a adjacent
            # has not been visited, then mark it
            # visited and enqueue it
            for i in self.graph[s]:
                if visited[i] == False:
                    queue.append(i)
                    visited[i] = True
 
# Driver code
 
# Create a graph given in
# the above diagram
g = Graph()
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 2)
g.addEdge(2, 0)
g.addEdge(2, 3)
g.addEdge(3, 3)
 
print ("Following is Breadth First Traversal"
                  " (starting from vertex 2)")
g.BFS(2)