/*****************************
title : 拓扑排序(邻接矩阵实现)
author: jay chang
date : 2009/07/14
*****************************/
#include<iostream>
using namespace std;
#define MAXSIZE 99
#define FALSE 0
#define TRUE 1
typedef char VertexData;
typedef int AdjType;
typedef struct VertexNode
{
VertexData vertexData;
}VertexNode;
typedef struct ArcNode
{
AdjType adj; //弧的权值
}ArcNode;
typedef struct AdjMatrix
{
VertexNode vertexNodes[MAXSIZE+1];
ArcNode arcNodes[MAXSIZE+1][MAXSIZE+1];
int vertexNum,arcNum;
}AdjMatrix;
typedef struct Queue
{
int data[MAXSIZE+1];
int head,rear;
}Stack;
/**********************************************************************************
Function Name:LocateGraph
Return Type: int
Function Description: 查询在图中是否存在结点信息为vertexData的结点,存在返回结
点位置,否则返回FALSE。
**********************************************************************************/
int LocateGraph(AdjMatrix* g,VertexData vertexData)
{
int iIndex;
for(iIndex=1;iIndex<=g->vertexNum;iIndex++)
{
if(vertexData==g->vertexNodes[iIndex].vertexData)
return iIndex;
}
return FALSE;
}
/**********************************************************************************
Function Name:InitAdjMatrix
Return Type: void
Function Description: 初始化有向无环图
**********************************************************************************/
inline void InitAdjMatrix(AdjMatrix* g)
{
for(int iIndex=1;iIndex<=g->vertexNum;iIndex++)
{
for(int jIndex=1;jIndex<=g->vertexNum;jIndex++)
{
g->arcNodes[iIndex][jIndex].adj=0;
}
}
}
/**********************************************************************************
Function Name:CreateAdjMatrix
Return Type: void
Function Description: 创建连通图
**********************************************************************************/
void CreateAdjMatrix(AdjMatrix* g)
{
cout<<"******************************************************************\n";
cout<<" 拓扑排序\n";
cout<<"******************************************************************\n";
cout<<"输入连通图的顶点数,弧数:\n";
cin>>g->vertexNum>>g->arcNum;
cout<<"输入顶点信息"<<endl;
int iCount,start,end;char arcStart,arcEnd;
InitAdjMatrix(g);
for(iCount=1;iCount<=g->vertexNum;iCount++)
{
cout<<"结点"<<iCount<<"的信息"<<endl;
cin>>g->vertexNodes[iCount].vertexData;
}
for(iCount=1;iCount<=g->arcNum;iCount++)
{
cout<<"输入第"<<iCount<<"条弧的起始,终点"<<endl;
cin>>arcStart>>arcEnd;
start=LocateGraph(g,arcStart);end=LocateGraph(g,arcEnd);
g->arcNodes[start][end].adj=1;
}
}
/**********************************************************************************
Function Name:FindID
Return Type: void
Function Description: 计算每个顶点的入度
**********************************************************************************/
void FindID(AdjMatrix* g,int indegree[])
{
for(int jIndex=1;jIndex<=g->vertexNum;jIndex++)
{
for(int iIndex=1;iIndex<=g->vertexNum;iIndex++)
{
if(g->arcNodes[iIndex][jIndex].adj==1)
{
indegree[jIndex]++;
}
}
}
}
/**********************************************************************************
Function Name:QueueOperation
Function Description: 队列的基本操作
**********************************************************************************/
inline void InitQueue(Queue* queue)
{
queue->head=0;
queue->rear=0;
}
inline bool IsEmpty(Queue* queue)
{
return queue->head%MAXSIZE==queue->rear?true:false;
}
inline void Quit(Queue* queue,int* i)
{
*i=queue->data[queue->head++];
}
inline int Enter(Queue* queue,int value)
{
if(queue->head==((queue->rear+1)%MAXSIZE))
return FALSE;
queue->data[queue->rear++]=value;
return TRUE;
}
/**********************************************************************************
Function Name:ClearZero
Return Type: int
Function Description: 删除以顶点i为起点的弧
**********************************************************************************/
inline void ClearZero(AdjMatrix* g,int iIndex,int indegree[],Queue* queue)
{
int jIndex;
for(jIndex=1;jIndex<=g->vertexNum;jIndex++)
{
if(g->arcNodes[iIndex][jIndex].adj>0)
{
g->arcNodes[iIndex][jIndex].adj=0;
indegree[jIndex]--;
if(indegree[jIndex]==0)
Enter(queue,jIndex);
}
}
}
/**********************************************************************************
Function Name:TopoSort
Return Type: int
Function Description: 拓扑排序
**********************************************************************************/
int TopoSort(AdjMatrix* g)
{
int indegree[MAXSIZE+1]={0},count;
Queue queue;
FindID(g,indegree);
InitQueue(&queue);
int iCount;
for(iCount=1;iCount<=g->vertexNum;iCount++)
{
if(indegree[iCount]==0)
Enter(&queue,iCount);
}
count=0;
while(!IsEmpty(&queue))
{
Quit(&queue,&iCount);
cout<<g->vertexNodes[iCount].vertexData<<" "; //输出顶点并计数
count++;
ClearZero(g,iCount,indegree,&queue); //删除以顶点i为起点的弧
}
cout<<endl;
return count==g->vertexNum?TRUE:FALSE;
}
int main()
{
AdjMatrix *g=(AdjMatrix*)malloc(sizeof(AdjMatrix));
InitAdjMatrix(g);
CreateAdjMatrix(g);
TopoSort(g);
return 0;
}
分享到:
相关推荐
从文本文件中读取邻接矩阵,通过减一治的方法实现拓扑排序
对于有向图进行拓扑排序,图使用邻接矩阵的存储结构。
实现图的拓扑排序,方法1:采用邻接表存储结构,按照堆栈的实现。 实现图的拓扑排序,方法2:采用邻接矩阵实现:
基于ADT实现的图的邻接矩阵,包含了基本的图算法的实现,包括BFS,DFS,拓扑排序,Prim,Kruskal,Dijkstra,Floyd,有注释,有测试样例,检验过没问题。
用邻接矩阵实现的拓扑排序,如果不是DAG,会找出有向图中的一个环(NKU算法作业)
本程序是邻接矩阵,邻接表的利用,共有4项功能,分别是: (1)建立并显示图的邻接表。 (2)以非递归方式进行深度优先遍历,显示遍历结果。 (3)对该图进行拓扑排序,显示排序结果。 (4)给出某一确定顶点到所有其它顶点...
深度优先排序、广度优先排序和一种补充算法
以邻接矩阵给出一张以整数为结点的有向图,其中0表示不是相邻结点,1表示两个结点相连且由当前结点为初始点。利用拓扑排序判断图中是否有环,若有输出YES没有输出NO。 输入: 结点数邻接矩阵 输出: YES/NO
" "二、实验内容和方法 " "(1)实验内容: " "1、编写一个程序algo8-1.cpp,实现不带权图和带权图的邻接矩阵与邻接表的相互转换" "算法、输出邻接矩阵与邻接表的算法,并在此基础上设计一个程序exp8-1.cpp实现如下" ...
邻接矩阵的Dijkstra实现邻接表的拓扑排序算法
数据结构中图的拓扑排序,采用邻接矩阵,没有采用栈的操作
图的几种常用算法(广度/深度优先搜索,最小生成树,弗洛伊德,拓扑排序....邻接矩阵),java实现。 注释清晰,代码简单易懂。
1.定义并实现图的数据结构(注:图可使用邻接表或邻接矩阵表示)。 2.完成校园交通游览图。要求: (1)至少10个地点。(2)从自已宿舍至各个地点的最短路径 (3)校园游览导航图。 注:本实验可两人一组完成之。
图的算法实现 (1)将图的信息建立文件; (2)从文件读入图的信息,建立邻接矩阵和邻接表; (3)实现Prim、Kruskal、Dijkstra和拓扑排序算法。
在具体实现拓扑排序的函数中,根据规则,当某个顶点的入度为0(没有前驱顶点)时, 就将此顶点输出,同时将该顶点的所有后继顶点的入度减1,为了避免重复检测入度为0 的顶点,设立一个栈St,以存放入度为0的顶点。...
拓扑排序 关键路径 各种遍历 邻接表 邻接矩阵
图的相邻矩阵实现,邻接表实现,深度优先周游,广度优先周游,两种拓扑排序,Dijkstra算法, Prim 算法和最小支撑树算法.
若图为有向无环图,则可进行拓扑排序。拓扑排序的结果为DFS后序遍历的倒序。选课是拓扑排序的经典应用场景之一,即:选修一门课程之前须先修完该课程的前置课程。 class Graph(object): def __init__(self, points_...
对于表示有向图的二进制邻接矩阵M,ALLTOPOSORT(M)返回具有所有可能的拓扑排序安排的矩阵。 该函数是 YL Varol 和 D. Rotem 的“生成所有拓扑排序安排的算法”中的算法的实现。
2) 对网进行拓扑排序,输出拓扑序列; 3) 求出网的最小生成树,输出生成树的n-1边及权值之和; (2)题目所选择的数据结构及存储结构; 逻辑结构为网状结构,网的存储结构为邻接矩阵和邻接表的存储结构