1.連通分支
連通分支（Connected Component）是指：在一個圖中，某個子圖的任意兩點有邊連接配接，并且該子圖去剩下的任何點都沒有邊相連。在 Wikipedia上的定義如下：
In graph theory, a connected component (or just component) of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph.
如Wikipedia上給的例子：
根據定義不難看出該圖有三個連通分支。
另外，連通分支又分為弱連通分支和強連通分支。強連通分支是指子圖點i可以連接配接到點j，同時點j也可以連接配接到點i。弱連通（隻對有向圖）分支是指子圖點i可以連接配接到點j，但是點j可以連接配接不到點i。
2.傳統算法
2.1算法思想
在傳統算法中，我們是根據一點任意點，去找它的鄰結點，然後再根據鄰結點，找它的鄰結點，直到所有的點周遊完。如下圖：
圖中有A、B、C、D和E五個點。我們先任選一個點C，然後找到C的鄰結點E。然後我們再找E的鄰結點，發現隻有C，但是我們之前周遊過C，是以排除C。現在我們沒有點可以周遊了，于是找到了第一個連通分支，如下藍色标記：
接着，我們再從沒有周遊的點（A、B、C）中任選一個點A。按照上述的方法，找到A的鄰結點B。然後在找B的鄰結點，找到A和D，但是A我們之前周遊過，是以排除A，隻剩下了D。再找D的鄰結點，找到B，同樣B之前也周遊過了，是以也排除B，最後發現也沒有點可以通路了。于是，就找到了第二個連通分支。到此圖中所有的點已經周遊完了，是以該圖有兩個連通分支（A、B、D）和（C、E）。如下圖：
2.2算法實作
下面是用Python實作的代碼：
class Data(object):
def __init__(self, name):
self.__name = name
self.__links = set()
@property
def name(self):
return self.__name
@property
def links(self):
return set(self.__links)
def add_link(self, other):
self.__links.add(other)
other.__links.add(self)
# The function to look for connected components.
def connected_components(nodes):
# List of connected components found. The order is random.
result = []
# Make a copy of the set, so we can modify it.
nodes = set(nodes)
# Iterate while we still have nodes to process.
while nodes:
# Get a random node and remove it from the global set.
n = nodes.pop()
print(n)
# This set will contain the next group of nodes connected to each other.
group = {n}
# Build a queue with this node in it.
queue = [n]
# Iterate the queue.
# When it's empty, we finished visiting a group of connected nodes.
while queue:
# Consume the next item from the queue.
n = queue.pop(0)
# Fetch the neighbors.
neighbors = n.links
# Remove the neighbors we already visited.
neighbors.difference_update(group)
# Remove the remaining nodes from the global set.
nodes.difference_update(neighbors)
# Add them to the group of connected nodes.
group.update(neighbors)
# Add them to the queue, so we visit them in the next iterations.
queue.extend(neighbors)
# Add the group to the list of groups.
result.append(group)
# Return the list of groups.
return result
# The test code...
if __name__ == "__main__":
# The first group, let's make a tree.
a = Data("a")
b = Data("b")
c = Data("c")
d = Data("d")
e = Data("e")
f = Data("f")
a.add_link(b) # a
a.add_link(c) # / \
b.add_link(d) # b c
c.add_link(e) # / / \
c.add_link(f) # d e f
# The second group, let's leave a single, isolated node.
g = Data("g")
# The third group, let's make a cycle.
h = Data("h")
i = Data("i")
j = Data("j")
k = Data("k")
h.add_link(i) # h————i
i.add_link(j) # | |
j.add_link(k) # | |
k.add_link(h) # k————j
# Put all the nodes together in one big set.
nodes = {a, b, c, d, e, f, g, h, i, j, k}
# Find all the connected components.
number = 1
for components in connected_components(nodes):
names = sorted(node.name for node in components)
names = ", ".join(names)
print("Group #%i: %s" % (number, names))
number += 1
# You should now see the following output:
# Group #1: a, b, c, d, e, f
# Group #2: g
# Group #3: h, i, j, k
3.基于矩陣的實作算法
3.1理論基礎
1.鄰接矩陣
鄰接矩陣表示頂點之間相鄰關系的矩陣，同時鄰接矩陣分為有向鄰接矩陣和無向鄰接矩陣，如：
2.回路計算
假設有鄰接矩陣
，則回路計算公式為：
其中，
表示從點i到點j經過k條路徑形成的通路總數。當然，如果
表示從點i到點j沒有通路（有向圖）或回路路（無向圖）。
3.2算法推導
如果把經過0、1、2、3••••••條路徑形成的回路矩陣求并集（注：經過0條路徑形成的回路矩陣即為機關矩陣I），那麼該并集C可以表示所有回路的總和，用公式可以表示為：
是以，
的（i，j）有非0值，表示點i和點j是同一個強連通的集合。
由于
比較複雜，但是，我們可以用下式計算：
C等于0的位置，D對應的位置也等于0；C等于1的位置，D對應的位置大于0。此時可以用D代替C進行計算。
對于D，這個式子幾乎不收斂，因為我們需要修改它。現在讓我們考慮式子
，證明如下：
是以，
但是，現在還有一個問題，D并不總是收斂。是以，需要引入一個系數
，使得用
代替A，則D重新定義為：
同理，由
（證明同上），
可以求得：
其中，矩陣D中非0值所在列相同的行，屬于同一個連通分支，即行結構相同的是一個連通分支。
3.3算法實作
下面是用Python實作的代碼：
from numpy.random import rand
import numpy as np
#利用求并集和交集的方法
def cccomplex(adjacencyMat):
def power(adjacencyMatPower, adjacencyMat):
adjacencyMatPower *= adjacencyMat
return adjacencyMatPower
dimension = np.shape(adjacencyMat)[0]
eye = np.mat(np.eye(dimension))
adjacencyMat = np.mat(adjacencyMat)
adjacencyMatPower = adjacencyMat.copy()
result = np.logical_or(eye, adjacencyMat)
for i in range(dimension):
adjacencyMatPower = power(adjacencyMatPower, adjacencyMat)
result = np.logical_or(result, adjacencyMatPower)
final = np.logical_and(result, result.T)
return final
#利用求矩陣逆的方法
def connectedConponents(adjacencyMat, alpha = 0.5):
n = np.shape(adjacencyMat)[0]
E = np.eye(n)
ccmatrix = np.mat(E - alpha * adjacencyMat)
return ccmatrix.I
def init(dimension):
mat = np.ones((dimension, dimension))
mat[(rand(dimension) * dimension).astype(int), (rand(dimension) * dimension).astype(int)] = 0
return mat
if __name__ == "__main__":
dimension = 4
adjacencyMat = init(dimension)
adjacencyMat1 = np.array([[0,1,0,0,0,0,0,0], [0,0,1,0,1,1,0,0],
[0,0,0,1,0,0,1,0],
[0,0,1,0,0,0,0,1],
[1,0,0,0,0,1,0,0],
[0,0,0,0,0,0,1,0],
[0,0,0,0,0,1,0,1],
[0,0,0,0,0,0,0,1]])
adjacencyMat2 = np.array([[0,1,1,0],[1,0,0,0],[1,0,0,0],[0,0,0,0]])
print(cccomplex(adjacencyMat1)) #(A, B, E) (C, D) (F, G) (H)
print(connectedConponents(adjacencyMat2))
#[[ True True False False True False False False]
# [ True True False False True False False False]
# [False False True True False False False False]
# [False False True True False False False False]
# [ True True False False True False False False]
# [False False False False False True True False]
# [False False False False False True True False]
# [False False False False False False False True]]
#[[ 2. 1. 1. 0. ]
# [ 1. 1.5 0.5 0. ]
# [ 1. 0.5 1.5 0. ]
# [ 0. 0. 0. 1. ]]
4.評價
基于矩陣運算實作的圖算法，有以下幾點優勢：
- 易于實作。利用矩陣可以僅僅通過矩陣與矩陣或矩陣與向量的運算就可以實作一些圖算法。
- 易于并行。在超大矩陣運算中，可以采用分塊的方式平行處理矩陣運算。同理，也可以很容易的移植分布式上（可以參考我的博文基于Spark實作的超大矩陣運算）。
- 效率更高。基于矩陣的圖形算法更清晰突出的資料通路模式，可以很容易地優化（實驗測試工作已完成）。
- 易于了解。這個需要對離散數學或者圖論有一定基礎，知道每一步矩陣運算所對應的實體意義或數學意義。