数据结构——邻接表表示的图的拓扑排序算法

发布时间:2016-12-8 4:09:13 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"数据结构——邻接表表示的图的拓扑排序算法",主要涉及到数据结构——邻接表表示的图的拓扑排序算法方面的内容,对于数据结构——邻接表表示的图的拓扑排序算法感兴趣的同学可以参考一下。

#include <iostream> using namespace std; #include <stdio.h> #include <stdlib.h> #define OK 1 #define NULL 0 #define MAX_VERTEX_NUM 20 // 最大顶点数 typedef char VertexType; typedef int VRType; typedef int InforType; typedef int indegree[MAX_VERTEX_NUM]; typedef struct ArcNode { int adjvex; //该边所指的顶点的位置 struct ArcNode *nextarc; //指向下一条边的指针 int weight; //边的权 }ArcNode; //表的结点 typedef struct VNode { VertexType data; //顶点信息(如数据等) ArcNode *firstarc; //指向第一条依附该顶点的边的弧指针 }VNode, AdjList[MAX_VERTEX_NUM]; //头结点 typedef struct ALGraph { AdjList vertices; int vexnum, arcnum; //图的当前顶点数和弧数 }ALGraph; //初始化图 void init_ALGraph(ALGraph &g) { g.arcnum=0; g.vexnum=0; } //返回顶点v在顶点向量中的位置 int LocateVex(ALGraph &G, char v) { int i; for(i = 0; v != G.vertices[i].data && i < G.vexnum; i++) ; if(i >= G.vexnum) return -1; return i; } //增加节点 void add_vex(ALGraph &G) { cout<<"输入有向图顶点数: "<<endl; cin>>G.vexnum; //getchar(); //吃回车 cout<<"输入顶点信息:"<<endl; for(int i = 0; i < G.vexnum; i++) { cin>>G.vertices[i].data; //构造顶点向量 G.vertices[i].firstarc = NULL; //getchar(); } } //增加边 void add_arc(ALGraph &G, indegree indegree) { ArcNode *s; ArcNode *p; for(int k=0; k<G.vexnum; k++) indegree[k]=0; cout<<"输入有向图边数: "<<endl; cin>>G.arcnum; char v1, v2; cout<<"输入边信息:"<<endl; for(k = 0; k < G.arcnum; k++) { cin>>v1>>v2; int i = LocateVex(G, v1); int j = LocateVex(G, v2); //确定v1 , v2在G中的位置 ++indegree[j]; //点j的入度增加1 s = (ArcNode*) malloc (sizeof(ArcNode)); s->adjvex = j; //该边所指向的顶点的位置为j s->nextarc = NULL; if(!G.vertices[i].firstarc) { G.vertices[i].firstarc=s; } else { for(p = G.vertices[i].firstarc; p->nextarc; p = p->nextarc) ; p->nextarc=s; } } } //构造邻接链表 void CreateUDN(ALGraph &G, indegree indegree) { add_vex(G); //增加节点 add_arc(G,indegree); //增加边 } void PrintAdjList(ALGraph &G) { int i; ArcNode *p; cout<<"编号 顶点 邻点编号"<<endl; for(i = 0; i < G.vexnum; i++) { cout<<" "<<i<<" "<<G.vertices[i].data<<" "; for(p = G.vertices[i].firstarc; p; p = p->nextarc) cout<<p->adjvex<<" "; cout<<endl; } } //拓扑排序 int TopologicalSort(ALGraph &g, indegree indegree) { //若G无回路,则输出拓扑排序序列并返回1,若有回路返回0。 ArcNode *q; int i,k; int gettop; int *stack; //建栈将入度为0的顶点入栈 stack=(int *)malloc( g.vexnum*sizeof(int) ); int top=0; for(i = 0; i<g.vexnum; i++) if(0 == indegree[i]) //将入度为0的顶点入栈 stack[++top]=i; int count=0; while(top!=0) { gettop=stack[top--]; cout<<g.vertices[gettop].data<<"-->"; count++; //输出i号顶点,并计数 for(q = g.vertices[gettop].firstarc; q; q = q->nextarc) { k=q->adjvex; if( !(--indegree[k]) ) //将i号顶点的邻接点的入度减1,如果减1后为0,则入栈 stack[++top]=k; }//for }//while cout<<endl; if(count < g.vexnum) return 1; else return 0; } int main() { ALGraph G; indegree indegree; init_ALGraph(G); //初始化图 CreateUDN(G, indegree); //创建图 PrintAdjList(G); //打印图 TopologicalSort(G, indegree); return 0; }

上一篇:防止sql注入的源代码
下一篇:java 正则表达式详解

相关文章

相关评论