图算法基础知识.ppt

文档介绍：图算法基础知识
第一页，课件共29页
图
图 G = (V, E)
V = 顶点的非空有限集
E = 边集 = V  V的子集，V中顶点对，边的有限集。
|E| = O(|V|2)
简单图(Sample Graph)
任意两个顶点最多只有一条边，且每个点都没有连接到自身的边。
完全图(Complete Grapth)
若有n个顶点的无向图n(n-1)/2条边，则此图为完全图。
第二页，课件共29页
图的扩展
扩展:
连通图（ connected graph） 从图中每一顶点都有到其它顶点的路径 。
无向图（ undirected graph）:
边(u,v) = 边 (v,u)
有向图 （directed graph）:
(u,v) 表示从顶点u 到顶点 v的一条有向边, 记为 uv
一个不含有环的有向图称为无环有向图(Directed acyclic graphs ,DAG）。
加权图（ weighted graph） 图中不是边就是顶点与权关联，例如：公路交通图，边以距离w为权。
第三页，课件共29页
图
通常用边数 |E|和顶点数|V|描述运行时间。
无向图中 0≤|E|≤|V|(|V|-1)/2
有向图中 0≤|E|≤|V|(|V|-1)
若|E|  |V|2 ，图是稠密的 dense
若 |E|  |V| ，图是稀疏的 sparse
对稠密图和稀疏图使用不同的数据结构
第四页，课件共29页
图的表示
假设 V = {1, 2, …, n}
邻接矩阵（adjacency matrix）
将图表示成一个 n x n 矩阵 A:
A[i, j] = 1 若边 (i, j)  E (或边的权wij) = 0 若边 (i, j)  E
第五页，课件共29页
图: 邻接矩阵
Example:
1
2
4
3
A
1
2
3
4
1
0
1
1
0
2
0
0
1
0
3
0
0
0
0
4
0
0
1
0
有向图 非对称矩阵
第六页，课件共29页
图: 邻接矩阵
Example:
1
2
4
3
a
d
b
c
A
1
2
3
4
1
2
3
??
4
第七页，课件共29页
图: 邻接矩阵
Example:
1
2
4
3
a
d
b
c
A
1
2
3
4
1
0
a
d
0
2
0
0
b
0
3
0
0
0
0
4
0
0
c
0
第八页，课件共29页
图: 邻接矩阵
Example:
1
2
4
3
5
1
4
3
A
1
2
3
4
1
0
3
5
0
2
0
0
1
0
3
0
0
0
0
4
0
0
4
0
第九页，课件共29页
图: 邻接矩阵
Example:
1
2
4
3
a
d
b
c
A
1
2
3
4
1
0
a
d
0
2
a
0
b
0
3
d
b
0
c
4
0
0
c
0
无向图 对称矩阵
第十页，课件共29页