图的定义：图G由顶点集V和边集E组成，记为G=（V，E），其中V（G）表示图G中顶点的有限非空集；E（G）表示图G中顶点之间的关系集合。
若图G中任意两个顶点是连通的，则称图G为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量。假设一个图有n个顶点，如果边数小于n-1，那么此图必是非连通图。
在有向图中，如果有一对顶点v和w，从v到w和从w到v之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。n个顶点的强连通图至少需要n条边。
连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n-1条边。

图的存储及基本操作

邻接矩阵
邻接表法
十字链表：弧结点中有五个域：tailvex和headvex两个域分别指示弧尾和弧头这两个顶点的编号；hlink域指向弧头相同的下一个弧结点；tlink域指向弧尾相同的下一个弧结点；info域存放该弧的相关信息。
邻接多重表

基本操作

Adjacent（G，x，y）：判断图G是否存在边<x，y>
Neighbors（G，x）：列出图G中与结点x邻接的边
InsertVertex（G，x）：在图G中插入顶点x
DeleteVertex（G，x）：从图G中删除顶点x
AddEdge（G，x，y）：若无向边（x，y）或有向边<x，y>不存在，则向图G中添加该边。
RemoveEdge（G，x，y）：若无向边（x，y）或有向边<x，y>存在，则向图G中删除该边
FirstNeighbor（G，x）：求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1
NextNeighbor（G，x，y）：假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1.
Get_edge_value（G，x，y）：获取图G中边（x，y）或<x，y>对应的权值
Set_edge_value（G，x，y，v）：设置图G中边（x，y）或<x，y>对应的权值为v

图的遍历

广度优先算法

bool visited[MAX_VERTEX_NUM];                  //访问标记数组
void BFSTraverse(Graph G){                     //对图G进行广度优先遍历
	for(i=0;i<G.vexnum;++i) visited[i]=FALSE;  //访问标记数组初始化
	InitQueue(Q);                              //初始化辅助队列Q
	for(i=0;i<G.vexnum;++i){                   //从0号顶点开始遍历
		if(!visited[i]) BFS(G,i);              //对每个连通分量调用BFS
	}
}
void BFS(Graph G,int v){                       //从顶点v出发广度优先遍历
	visit(v);                                  //访问初始顶点v
	visited[v]=TRUE;                           //对v做已访问标记
	Enqueue(Q,v);                              //顶点v入列Q
	while(!isEmpty(Q)){
		DeQueue(Q,v);                          //顶点v出队列
		for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){  
		                                      //检测v所有邻接点
			if(!visited[w]){                   //w为v的尚未访问邻接顶点
				visit(w);                      //访问顶点w
				visited[w]=TRUE;               //对w做已访问标记
				EnQueue(Q,w);                  //顶点w入队列
			}
		}
	}
}

算法时间复杂度为O（）
使用BFS可以求解非带权图的单源最短路径问题

深度优先算法

bool visited[MAX_VERTEX_NUM];                  //访问标记数组
void DFSTraverse(Graph G){                     //对图G进行深度优先遍历
	for(v=0;v<G.vexnum;++v) visited[v]=FALSE;  //初始化已访问标记数组
	for(v=0;v<G.vexnum;++v){
		if(!visited[v]) DFS(G,v);
	}
}
void DFS(Graph G,int v){                       //从顶点v出发深度优先遍历
	visit(v);                                  //访问顶点v
	visited[v]=TRUE;                           //对v做已访问标记
	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
		if(!visited[w]) DFS(G,w);              //递归
	}
}

空间复杂度O（V），以邻接矩阵表示，时间复杂度O（）;以邻接表表示，时间复杂度O（V+E）

图的应用

最小生成树

对于一个带权连通无向图G=（V，E），生成树不同，每棵树的权也可能不同。设R为G的所有生成树的集合，若T为R中边的权值之和最小的那棵生成树，则T称为G的最小生成树。

Prim算法

初始时从图中任取一顶点加入树T，此时树中只含有一个顶点，之后选择一个与当前T中顶点集合距离最近的顶点，并将该顶点和相应的边加入T，每次操作后T中的顶点数和边数都增1.以此类推，直至图中所有的顶点都并入T，得到的T就是最小生成树。此时T中必然有n-1条边。
时间复杂度为O（）

Kruskal算法

初始时只有n个顶点而无边的非连通图T，每个顶点自成一个连通分量，然后按照变得权值由小到大的顺序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T，否则舍弃此边而选择下一条权值最小的边。
时间复杂度为O（）

最短路径

Dijkstra算法：求图中某一点到其他顶点的最短路径（O（））不一定能解决负边
Floyd算法：求各顶点之间最短路径问题（O（）） 允许图中带负权值的边，但不允许有包含带负权值的边组成回路

拓扑排序

AOV网：用顶点表示活动，用有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行的一种关系，则称这种有向图称为顶点表示活动网络。在AOV网中，活动Vi是Vj的直接前驱，活动Vj是活动Vi的直接后继

bool TopologicalSort(Graph G){
	InitStack(S);                            //初始化栈，存储入度为0的顶点
	int i;
	for(i=0;i<G.vexnum;i++){
		if(indegree[i]==0){
			Push(S,i);                       //将所有入度为0的顶点进栈
		}
	}
	int count=0;                             //计数，记录已经输出的顶点数
	while(!IsEmpty(S)){                      //栈不空，则存在入度为0的顶点
		Pop(S,i);                            //栈顶元素出栈
		print[count++]=i;                    //输出
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){
		//将所有i指向的顶点的入度减1，并将入度为0的顶点压入栈
			v=p->adjvex;
			if(!(--indegree[v])) Push(S,v);  //入度为0，入栈
		}
	}
	if(count<G.vexnum) return false;         //排序失败，有向图存在回路
	else return true;
}

采用邻接表的时间复杂度O（V+E），采用邻接矩阵的时间复杂度O（）

关键路径

带权有向图中具有最大路径长度的路径称为关键路径。完成整个工程的最短时间就是关键路径的长度。需要计算每个事件的最早发生时间和最迟发生时间。

XYX Blog

第五章-图