图5——AOV网和AOE网

AOV网：
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。

特点：
1.AOV网中的弧表示活动之间存在的某种制约关系。
2.AOV网中不能出现回路 。

拓扑序列：

设G=(V，E)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列；
当且仅当满足下列条件：若从顶点vi到vj有一条路径，则在顶点的拓扑序列中顶点vi必在顶点vj之前。

拓扑排序：

对一个有向图构造拓扑序列的过程称为拓扑排序 。

基本步骤：
⑴ 从AOV网中选择一个没有前驱的顶点并且输出；
⑵ 从AOV网中删去该顶点，并且删去所有以该顶点为尾的弧；
⑶ 重复上述两步，直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点。

—看上述步骤是不是觉得有点啰嗦，简单点操作：就是依次删除入度为0的结点。

设计数据结构部分：

基本思路：

（1）找G中无前驱的顶点
- 查找indegree ［i］为零的顶点vi；
（2）修改邻接于顶点i的顶点的入度（删除以i为起点的所有弧）

• 对链在顶点i后面的所有邻接顶点k，将对应的indegree［k］ 减1。
  为了避免重复检测入度为零的顶点，可以再设置一个辅助栈，若某一顶点的入度减为0，则将它入栈。每当输出某一入度为0的顶点时，便将它从栈中删除。

void TOpSort(){
   int  top=-1, count=0;
   for(int i=0;i<vertexnum;i++)
       if(adjlist[i].in==0) 
            s[++top]=i;
         while(top!=-1){
             j=s[top--];
             cout <<adjlist[j].vertext;
             count++;
             p=adjlist[j].firstedge;
         while(p!=NULL){
             k=p->adjvex;
             adjlist[k].in--;
             if(adjlist[k].in==0) 
                s[top++]=k;
             p=p->next;
         } 
     }
        if (count<vertexNum)
          cout<<“有回路”;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

AOE网

在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。
需要注意的是，AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为终点（或汇点）。

性质：
⑴ 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；
⑵ 只有在进入某顶点的各活动都结束，该顶点所代表的事件才能发生。

存储结构的选择：

为处理方便，同时采用了邻接矩阵和边集数组两种存储结构。
邻接矩阵可以方便的查找邻接点，完成时间的最早和最晚发生时间的计算。
边集数组可以方便的计算时间的活动的最晚发生时间

struct Edge{
	int from;
	int to;
	int e;
	int l;
};

class Grap{
	int vertexnum,e;
	int **adjlist;   //邻接矩阵
	int start,end;
	Edge *edge;  //边集数组
public:
	Grap(int n,int e);
	int  path();
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

 q.push(0);//源点事件入队
for(j=0;j<vertexnum;j++)	{  //初始化每个事件最早发生时间
	ve[j]=0;	visit[j]=0;	}
visit[0]=1;	
 while(!q.empty())	{		
	i=q.front();       //利用标准模板库中的队列实现
	q.pop();
	for(j=0;j<vertexnum;j++){//计算i的邻接点的ve
		if(adjlist[i][j]!=9999 && ve[i]+adjlist[i][j]>ve[j] ){
			ve[j]=ve[i]+adjlist[i][j];
			if(!visit[j])   //如果j没有被访问过，顶点j入队
				q.push(j);
			visit[j]=1;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

  q.push(vertexnum-1);
	for(j=0;j<vertexnum;j++)	{
		vl[j]=ve[vertexnum-1];	visit[j]=0;	}
    while(!q.empty())	{
		i=q.front();
		q.pop();
		for(j=0;j<vertexnum;j++)	{
			if(adjlist[j][i]!=9999 && vl[i]-adjlist[j][i]<vl[j] ){
				vl[j]=vl[i]-adjlist[j][i];
				if(!visit[j])
					q.push(j);
				visit[j]=1;
			}
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

for(i=0;i<e;i++)
	{
		edge[i].e=ve[edge[i].from];
	}
1
2
3
4

for(i=0;i<e;i++)
	{
		edge[i].e=ve[edge[i].from];
		edge[i].l=vl[edge[i].to]-adjlist[edge[i].from][edge[i].to];
	}
1
2
3
4
5

图的连通性

一.无向图：

要想判定一个无向图是否为连通图，或有几个连通分量，通过对无向图遍历即可得到结果。

**连通图：**仅需从图中任一顶点出发，进行深度优先搜索（或广度优先搜索），便可访问到图中所有顶点。
**非连通图：**需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。

求无向图的连通分量（非连通图的遍历方法）

1.count=0;
2.  for (图中每个顶点v)
       2.1 if (v尚未被访问过) 
             2.1.1 count++;
             2.1.2 从v出发遍历该图（函数调用）；
3.  if (count==1) cout<<"图是连通的";
     else cout<<"图中有"<<count<<"个连通分量";
1
2
3
4
5
6
7

有向图的连通子图的求解过程

⑴ 从某顶点出发进完（即出栈）的顺序将顶点排列起来行深度优先遍历，并按其所有邻接点都访问。
⑵ 从最后完成访问的顶点出发，沿着以该顶点为头的弧作逆向的深度优先遍历。若不能访问到所有顶点，则从余下的顶点中最后访问的那个顶点出发，继续作逆向的深度优先遍历，直至有向图中所有顶点都被访问到为止。