- 浏览: 716105 次
- 性别:
- 来自: 嘉兴
文章分类
- 全部博客 (386)
- Struts1.1 (2)
- Database (18)
- Core Java (15)
- Log4j (4)
- SSH (0)
- Dao (1)
- Architecture Design (1)
- References (2)
- Eclipse&MyEclipse (10)
- Hibernate (7)
- Spring (8)
- JavaMail (1)
- Data Structure And Algorithm (48)
- Struts 2 (2)
- SSI (1)
- SSL (2)
- JSTL (1)
- EJB3 (2)
- NET (2)
- XML (2)
- Components (2)
- Ant (3)
- Multi Thread (1)
- Performance Monitoring (1)
- Web Server (17)
- Oracle (1)
- jQuery (8)
- Regular Expression (1)
- Weblogic (1)
- Exception (1)
- Security (2)
- File Manipulation (1)
- JavaScript (12)
- JVM (2)
- HTML&DIV&CSS (4)
- Android (10)
- Beyond GFW (0)
- Business (0)
- SVN (6)
- 虚拟主机 (1)
- Virtual Host (3)
- My mentality (5)
- OS (15)
- ISPMP (3)
- Magento (5)
- Jsoup&HttpClient (7)
- LINUX (9)
- Database Design (0)
- Power Designer (1)
- TaobaoOpenPlatform (2)
- C/C++ (3)
- Maven (11)
- Quartz (1)
- Load Balance (1)
- Zabbix (4)
- Product&Business (1)
- Pay Interface (1)
- Tomcat (2)
- Redis (1)
- 集群 (1)
- Session (1)
- 共享Session (1)
- Jedis (1)
- jenkins (1)
- 持续集成 (1)
- Web前端 (1)
最新评论
-
aqq331325797:
特意注册账号上来说一句。牛逼!
swagger2.2.2 与 spring cloud feign冲突 -
KitGavinx:
跨顶级域名怎么保持sessionid一致?
Tomcat7集群共享Session 基于redis进行统一管理 -
jaychang:
dujianqiao 写道HI ,能否给一个完整的demo 啊 ...
淘宝订单同步方案 - 丢单终结者 -
GGGGeek:
找了一会儿,感觉mybatis应该没有这种操作,直到发现博主的 ...
mybatis collection list string -
dujianqiao:
HI ,能否给一个完整的demo 啊 ?
淘宝订单同步方案 - 丢单终结者
/********************************** title: 拓扑排序(邻接表实现) author: jay chang date: 2009/07/16 **********************************/ #include<iostream> #define MAXSIZE 99 #define TRUE 1 #define FALSE 0 using namespace std; typedef char VertexData; typedef int AdjType; typedef struct Stack //定义栈 { int data[MAXSIZE+1]; int top; }Stack; typedef struct ArcNode //定义弧结点 { AdjType adj; ArcNode *nextArc; }ArcNode; typedef struct VertexNode //定义顶点 { VertexData vertexData; ArcNode *firstArc; }VertexNode; typedef struct AdjMatrix //定义图 { VertexNode vertexNodes[MAXSIZE+1]; int verNum,arcNum; }AdjMatrix; //全局变量 int indegree[MAXSIZE+1]={0}; int LocateGraph(AdjMatrix *g, VertexData vertexData) { int iIndex; for(iIndex=1;iIndex<=g->verNum;iIndex++) { if(vertexData==g->vertexNodes[iIndex].vertexData) return iIndex; } return FALSE; } void CreateGraph(AdjMatrix *g) { int iCount,arcStart,arcEnd;char start,end; cout<<"*****************************************"<<endl; cout<<"*** 拓扑排序\n"; cout<<"*** Author: Jay Chang\n"; cout<<"*****************************************"<<endl; cout<<"输入有向无环图的顶点,及弧数\n"; cin>>g->verNum>>g->arcNum; cout<<"输入有向无环图的顶点信息\n"; ArcNode *q=NULL; for(iCount=1;iCount<=g->verNum;iCount++) { cout<<"输入第"<<iCount<<"个顶点的信息"<<endl; cin>>g->vertexNodes[iCount].vertexData; g->vertexNodes[iCount].firstArc=NULL; } for(iCount=1;iCount<=g->arcNum;iCount++) { cout<<"输入第"<<iCount<<"条弧的起始与结束的信息"<<endl; cin>>start>>end; arcStart=LocateGraph(g,start); arcEnd =LocateGraph(g,end); //添加弧结点 q=(ArcNode*)malloc(sizeof(ArcNode)); q->adj=arcEnd; q->nextArc=g->vertexNodes[arcStart].firstArc; g->vertexNodes[arcStart].firstArc=q; //对于第arcEnd个顶点的入度值加1 indegree[arcEnd]++; } } //判栈空 int IsEmpty(Stack *stack) { return stack->top==-1?TRUE:FALSE; } //初始化栈 void InitStack(Stack *stack) { stack->top=-1; } //出栈 void Pop(Stack *stack,int *iIndex) { *iIndex=stack->data[stack->top--]; } //进栈 void Push(Stack *stack,int value) { stack->data[++stack->top]=value; } //拓扑排序 int Tuopu(AdjMatrix *g) { int iCount,count=0; Stack *stack=(Stack*)malloc(sizeof(Stack)); InitStack(stack); ArcNode *p=NULL; //对于入度为0的顶点入栈 for(iCount=1;iCount<=g->verNum;iCount++) { if(indegree[iCount]==0){ Push(stack,iCount); } } cout<<"输出拓扑序列\n"; //输出顶点后,将与该顶点相连的顶点的边删除,将与相连顶点的入度减1,如减后为0,入栈,栈空结束 while(!IsEmpty(stack)) { Pop(stack,&iCount); cout<<g->vertexNodes[iCount].vertexData<<" "; count++; p=g->vertexNodes[iCount].firstArc; while(p!=NULL) { if(--indegree[p->adj]==0) Push(stack,p->adj); p=p->nextArc; } }//end while if(count<g->verNum){ cout<<"有回路"<<endl; return FALSE; } cout<<endl; } int main() { AdjMatrix *g=(AdjMatrix*)malloc(sizeof(AdjMatrix)); CreateGraph(g); Tuopu(g); return 0; }
评论
2 楼
jaychang
2010-07-15
lixia0417 写道
不错,不过要是用java来描述就更好了
呵呵,有时间出个JAVA版的,敬请期待哈。。。
1 楼
lixia0417
2010-07-14
不错,不过要是用java来描述就更好了
发表评论
-
【排序算法系列】希尔排序
2015-12-05 16:14 801希尔排序的概述: a[0]...a[n-1 ... -
归并排序
2015-06-20 15:28 853public class MergeSort { pub ... -
插入排序
2015-06-20 15:27 449/** * 插入排序1 容易理解 * * ... -
有序线性链表归并
2013-10-05 11:30 1502#include<stdio.h> #incl ... -
Trie树 应用 Phone List
2012-06-15 11:21 1140Phone List 时间限 ... -
Trie树 单词查找树 键树(JAVA版附分析说明)
2012-06-13 10:27 5109来源于英文“retrieval”. ... -
Trie树 单词查找树 键树
2012-06-12 08:59 1113转自:http://zh.wik ... -
数字金额转中文大写金额
2010-11-26 15:09 1393/** * 用来将数字金额转化成中文大写的金额 ... -
汉诺塔递归算法
2010-11-25 08:17 1311import java.util.Scanner; /* ... -
约瑟夫出圈
2010-11-24 20:45 1067#include<iostream> #incl ... -
SmartHashSet只是为了解释HashSet的原理
2010-07-26 11:11 1325写该类的目的只是为了 ... -
二叉树中序遍历非递归算法
2010-06-29 23:17 1686#include<iostream> usi ... -
二叉树的创建
2010-06-29 23:15 1094#include<iostream> usi ... -
哈弗曼树建立与哈弗曼编码
2010-06-29 23:12 1202#include<iostream> #de ... -
二叉排序树转双向链表(要求无任何新增节点)
2010-06-29 23:07 2456题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双 ... -
线索二叉树中插入结点
2010-06-29 23:05 1842#include<iostream> usi ... -
二叉排序树的递归与非递归查找
2010-06-29 22:58 2251#include<iostream> usi ... -
二叉树中序线索化及查找某一结点的前驱,后继结点
2010-06-29 22:54 2637#include<iostream> usi ... -
十字链表定义创建查找
2010-06-29 22:44 1279#include<iostream> #defi ... -
稀疏矩阵转置
2010-06-29 22:39 1596#include<iostream> #defi ...
相关推荐
拓扑排序 邻接表实现.zip
基于邻接表存储的图的拓扑排序算法,学习C++和理解数据结构很有帮助
逆邻接表实现拓扑排序,能够更快速直接的计算顶点的入度,即终点指向结点,有几个边表,则代表入度是几
在C语言下利用C语言创建AOE网,并进行拓扑排序。功能模块包含图的创建,图的输出及拓扑排序。
拓扑排序 有注释 邻接表形式的 求入度的
程序所实现的功能: 建立对应的邻接表,对该图进行拓扑排序,并显示排序结果。 输入: 顶点数, 边数及各顶点信息(数据格式为整形) 输出: 拓扑排序结果。 2. 2 概要设计 1.拓扑排序是指由某个集合上的一个偏序得到...
请输入有向图的顶点数和弧数: 6 8 请输入各顶点的值(eg:字符型): ABCDEF 请输入各条弧的始点和终点: AB AC AD CB CE FD FE DE 该有向图的一个拓扑排序为: FACBDE
c语言实现的AOV网的拓扑排序算法,采用动态创建邻接表的方法实现图的构建,内有输入示意图,含有较多的代码注释,欢迎下载学习!!!
用邻接表的方式创建有向图,然后再邻接表的基础上采用静态链表的存储结构实现拓扑排序
实现图的拓扑排序,方法1:采用邻接表存储结构,按照堆栈的实现。 实现图的拓扑排序,方法2:采用邻接矩阵实现:
头歌数据结构图的邻接表存储及遍历操作 第1关图的邻接表存储及求邻接点操作 第2关图的深度遍历 第3关图的广度遍历 稳过
【数据结构】基于紧缩图的邻接表的拓扑排序.doc
数据结构基于紧缩图的邻接表的拓扑排序-毕业论文.doc
毕业设计-数据结构基于紧缩图的邻接表的拓扑排序.doc
【数据结构】基于紧缩图的邻接表的拓扑排序正文终稿.doc
(3)以有向图的邻接表为基础实现并输出它的拓扑排序序列。 (4)在主函数中设计一个简单的菜单,分别调试上述算法。 2.无向图 (1)建立一个无向图的邻接表,并输出该邻接表。 (2)采用邻接表存储实现无向图的...
数据结构实习常见题,拓扑排序,简易清晰,通俗易懂!希望对你有所帮助。
数据结构C#的课程设计 拓扑排序 利用邻接表实现数据存储 其中还运用到了栈
1.采用C++实现; 2.熟练掌握图的应用; 3.熟练掌握图的邻接表存储结构以及拓扑排序的基本思想。 4.上机调试程序,掌握查错、排错使程序能正确运行。