这篇文章记录了我学习图找到的一些有用的资料以及edX上Data Structures and Algorithms第五周的笔记.
图(graph)的概念
- G = (V;E) vertex;edge
- 邻接关系: adjacency - 顶点与顶点的关系
- 关联关系: incidence(入射的) - 顶点与相关的某条边的关系
暂时忽略自环的边
无向边(undirected edge): 邻接顶点的次序无所谓
无向图(undigraph):所有边均无方向的图
有向边(directed edge):u和v分别称作尾(tail),头(head)
有向图(digraph):所有边均为有向边
混合图(mixed graph)
关注有向图: 有向图可以表示并且实现无向图以及混合图
路径(path): path(non-simple path),simple path(不含重复节点的路径)
环路(cycle): 起点终点重合; 也有简单/不简单之分, 区别为是否包含重复节点
有向无环图(DAG,directed acyclic graph)
Eulerian tour: 经过所有边恰好一次的环路
Hamiltonian tour: 经过所有顶点恰好一次的环路
图(graph)的代码实现
1.接口
/*Graph template*/
template <typename Tv,typename Te> class Graph{
private:
void reset(){ //所有顶点,边的辅助信息复位
for(int i=0;i<n;i++){ //顶点
status(i) = UNDISCOVERED;
dTime(i) = fTime(i) = -1;
parent(i) = -1;
priority(i)= INT_MAX;
for(int j=0;j<n;j++)
if(exists(i,j)) status(i,j) = UNDETERMINED;
}
}
public: /*...顶点操作,边操作,图算法*/
}//Graph
邻接矩阵(Adjacency matrix)+关联矩阵(Incidence matrix)
1.邻接矩阵(Adjacency matrix)
(1)描述顶点之间相互邻接关系的一种形式
(2)有n个顶点,矩阵是n*n大小的
(3)M(i,j)表示顶点i与顶点j之间是否存在一条边(是否关联),是取1,否取0
(4)无向图
-邻接矩阵对称:M(i,j)=M(j,i)
-对角线元素:自环
(5)无权(non-weighted)图:(binary)bit矩阵
(6)有权(weighted) 图: float/int矩阵
2.关联矩阵(Incidence matrix)
(1)n个节点,e条边
(2)矩阵:n行e列,n*e
(3)M(i,j)表示i节点e边是否存在关联关系
(4)存在关系记为1,不存在记为0
(5)任何一列,恰好只有两个单元的数值为1,其余为0 (意义:一条边连接两个点)
3.顶点(vertex)和边(edge)
/*Vertex*/
typedef enum {UNDISCOVERED,DISCOVERED,VISITED} VStatus;
template <typename Tv> struct Vertex{ //顶点对象
Tv data; //数据
int inDegree,outDegree; //出入度数(和其他顶点相关联)
VStatus status; //(如上三种)状态
int dTime,fTime; //时间标签
int parent; //在遍历树中的父节点
int priority; //在遍历树中的优先级(最短通路,极短跨边等)
Vertex( Tv const & d ): //构造新顶点
data(d),inDegree(0),outDegree(0),status(UNDISCOVERED),//初始状态
dTime(-1),fTime(-1), parent(-1);
priority(INT_MAX){}
};
/*Edge*/
typedef enum {UNDETERMINED,TREE,CROSS,FORWARD,BACKWARD} EStatus;
template <typename Te> struct Edge{ //边对象
Te data; //数据
int weight; //权重
EStatus status; //类型
Edge( Te const & d, int w): //构造新边
data(d),weight(w),status(UNDETERMINED){}
}
4.邻接矩阵(Adjacency matrix)
(1)基于邻接矩阵,实现图结构的一种可行方式
/*GraphMatrix*/
template <typename Tv,typename Te>
class GraphMatrix: public Graph<Tv,Te>{
private:
Vector< Vertex<Tv> > V; //顶点集
Vector< Vector< Edge<Te>* > > E; //边集
public:
/*操作接口:顶点相关，边相关...*/
GraphMatrix(){ n=e=0; } //构造
~GraphMatrix(){ //析构
for (int j=0;j<n;j++)
for (int k=0;k<n;k++)
delete E[j][k]; //清除所有动态申请的边记录
}
}
5.顶点操作
(1)基本操作
/*顶点基本操作*/
Tv & vertex(int i) { return V[i].data; } //数据
int inDegree(int i) { return V[i].inDegree; } //入度(和其他顶点相关联)
int outDegree(int i){ return V[i].outDegree; } //出度
Vstatus & status(int i){ return V[i].status; } //状态
int & dTime(int i){ return V[i].dTime; } //时间标签dTime
int & fTime(int i){ return V[i].fTime; } //时间标签fTime
int & parent(int i){ return V[i].parent; } //在遍历树中的父亲
int & priority(int i){ return V[i].priority; } //优先级数
(2)对于任意顶点i,如何 枚举 其所有的邻接顶点neighbor?
int nextNbr(int i,int j){ //对于顶点i,若已枚举至邻居j,则转向下一邻居
while( (-1<j) && !exists(i,--j) ); //逆向顺序查找,O(n)
return j;
}//改用邻接表可提高至O(1+outDegree(i))
/*确定第一个有效邻居*/
int firstNbr(int i){
return nextNbr(i,n);
}//首个邻居
6.边操作
(1)
/*判断边是否存在*/
bool exists(int i,int j){ //判断边(i,j)是否存在
return (0<=i) && (i<n) && (0<=j) && (j<n)
&& E[i][j]!=NULL; //短路求值
}
/*以下假定exists(i,j)...*/
Te & edge(int i,int j){ //边(i,j)的数据
return E[i][j]->data;
}
Estatus & status(int i,int j){ //边的状态
return E[i][j]->status;
}
int & weight(int i,int j){ //权重
return E[i][j]->weight;
}
(2)边插入
void insert(Te const & edge,int w,int i,int j){//插入(i,j,w)
if(exists(i,j)) return; //忽略已有的边
E[i][j] = new Edge<Te>(edge,w); //创建新边
e++; //更新边计数
V[i].outDegree++; //更新关联顶点i的*出度*
V[j].inDegree++; //更新关联顶点j的*入度*
}
(3)边删除
Te remove(int i,int j){ //删除顶点i和j之间的连边(exist(i,j))
Te eBak = edge(i,j); //backup
delete E[i][j]; //delete
E[i][j] = NULL;
e--;
V[i].outDegree--; //更新关联顶点i的*出度*
V[j].inDegree--; //更新关联顶点j的*入度*
return eBak;
}
(4)顶点动态操作
/*顶点插入*/
//引入新的顶点,改变整体矩阵
//此前表操作中, 矩阵的规模不变
int insert(Tv const & vertex){ //插入顶点,返回编号
for(int j=0;j<n;j++) E[j].insert(NULL);
n++;
E.insert( Vector< Edge<Te>* >(n,n,NULL) );
return V.insert( Vertex<Tv>(vertex) );
}
/*顶点删除*/
Tv remove(int i){ //删除顶点及其相关连边,返回该顶点信息
//删除所有出边
for(int j=0;j<n;j++){
if(exists(i,j)){
delete E[i][j];
V[j].inDegree--;
}
}
//删除第i行边
E.remove(i); n--;
//删除所有入边及第i列
for(int j=0;j<n;j++){
if(exists(j,i)){
delete E[j].remove(i);
V[j].outDegree--;
}
}
//backup and remove
Tv vBak = vertex(i);
V.remove(i);
return vBak;
}
7.邻接矩阵(Adjacency matrix)概括总结
优点
(1)直观,易于理解和实现
(2)适用范围广泛: digraph / network / cyclic / ...
尤其适用于稠密图(dense graph), (我觉得是因为冗余不多)
(3)操作复杂度:
-判断两点之间是否存在连边:O(1)
-获取顶点(出/入)度数:O(1)
-添加,删除边后更新度数:O(1)
(4)扩展性(scalability):
-得益于Vector良好的空间控制策略
-空间溢出等情况可"透明地"予以处理
缺点
(1)空间复杂度O(n^2),与边数无关
(2)考虑平面图(planar graph):可嵌入于平面的图
-平面图的空间利用率~=1/n, 空间利用率低下
广度优先搜索(Breadth First Search)
1.化繁为简,非线性结构转化为线性结构(遍历序列)
2.图->半线性结构树(支撑树)->转化为树的算法问题->线性结构
3.体现为针对某种目标的查找过程:搜索(search)
4.搜索策略
(1)始自顶点s的广度优先算法(Breadth First Search)
(2)访问顶点s
(3)依次访问s所有尚未访问的邻接顶点
(4)依次访问它们尚未访问的邻接顶点
(5)直到没有尚未访问的邻接顶点
(6)结果是一个极大的无环图(一棵树)
(7)这棵树涵盖了原图所有的顶点,所以称为支撑树(spanning tree)
(8)图的广度优先遍历实际上就等同于树的层次遍历
5.实现
/*Graph::BFS()*/
template <typename Tv,typename Te> //顶点类型, 边类型
void Graph<Tv,Te>::BFS( int init_v,int & clock ){
Queue<int> Q; //利用队列,和树的层次遍历(level order)类似
status(init_v) = DISCOVERED;
Q.enqueue(init_v); //入队;
while(!Q.empty()){
int v = Q.dequeue();
dTime(v) = ++clock; //时间标签,给出时间进度,
for(int u = firstNbr(v);-1<u;u=nextNbr(v,u)){
/*视u的状态,分别处理,符合状态的就入队*/
if(status(u)==UNDISCOVERED){
status(u) = DISCOVERED;
Q.enqueue(u);
status(v,u) = TREE; //引入树边(UNDETERMINED->TREE)
parent(u) = v;
} else {
status(v,u) = CROSS; //将(v,u)归类于跨边
}
}//其实不明白status和parent是怎么玩的?
status(v) = VISITED; //至此,当前顶点访问完毕
//每一个顶点的状态都会由最初的undiscovered转化为discovered并最终转化为visited
}
}
6.多连通
(1)图有可能包含多个连通域
template <typename Tv,typename Te>
void Graph<Tv,Te>::bfs(int s){
reset(); int clock=0; int v = s;//初始化
do
if( UNDISCOVERED == status(v) )
BFS(v,clock);
while( s!=(v=(++v%n)) ); //这里不明白......
//按序号访问,不漏不重
}//无论共有多少连通/可达分量
7.复杂度
(1)访问neighbour是O(n^2),因为每个vertex都要走一遍它的neighbour判断是否符合条件(邻接矩阵)
(2)neighbour是紧凑的整体,高速缓冲机制(在后面的B树中会提及),储存级别的巨大速度差异,抵消O(n^2)成O(n)
(3)邻接矩阵改成邻接表(list),可以直接成O(n)
8.最短路径问题(shortest path)
(1)考虑vertex到root的shortest path
(2)考虑树的层次遍历(level order traversal of tree)
(3)最短通路就是图BFS树的vertex到root的通路
一些资料
1.大话数据结构-图
http://www.cnblogs.com/w-wanglei/p/figure.
2.http://blog.chinaunix.net/uid-21813514-id-3866951.html
3.enum枚举(讲解的很好)
http://hi.baidu.com/yuleishou/item/caacae872190031ec216272f