矢量图类操作集锦

/* 矢量图类操作集锦(顶点及弧的插入，删除，深度及广度优先遍历，AOV 拓扑排序(栈和队列)，AOE 关键路径
最短路径长度 Dijkstra 和 Floyd 算法及各顶点之间最短路径算法的实现)

      作者: rubily
  完成时间: 2008年7月15日

求最短路径长度的 Dijkstra 算法思想:
1. 初始化: dist[i] ← Edge[v0][i] (源点v0到顶点vi有边,则为权值,否则为 -1 表示无穷大)
2. 求最短路径长度: dist[k] ← min{ dist[i] }
3. 修改: dist[i] ← min{ dist[i], dist[k] + Edge[k][vi] }
4. 若 S = V ,则算法结束,否则转2开始执行

求最短路径长度的 Floyd 算法思想:
1. 初始化: dist[u] ← Edge[v0][u] (源点v0到顶点vi有边,则为权值,否则为 MAXINT 表示无穷大)
2. 逐一比较 dist[u] 和 dist[k] + Edge[k][u] ( 假设dist[k] 为从源点 v0 到顶点 k 的最短路径),
并求得 dist[u] = min{ dist[u], dist[k] + Edge[k][u] }
3. 重复步骤 2 循环执行 vexcount -1 次后退出,算法结束

求关键路径算法思想:
1. 初始化最早开始时间<拓扑排序>: ve[k] = 0   (k = 0,1,....n-1),
求最早开始时间: ve[k] ← max{ ve[k], ve[i] + duration<i,k> }  (i 是 k 的前驱顶点)
2. 初始化最迟开始时间<逆向拓扑排序>: vl[k] = max{ ve[i] } (完成点的最早开始时间,最大值),
求最迟开始时间: vl[k] ← min{ vl[k], vl[i] - duration<k,i> } (i 是 k 的后继顶点)
关键活动点: 事件最早开始时间ve[i] = 事件最迟开始时间的活动vl[i]*/

#include<assert.h>
#include<iostream.h>
#include<iomanip.h>
typedef char ElemType;
#define MAXINT 1000

#define MAXSIZE 10
#define MAX_VERTEX_NUM 10
struct ArcNode
{
int adjvex; // 邻接顶点编号
int weight; // 权值
struct ArcNode* nextarc;
};
struct VertexNode
{
ElemType vexdata; // 顶点数据
int inD, outD;  //入度 , 出度
ArcNode* firstarc;
};
struct VertexType
{
int ve;  // 最早开始时间
int vl;  // 最迟开始时间
};
class Graph{
public:
Graph(int N = 10);
Graph(Graph& G,int N);
~Graph();
void InsertVertex(const ElemType& vertex);  // 插入顶点节点
void InsertArcF(const int v1,const int v2,int weight);  // 在邻接点首部插入弧 <v1,v2>
void InsertArcR(const int v1,const int v2,int weight); // 在邻接点尾部插入弧 <v1,v2>
void DeleteVertex(const ElemType vertex);      // 删除顶点及关联的弧
void DeleteArc(const int v1,const int v2);   // 删除弧
int VertexOutD(const ElemType vertex);  // 顶点出度