| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 665 人关注过本帖
标题:拓扑排序之变量序列
只看楼主 加入收藏
巧若拙
Rank: 4
来 自:宁波余姚
等 级:业余侠客
威 望:1
帖 子:159
专家分:273
注 册:2014-8-24
结帖率:46.15%
收藏
 问题点数:0 回复次数:0 
拓扑排序之变量序列
拓扑排序之变量序列
巧若拙(欢迎转载,但请注明出处:http://blog.

题目描述:
假设有n个变量(1<=n<=26,变量名用单个小写字母表示),还有m个二元组(u,v),分别表示变量u小于v。那么,所有变量从小到大排列起来应该是什么样子的呢?
    例如有4个变量a,b,c,d,若以知a<b,c<b,d<c,则这4个变量的排序可能是a<d<c<b。尽管还有可能其他的可能,你只需找出其中的一个即可。
输入:
输入为一个字符串,其中包含N+N个字符,依次表示N个关系式(1<=N<=100000),例如序列"abcbdc"表示a<b,c<b,d<c.
输出:
给出一个字符串,其中存储了一个符合要求的变量序列,例如,字符串"adcb"表示a<d<c<b。
   
算法分析:
    这是典型的拓扑排序问题。先简单科普一下,所谓拓扑排序,是指将一个有向无环图G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若<u,v> ∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列,简称拓扑序列。
    我们先将变量作为顶点输入到图数据结构中。表示图的数据结构有多种,由于本题对应的是稀疏图,应该以边为主要研究对象,所以可以把数据结构设置为邻接表或边表集。
    我们先来看邻接表数据结构:
typedef char VertexType; //顶点类型由用户自定义
typedef int EdgeType; //边上的权值类型由用户自定义

typedef struct EdgeNode{ //边表结点
    int adjvex;  //邻接点域,存储该顶点对应的下标
//    EdgeType weight; //权值,对于非网图可以不需要
    struct EdgeNode *next; //链域,指向下一个邻接点
} EdgeNode;

typedef struct VertexNode{ //顶点表结点
    VertexType data; //顶点域,存储顶点信息
    int in;   //存储顶点入度的数量
    EdgeNode *firstEdge; //边表头指针
} VertexNode;

由于变量名用单个小写字母表示,我们可以设置一个大小为26的数组存储顶点;又由于26个字母不见得都会出现,故我们设置一个全局变量int book[MAXM] = {0}; 用来标记某字母是否出现。
首先创建一个图,读入顶点和边信息。代码如下:
/*
函数名称:CreateGraph
函数功能:把顶点和边信息读入到表示图的邻接表中
输入变量:char *data:存储了N个关系式的字符串
          VertexNode *GL : 顶点表数组
输出变量:表示图的顶点表数组
返回值:int :顶点数量
*/
int CreateGraph(char *data, VertexNode *GL)
{
    int i, u, v;
    int count = 0;//记录顶点数量
    EdgeNode *e;
   
    for (i=0; i<MAXM; i++)//初始化图
    {
        GL[i].data = i + 'a';
        GL[i].in = 0;
        GL[i].firstEdge = NULL;
        book[i] = 0;
    }
   
    for (i=0; data[i]!='\0'; i+=2)//每次读取两个变量  
    {
        u = data[i] - 'a'; //字母转换为数字,'a'对应0,'b'对应1,以此类推
        v = data[i+1] - 'a';
        book[u] = book[v] = 1;
        
        e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点
        if (!e)
        {
            puts("Error");
            exit(1);
        }
        e->adjvex = v;
        e->next = GL[u].firstEdge;
        GL[u].firstEdge = e;
        
        GL[v].in++;
    }
   
    for (i=0; i<MAXM; i++)//计算顶点数量
    {
        if (book[i] != 0)
            count++;
    }
   
    return count;
}

拓扑排序算法其实非常简单,只需要搜索入度为0的弧尾顶点,然后将其对应的弧头顶点入度减1,如果该弧头顶点入度也变成了0,就将其存储到栈(或队列)中。搜索的方法有深度优先和广度优先两种。代码分别如下:
/*
函数名称:TopoLogicalSort_DFS
函数功能:拓扑排序,采用深度优先搜索获取拓扑序列
输入变量:char *topo:用来存储拓扑序列的字符串
          VertexNode *GL : 顶点表数组
          int n:顶点个数
输出变量:用来存储拓扑序列的字符串
返回值:int :拓扑排序成功返回真,若存在环则返回假
*/
int TopoLogicalSort_DFS(char *topo, VertexNode *GL, int n)
{
    int i, u, v, top;
    int count = 0; //用于统计输出顶点的个数
    EdgeNode *e;
    int Stack[MAXM];
   
    for (top=i=0; i<MAXM; i++)//将入度为0的顶点入栈
    {
        if (book[i] != 0 && GL[i].in == 0)
        {
            Stack[top++] = i;
        }
    }
   
    while (top > 0)//采用深度优先搜索获取拓扑序列
    {
        u = Stack[--top];
        topo[count++] = u + 'a';
        
        for (e=GL[u].firstEdge; e!=NULL; e=e->next)//将u的邻接点入度减1,并将入度为0的顶点入栈
        {
            v = e->adjvex;
            if (--GL[v].in == 0)
                Stack[top++] = v;
        }
    }
    topo[count] = '\0';
   
    return (count == n);//如果count小于顶点数,说明存在环
}

/*
函数名称:TopoLogicalSort_BFS
函数功能:拓扑排序,采用广度优先搜索获取拓扑序列
输入变量:char *topo:用来存储拓扑序列的字符串
          VertexNode *GL : 顶点表数组
          int n:顶点个数
输出变量:用来存储拓扑序列的字符串
返回值:int :拓扑排序成功返回真,若存在环则返回假
*/
int TopoLogicalSort_BFS(char *topo, VertexNode *GL, int n)
{
    int i, u, v, front, rear;
    EdgeNode *e;
   
    front = rear = 0;
    for (i=0; i<MAXM; i++)//将入度为0的顶点入栈
    {
        if (book[i] != 0 && GL[i].in == 0)
        {
            topo[rear++] = i + 'a';
        }
    }
   
    while (front < rear)//采用广度优先搜索获取拓扑序列
    {
        u = topo[front++] - 'a';
        
        for (e=GL[u].firstEdge; e!=NULL; e=e->next)//将u的邻接点入度减1,并将入度为0的顶点入栈
        {
            v = e->adjvex;
            if (--GL[v].in == 0)
                topo[rear++] = v + 'a';
        }
    }
    topo[rear] = '\0';
   
    return (rear == n);//如果count小于顶点数,说明存在环
}

我们也可以用边表集来表示图,数据结构如下:
typedef struct Edge{ //边集数组
    int u, v; //弧尾和弧头
    int next; //指向同一个弧尾的下一条边
//    EdgeType weight; //权值,对于非网图可以不需要
} EdgeLib;

为了表示顶点信息,我们还需要设置两个数组:int In[MAXM], first[MAXM]; //分别存储顶点的入度和第一条边信息。
边表集实现拓扑排序的算法和邻接表非常相似,也是先读入图的顶点和边信息,然后进行拓扑排序。代码如下:
/*
函数名称:CreateGraph_2
函数功能:把顶点和边信息读入到表示图的边表集中
输入变量:char *data:存储了N个关系式的字符串
          int In[]:存储了顶点的入度信息
          int first[]:指向以该顶点为弧尾的第一条边
          EdgeLib edge[]:存储了边信息的边表集
输出变量:表示图的边表集数组
返回值:int :顶点数量
*/
int CreateGraph_2(char *data, int In[], int first[], EdgeLib edge[])//创建一个图
{
    int i, j;
    int count = 0;//记录顶点数量
   
    for (i=0; i<MAXM; i++)//初始化图
    {
        first[i] = -1;
        book[i] = 0;
        In[i] = 0;
    }
   
    for (j=i=0; data[i]!='\0'; i+=2,j++)//每次读取两个变量  
    {
        edge[j].u = data[i] - 'a'; //字母转换为数字,'a'对应0,'b'对应1,以此类推
        edge[j].v = data[i+1] - 'a';
        book[edge[j].u] = book[edge[j].v] = 1;
        
        edge[j].next = first[edge[j].u];
        first[edge[j].u] = j;
        In[edge[j].v]++;
    }
   
    for (i=0; i<MAXM; i++)//计算顶点数量
    {
        if (book[i] != 0)
            count++;
    }
   
    return count;
}

/*
函数名称:TopoLogicalSort
函数功能:拓扑排序,采用广度优先搜索获取拓扑序列
输入变量:char *topo:用来存储拓扑序列的字符串
          EdgeLib edge[]:存储了边信息的边表集
          int In[]:存储了顶点的入度信息
          int first[]:指向以该顶点为弧尾的第一条边
          int n:顶点个数
输出变量:用来存储拓扑序列的字符串
返回值:int :拓扑排序成功返回真,若存在环则返回假
*/
int TopoLogicalSort(char *topo, EdgeLib edge[], int In[], int first[], int n)
{
    int i, u, front, rear;
   
    front = rear = 0;
    for (i=0; i<MAXM; i++)//将入度为0的顶点入栈
    {
        if (book[i] != 0 && In[i] == 0)
        {
            topo[rear++] = i + 'a';
        }
    }
   
    while (front < rear)//采用广度优先搜索获取拓扑序列
    {
        u = topo[front++] - 'a';
        for (i=first[u]; i!=-1; i=edge[i].next)
        {
            if (--In[edge[i].v] == 0)
                topo[rear++] = edge[i].v + 'a';
        }
    }
    topo[rear] = '\0';
   
    return (rear == n);//如果count小于顶点数,说明存在环
}

这里只给出了相关函数,完整的测试代码请到巧若拙的博客(http://blog.)查看。
搜索更多相关主题的帖子: 字母表 字符串 
2014-11-17 20:59
快速回复:拓扑排序之变量序列
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.019975 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved