图的定义和术语.ppt

第七章图7.1图的定义和术语基本术语：
1.有向图与无向图
在有向图中，顶点对<v,w>是有序的。在无向图中，顶点对(x,y)是无序的。有向边又可称为弧,<vi,vj>中vi称为弧尾或初始点，vj称为弧头或终端点。2.邻接点及关联
若无向图中存在边(v,u)，则称顶点v和u互为邻接点；边(v,u)依附于顶点v和u；或者说边(v,u)和顶点v和u相关联。
3.顶点的度、入度、出度在无向图中：顶点V的度=与V相关联的边的数目
在有向图中：
顶点V的出度=以V为狐尾的有向边数
顶点V的入度=以V为狐头的有向边数
顶点V的度=V的出度+V的入度4.路径、回路例：有向图G2在一条路径中,若除起点和终点外,所有顶点各不相同,
则称该路径为简单路径。
由简单路径组成的回路称为简单回路。
在图G1中，V0,V1,V2,V3是简单路径。V0,V1,V2,V4,V1不是简单路径。
在图G2中，V0,V2,V3,V0是简单回路。非连通图(a)9.连通分量（强连通分量）有向图G的极大强连通子图称为G的强连通分量。极大强连通子图意思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不再连通
包含无向图G所有顶点的极小连通子图称为G的生成树
对非连通图，则称由各个连通分量的生成树的集合为非连通图的生成森林。例：例：邻接矩阵类型定义:邻接表的类型定义
#defineMAX_VERTEX_NUM20
typedefstructArcNode{
intadjvex;
structArcNode*nextarc;
InfoType*info;
}ArcNode;adjvexnextarc例：例：7.3图的遍历V1深度优先遍历算法（递归算法）
Booleanvisited[MAX];
Status(*VisitFunc)(intv);
voidDFSTraverse(GraghG,Status(*Visit)(intv)){
VisitFunc=Visit;
for(v=0;v<G.vexnum;++v)visited[v]=FALSE;
for(v=0;v<G.vexnum;++v)if(!visited[w])DFS(G,v);
}
voidDFS(GraghG,intv)
{visited[v]=TRUE;VisitFunc(v);
for(w=FirstAdjVex(G.v);w>=0;w=NextAdjVex(G,v,w))
if(!visited[w])DFS(G,W);
}V17.3.2广度优先搜索广度优先遍历算法
voidBFSTraverse(GraphG,Status(*Visit)(intv)){
for(v=0;v<G.vexnum;++v)visited[v]=FALSE;
InitQueue(Q);
for(v=0;v<G.vexnum;++v)
if(!visited[v]){
visited[v]=TRUE;Visit(v);
EnQueue(Q,v);
while(!QueueEmpty(Q)){
DeQueue(Q,u);
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
Visited[w]=TRUE;visit(w);
EnQueue(Q,w);}
}
}
}V1例:7.4图的连通性问题算法思想：设N=(V,{E})是连通网，TE是N上最小生成树中边的集合。
1.初始令U={u0},(u0V),TE=。
2.在所有uU,vV-U的边(u,v)E中，找一条代价最小的边(u0,v0)。
3.将(u0,v0)并入集合TE，同时v0并入U。
4.重复上述操作直至U=V为止，则T=(V,{TE})为N的最小生成树。例：例：7.5有向无环图及其应用例：C1算法实现：
1.以邻接表作存储结构。
2.把邻接表中所有入度为0的顶点进栈。
3.栈非空时，输出栈顶元素Vj并退栈；在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈。
4.重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。4问题提出：把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始。定义：
AOE网(ActivityOnEdge)：也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。
路径长度：路径上各活动持续时间之和。
关键路径：路径长度最长的路径。
ve(j)：表示事件Vj的最早发生时间。
vl(j)：表示事件Vj的最迟发生时间。
e(i)：表示活动ai的