void DeleteVex(int i); //删除图中第i个顶点
void InsertArc(int i, int j); //在图中插入一条边，其依附的两个顶点的编号为i和j void DeleteArc(int i, int j); //在图中删除一条边，其依附的两个顶点的编号为i和j void DFSTraverse(int v); //深度优先遍历图 void BFSTraverse(int v); //广度优先遍历图 private: VertexNode adjlist[MaxSize]; //存放顶点表的数组 int vertexNum, arcNum; //图的顶点数和边数 };
template
ALGraph::ALGraph(T a[ ], int n, int e) {
vertexNum=n; arcNum=e;
for (i=0; i adjlist[i].vertex=a[i]; adjlist[i].firstedge=NULL; } for (k=0; k cin>>i>>j; //输入边所依附的两个顶点的序号 s=new ArcNode; s->adjvex=j; //生成一个边表结点s s->next=adjlist[i].firstedge; //将结点s插入到结点i的边表的表头 adjlist[i].firstedge=s; } } template void ALGraph::DFSTraverse(int v) { cout< while (p) //依次搜索顶点v的邻接点j { j=p->adjvex; if (visited[j]==0) DFSTraverse(j); p=p->next; } } template void ALGraph::BFSTraverse(int v) { front=rear=-1; //初始化队列, 假设队列采用顺序存储且不会发生溢出 cout< v=Q[++front]; p=adjlist[v].firstarc; //边表中的工作指针p初始化 while (p) { j= p->adjvex; if (visited[j]==0) { cout< p=p->next; } } } 2.图的邻接矩阵类的定义 const int MaxSize=10; //图中最多顶点个数 template public: MGraph(T a[ ], int n, int e ); //构造函数，初始化具有n个顶点e条边的图 ~MGraph( ) { } //析构函数 T GetVex(int i); //取图中第i个顶点数据信息 void PutVex(int i, T value); //将图中第i个顶点的数据域置为value void InsertVex(int i, T value); //在图中插入一个顶点，其编号为i，值为value void DeleteVex(int i); //删除图中第i个顶点 void InsertArc(int i, int j); //在图中插入一条边，其依附的两个顶点的编号为i和j void DeleteArc(int i, int j); //在图中删除一条边，其依附的两个顶点的编号为i和j void DFSTraverse(int v); //深度优先遍历图 void BFSTraverse(int v); //广度优先遍历图 private: T vertex[MaxSize]; //存放图中顶点的数组 int arc[MaxSize][MaxSize]; //存放图中边的数组 int vertexNum, arcNum; //图的顶点数和边数 }; template MGraph::MGraph(T a[ ], int n, int e) { vertexNum=n; arcNum=e; for (i=0; i for (i=0; i for (k=0; k cin>>i>>j; //边依附的两个顶点的序号 arc[i][j]=1; //置有边标志 arc[j][i]=1; } } 3．图的拓扑排序 void TopSort( ) { top= -1; count=0; //采用顺序栈S并初始化，累加器初始化； for (i=0; i while (top!= -1 ) //当图中还有入度为0的顶点时循环 { j=S[top--]; //从栈中取出一个入度为0的顶点 cout< p=adjlist[j].firstedge; //扫描顶点表，找出顶点j的所有出边 while (p!=NULL) { k=p->adjvex; adjlist[k].in--; //将入度减1，如果为0，则将该顶点入栈 if (adjlist[k].in==0) S[++top]=k; p=p->next; } } if (count } 4．图的Prim算法，求图的最小生成树 void Prim(MGraph G) { for (i=1; i { lowcost[i]=G.arc[0][i]; adjvex[i]=0; } lowcost[0]=0; //将顶点0加入集合U中 for (i=1; i k=MinEdge(lowcost, G.vertexNum) //在lowcost中寻找最短边的顶点k cout<<\(\)\ //输出加入TE中的边 lowcost[k]=0; //将顶点v加入集合U中 for (j=1; j lowcost[j]=G.arc[k][j]; adjvex[j]=k; } } } 5．图的最短路径 void Dijkstra(MGraph G, int v) { for (i=0; i { dist[i]=G.arc[v][i]; if (dist[i]!=∞) path[i]=G.vertex[v]+G.vertex[i]; else path[i]=\ } s[0]=G.vertex[v]; //初始化集合S dist[v]=0; //标记顶点v为源点 num=1; while (num k=0; for (i=0; i if ((dist[i] s[num++]= G.vertex[k]; //将新生成的终点加入集合S dist[k]=0; //置顶点vk为已生成终点标记 for (i=0; i if (dist[i]>dist[k]+G.arc[k][i]) { dist[i]=dist[k]+G.arc[k][i]; path[i]=path[k]+G.vertex[i]; } } } void Floyd(MGraph G) { for (i=0; i dist[i][j]=G.arc[i][j]; if (dist[i][j]!=∞) path[i][j]=G.vertex[i]+G.vertex[j]; else path[i][j]=\ } for (k=0; k for (i=0; i if (dist[i][k]+dist[k][j] dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=path[i][k]+path[k][j]; } } 注意问题 １．注意理解各算法实现时所采用的存储结构。 ２．注意区别正、逆邻接矩阵。
