social graph
本文我们将探讨非线性的数据结构:图。
- 图的概念和术语
- 图的表示
- 广度优先搜索
图在计算机领域有着相当广泛的应用。假如你想去一个陌生的地方，通过GPS导航软件可以辅助你找到最短路径，最省时路径等。另外,有一个非常知名的理论叫做六度空间理论，讲的是世界上任何一个人与另一个人的联系，通过六层关系就可以全部实现，该理论就是基于图的概念所提出的。
概念和术语
什么是图?
图是一种（包含若干个节点），每个节点可以连接 0 个或多个元素
两个节点相连的部分称为边（edge）。节点也被称作顶（vertice）。
一个顶点的度（degree）是指与该顶点相连的边的条数。比如上图中，紫色顶点的度是 3，蓝色顶点的度是 1。
如果所有的边都是双向的，那我们就有了一个无向图（undirected graph）。反之如果边是有向的，我们得到的就是有向图（directed graph）。你可以将有向图和无向图想象为单行道或双行道组成的交通网。
顶点的边可以是从自己出发再连接回自己（如蓝色的顶点），拥有这样的边的图被称为自环。
当图的每条边都被分配了权重时，我们就有了一个加权图（weighted graph）。如果边的权重被忽略，那么可以将（每条边的）权重都视为 1。
图的表示
图的表示有两种方式：
- 邻接表
- 邻接矩阵
邻接表
邻接表是最常用的图表示方法。每个顶点都有一个记录着与它所相邻顶点的表。
使用一个数组来建立一个邻接表，它存储这所有的顶点。每个顶点都有一个列表，存放着与其相邻的顶点。
邻接矩阵
邻接矩阵使用二维数组（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)
