6、图
1、概念
顶点
简单图:没有指向自己的边、没有重复的边
无向图
无向边(边)
度:边/2
连通:两顶点间有路径存在
连通图:任意两个顶点都是联通的
连通图最少边:n-1
非连通图最多边:
连通分量:极大连通子图(包含尽可能多的子图和边)
完全图::任意两个顶点之间都存在边
有向图
有向边(弧)
入度、出度:有向图的度=入度+出度
强连通:两个顶点之间正向、逆向均有路径
强连通图:任意两个顶点之间都是强连通的
强连通的最少边:n(环)
连通分量:极大强连通子图(必须强连通、包括尽可能多的边和点)
完全图:任意两个顶点之间都存在方向相反的两条弧
简单图:没有指向自己的边、没有重复的边
路径:两个顶点之间的顶点序列
回路:第一个顶点和最后一个顶点相同的路径
简单路径:路径中所有的顶点不重复出现
简单回路:除了第一个和最后一个顶点外,其它顶点不重复
路径长度:路径上边的数量
顶点到顶点的距离:最短路径(若存在)
子图:首先是个图。分别取点集和边集的子集构成
生成子图:子图中包含了原图的所有顶点
生成树:包含全部顶点的一个极小连通子图(边尽可能少、保持联通)
生成森林:由非连通图各个连通分量的生成树构成
带权图
边的权:边所带的权值
带权路径长度:路径上所有边的权值之和
树:不存在回路且连通的无向图
2、表示
邻接矩阵
#define MaxVertexNum 100 //顶点数目的最大值
typedef struct{
char Vex [MaxVertexNum] ; //顶点表
int Edge [MaxVertexNum] [MaxVertexNum] ; //邻接矩阵,边表
int vexnum, arcnum; //图的当前顶点数和边数/弧数
} MGraph;
有向图:
出度:行
入度:列
优点
快速查找两点之间是否有边
缺点
不适用于查找从某点出发的所有边
邻接表法

//"边/弧"
typedef struct ArcNode{
int adivex; //边/弧指向哪个结点
struct ArcNode *next ; //指向下一条弧的指针
//InfoType info; //边权值
}ArcNode;
//"顶点"
typedef struct VNode{
VertexType data; //顶点信息
ArcNode *first; //第一条边/弧
}VNode,AdjList [MaxVertexNum];
//用邻接表存储的图
typedef struct{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
十字链表:有向图
邻接多重表:无向图
优点
快速查找从某点出发的所有边
缺点
不适用于查找某两点之间是否有边
3、遍历
广度优先BFS
节点入队
队列非空,则将队头出队
访问队头节点的相邻节点,并将之存入队尾
循环操作直至队空
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]) //对每个连通分量调用一次BI
BFS(G,i); //vi未访问过,从vi开始BF
}
//广度优先遍历
void BFS(Graph G,int v){ //从顶点v出发,广度优先遍历图G
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入队列
}//if
}//while
}
BFS函数调用的次数=连通分量数
时间复杂度:
邻接矩阵表示:
访问所有顶点:O(V)
访问每个顶点的邻接点:O(V)
总时间复杂度:
邻接表表示:
访问所有顶点:O(V)
访问各个顶点的邻接点:O(E)
总时间复杂度:
深度优先DFS
bool vis ited [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) //本代码中是从v=0开始遍历
if( !visited[v])
DFS(G,v);
}
void DFS(Graph G,int v){ //从顶点v出发,深度优先遍历图G
visit(v); //访问顶点v
visited[v]=TRUE; //设已访问标记
for (w=FirstNeighbor(G, v);W>=0;w=NextNeighor(G,v,w)
if(!visited[w]){ //w为u的尚未访问的邻接顶点
DFS(G,w);
}//if
}
DFS调用的次数=顶点数
时间复杂度:
邻接矩阵表示:
访问所有顶点:O(V)
访问每个顶点的邻接点:O(V)
总时间复杂度:
邻接表表示:
访问所有顶点:O(V)
访问各个顶点的邻接点:O(E)
总时间复杂度:
4、最小生成树
Prim算法
每次将代价最小的顶点接入树
适合边稠密的图
时间复杂度为:
Kruskal算法
每次选择权值最小的边,连接这条边的两个节点(两顶点不能都在已有集合中)
适合边稀疏的图
采用堆存放边的集合
时间复杂度
每次选择最小权值的边:
总时间复杂度:
5、最短路径
Dijkstra算法
从某点除法,遍历所有未确定最短路径的点,算出其距离
选择未确定的点中距离最短的作为下一个遍历的目标,并将其路径设为true
将距离改为从新的点出发的路径中最短的
不适合求有负权值的图





Floyd算法
首先不允许任何定点作为中转

接下来允许在中转
对比原来矩阵中与
若中转路径大 ,则替换为新的,并修改
例:

允许在、中转

允许在、、中转

查询最短路径
,:
到的最短路径为4
不经过中转
,:
到的最短路径为10
经过中转
for (int k=0; k<n; k++){ //以Vk为中转点
for (int i=0; i<n; i++){ //遍历矩阵,i行j列
for (int j=0; j<n; j++){
if (A[i][j]>A[i][k]+A[k][j]){
A[i][j]=A[i][k]+A[k][j];
path[i][j]=k;
}
}
}
}
时间复杂度:
空间复杂度:两个矩阵
实例:

求到的最短路径
中转点为3
到中转点为2
到直接相连
目前路径为
到中转点为1
最短路径为,为4
6、拓扑排序
DAG图:有向无环图
AOV网:使用DAG图表示一个工程,顶点表示活动
拓扑排序:找到做事的先后顺序
从AOV网中找一个入度为0的顶点并输出
从AOV网中删除这个顶点和所有以它为起点的边
重复直到AOV网为空或者不存在入度为0的点为止
bool TopologicalSort(Graph G){
InitStack(S); //初始化栈, 存储入度为0的顶点
for(int 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; //输出顶点i
for(p=G.vertices[i].firstarc; p; p=p->nextarc){
//将所有i指向的顶点的入度减1,并且将入度减为0的顶点压入栈S
v=p->adjvex;
if(!(--indegree[v]))
Push(S,v); //入度为0,则入栈
}
}//while
if(count<G .vexnum)
return false; //排序失败,有向图中有回路
else
return true; //拓扑排序成功
}
7、关键路径
AOE网:带权有向图,用边表示活动,边的权值表示活动的开销
关键路径:具有最大路径长度的路径,决定整个事件的完成时间
最早开始时间:弧起点所表示的事件最早开始的时间
最迟开始时间:弧尾所表示的事件最晚开始的时间
时间余量:不影响整个工程的情况下,事件可以拖延的时间
关键活动:时间余量为0的活动
Last updated