第七章  图

7.1 图的定义及术语
一.        定义  graph=(V,E)，其中，V是顶点的有限集；E是两顶点间的关系集（边集）。
二.        术语  无向图，有向图，弧尾与弧首，邻接点，度（入度、出度），连通图与连通分量，树图与生成树。
三.        特点  任意两点之间都可能存在边，是一种复杂的关系（多对多）。
7.2 图的存储结构
一.        数组表示法
二.        邻接表
三.有向图的十字链表
四.无向图的邻接多重表
7.3 图的遍历

7.3.1 .深度优先遍历 (depth first search)
void dfs (graph g, vtxptr v0){  //从v0出发深度优先遍历图g
  访问v0;  w=v0的第一个邻接点；
  while (当邻结点w存在时)
  {  if （w未访） dfs(g,w); //若W未访问，则深度优先遍历图
   w=下一邻接点；
  }
}// dfs
7.3.2 广度优先遍历
visite(v0); visited[v0]=true; initqueue(Q); enqueue(Q,v0); //v0进队列Q
while (! queueempty(Q))
{ delqueue(Q,v); w:=求V第一个的邻接点；
   while (当邻结点w存在时)
   {  if (w未访)  {  visite(w); visited[w]=true; enqueue(Q,w)  ; }
   w = 下一邻接点；
   }
7.4  最小生成树
一.Kruskal算法
V(T);=V(G); E(T)=[];
while ( E(T)中的边数<n-1
  {  在E（G）中找最小权值的边 (u,v)；
   IF  不构成环 ) 将（u,v）加入E（T）中；
   从E（G）中删除（u,v)
  }
二. PRIME算法
void minispantree_prim (mgraph g, vertextype u)  {
//从u出发构造网g的最小生成树
for ( v=1;v<=vtxnum;v++ )
if (v!=u) {closedge[v].vex=u;closedge[v].lowcost=gn[v];}//初始化
for ( i=1 ; i<=vtxnum-1;++i)
  { k=最小边所在下标位置；输出生成树的边；
  closedge[k].lowcost=0;  //顶点k并入U集
  for ( v=1 ;v<= vtxnum ; ++v)
   if (g[k][v]< closedge[v].lowcost)
   { closedge[v].lowcost=g[k][v]; closedge[v].vex=k;  }
   //在新的顶点并入U之后,重新选择具有最小代价的边
}
}
7.5 有向无环图及应用
7.5.1  拓扑排序
拓扑排序由某个集合上的一个偏序得到该集合上的一个全序. 也可以看成是对线性结构的有向图进行线性化的重要手段.
AOV网-----顶点表示活动， 边表示优先关系  
一.如何进行拓扑排序
(1) 在有向图中选一个没有前趋(即入度为0)的顶点, 输出;
(2) 从图中删除此顶点及以它为尾的弧  (即对入度为0的结点所指的链表中的结点的入度-1)
二.找所有的拓扑序列
三.算法思想
(1) 查邻接表, 若 id(vi)=0 then push(s,vi);
(2) 若栈非空, pop(s，j)；输出顶点j；找vj的后继vk, id(vk)--,若id(vk)=0,则push(s,vk);至栈空止.
四.算法
inistack(s);  //置空栈
for ( i=1;i<=n; ++i)
if ( dig.indegree=0 ) push(s.i); //入度为零的顶点栈
count=0;  //count为计数器,计输出顶点数
while ( ! stackempty(s))
{ j=pop(s); printf(dig[j].vexdata);count++;q=dig[j].firstarc ;
//q指示以vj为尾的第一条弧结点
  while ( q )
   { k=q->adjvex; //顶点vk为 vj的直接后继  dig[k].indegree--;
   if ( dig[k].indegree=0 ) push(s,k);  //新的入度为零的顶点入栈
   q=q->nextarc;
  }
   }
7.5.2 关键路径 ---- 路径长度最长的路径
问题: (1) 完成整个工程需多少时间?
  (2) 哪些活动是影响工程进度的关键?
事件         1           2         3         4         5         6         7         8         9        
Ve         0         6         4         5          7         7         16     &nb