拓扑排序之变量序列代码
Name:?
Copyright:?
Author:?
Date: 17-11-14 21:02
Description: 拓?fù)渑判蛑兞啃蛄?
如果有n個(gè)變量（1<=n<=26，變量名用單個(gè)小寫字母表示）。還有m個(gè)二元組（u,v），分別表示變量u小于v。
那么，全部變量從小到大排列起來應(yīng)該是什么樣子的呢？
比如有4個(gè)變量a,b,c,d，若以知a<b,c<b,d<c，則這4個(gè)變量的排序可能是a<d<c<b。
雖然還有可能其它的可能，你僅僅需找出當(dāng)中的一個(gè)就可以。
Input
輸入為一個(gè)字符串data，當(dāng)中包括N+N個(gè)字符。表示N個(gè)關(guān)系式（1<=N<=100000），比如序列"abcbdc"表示a<b,c<b,d<c.
Output
給出一個(gè)字符串，當(dāng)中存儲(chǔ)了一個(gè)符合要求的變量序列，比如，字符串"adcb"表示a<d<c<b。?
*/
#include<stdio.h>
#include<stdlib.h>
#define true 1 ?
#define false 0
#define MAXM 26 ? //最大變量（頂點(diǎn)）數(shù)量?
#define MAXN 100000 ? //最大關(guān)系式數(shù)量?
typedef char VertexType; //頂點(diǎn)類型由用戶自己定義
typedef int EdgeType; //邊上的權(quán)值類型由用戶自己定義
typedef struct EdgeNode{ //邊表結(jié)點(diǎn)
int adjvex; ?//鄰接點(diǎn)域，存儲(chǔ)該頂點(diǎn)相應(yīng)的下標(biāo)
// EdgeType weight; //權(quán)值。對(duì)于非網(wǎng)圖能夠不須要?
struct EdgeNode *next; //鏈域，指向下一個(gè)鄰接點(diǎn)?
} EdgeNode;
typedef struct VertexNode{ //頂點(diǎn)表結(jié)點(diǎn)
VertexType data; //頂點(diǎn)域，存儲(chǔ)頂點(diǎn)信息
int in; ? //存儲(chǔ)頂點(diǎn)入度的數(shù)量?
EdgeNode *firstEdge; //邊表頭指針
} VertexNode;
typedef struct Edge{ //邊集數(shù)組?
int u, v; //弧尾和弧頭?
int next; //指向同一個(gè)弧尾的下一條邊?
// EdgeType weight; //權(quán)值，對(duì)于非網(wǎng)圖能夠不須要?
} EdgeLib;
int book[MAXM] = {0}; //標(biāo)記某字母是否出現(xiàn)?
int IsTopoSeq(char *data, char *topo);//依據(jù)關(guān)系列表data，推斷topo字符串是否為拓?fù)湫蛄?
int CreateGraph(char *data, VertexNode *GL);//創(chuàng)建一個(gè)圖
void PrintGraph(VertexNode *GL);//輸出圖
int TopoLogicalSort_DFS(char *topo, VertexNode *GL, int n);//拓?fù)渑判?#xff0c;獲取拓?fù)湫蛄?#xff0c;若存在環(huán)則返回假?
int TopoLogicalSort_BFS(char *topo, VertexNode *GL, int n);//拓?fù)渑判?#xff0c;獲取拓?fù)湫蛄小Ｈ舸嬖诃h(huán)則返回假?
int CreateGraph_2(char *data, int In[], int first[], EdgeLib edge[]);//創(chuàng)建一個(gè)圖
void PrintGraph_2(int first[], EdgeLib edge[]);//輸出圖
int TopoLogicalSort(char *topo, EdgeLib edge[], int In[], int first[], int n);//拓?fù)渑判颉＋@取拓?fù)湫蛄?#xff0c;若存在環(huán)則返回假，使用隊(duì)列存儲(chǔ)拓?fù)湫蛄?
int main()
{
int i, n;
VertexNode GL[MAXM];
char topo[MAXM+1];
char data[MAXN+MAXN+1];
int In[MAXM], first[MAXM]; //存儲(chǔ)頂點(diǎn)信息
EdgeLib edge[MAXN]; //存儲(chǔ)邊信息?
gets(data);?
n = CreateGraph_2(data, In, first, edge);//創(chuàng)建一個(gè)圖
PrintGraph_2(first, edge);//輸出圖
if (TopoLogicalSort(topo, edge, In, first, n))//採用拓?fù)渑判驑?gòu)造拓?fù)湫蛄?
puts(topo);
else
puts("不存在滿足條件的序列");?
if (IsTopoSeq(data, topo))//依據(jù)關(guān)系列表data。推斷topo字符串是否為拓?fù)湫蛄?
puts(topo);
else
puts("不存在滿足條件的序列");
gets(data);?
n = CreateGraph(data, GL);//創(chuàng)建一個(gè)圖
PrintGraph(GL);//輸出圖
if (IsTopoSeq(data, topo))//依據(jù)關(guān)系列表data，推斷topo字符串是否為拓?fù)湫蛄?
puts(topo);
else
puts("不存在滿足條件的序列");
if (TopoLogicalSort_BFS(topo, GL, n))//採用拓?fù)渑判驑?gòu)造拓?fù)湫蛄?
puts(topo);
else
puts("不存在滿足條件的序列");?
gets(data);?
n = CreateGraph(data, GL);//創(chuàng)建一個(gè)圖
PrintGraph(GL);//輸出圖
if (TopoLogicalSort_DFS(topo, GL, n))//採用拓?fù)渑判驑?gòu)造拓?fù)湫蛄?
puts(topo);
else
puts("不存在滿足條件的序列");?
if (IsTopoSeq(data, topo))//依據(jù)關(guān)系列表data，推斷topo字符串是否為拓?fù)湫蛄?
puts(topo);
else
puts("不存在滿足條件的序列");
? ? return 0;
}
/*
函數(shù)名稱：CreateGraph
函數(shù)功能：把頂點(diǎn)和邊信息讀入到表示圖的鄰接表中?
輸入變量：char *data：存儲(chǔ)了N個(gè)關(guān)系式的字符串?
? ? ? ? ? VertexNode *GL ： 頂點(diǎn)表數(shù)組?
輸出變量：表示圖的頂點(diǎn)表數(shù)組?
返回值：int ：頂點(diǎn)數(shù)量?
*/?
int CreateGraph(char *data, VertexNode *GL)
{
int i, u, v;
int count = 0;//記錄頂點(diǎn)數(shù)量?
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)//每次讀取兩個(gè)變量 ?
{
u = data[i] - 'a'; //字母轉(zhuǎn)換為數(shù)字，'a'相應(yīng)0，'b'相應(yīng)1。以此類推?
v = data[i+1] - 'a';
book[u] = book[v] = 1;
e = (EdgeNode*)malloc(sizeof(EdgeNode)); //採用頭插法插入邊表結(jié)點(diǎn)?
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++)//計(jì)算頂點(diǎn)數(shù)量?
{
if (book[i] != 0)
count++;
}
return count;
}?
void PrintGraph(VertexNode *GL)//輸出圖
{
int u, v;
EdgeNode *e;
for (u=0; u<MAXM; u++)
{
printf("G[%d] = %c: ", u, GL[u].data);
for (e=GL[u].firstEdge; e!=NULL; e=e->next)//將u的鄰接點(diǎn)入度減1。并將入度為0的頂點(diǎn)入棧?
{
v = e->adjvex;
printf("<%c, %c>, ", GL[u].data, GL[v].data);
}
printf("\n");
}
printf("\n");
}?
/*
函數(shù)名稱：TopoLogicalSort_DFS
函數(shù)功能：拓?fù)渑判?#xff0c;採用深度優(yōu)先搜索獲取拓?fù)湫蛄?br /> 輸入變量：char *topo：用來存儲(chǔ)拓?fù)湫蛄械淖址?
? ? ? ? ? VertexNode *GL ： 頂點(diǎn)表數(shù)組?
? ? ? ? ? int n：頂點(diǎn)個(gè)數(shù)?
輸出變量：用來存儲(chǔ)拓?fù)湫蛄械淖址?br /> 返回值：int ：拓?fù)渑判虺晒Ψ祷卣?#xff0c;若存在環(huán)則返回假
*/?
int TopoLogicalSort_DFS(char *topo, VertexNode *GL, int n)
{
int i, u, v, top;
int count = 0; //用于統(tǒng)計(jì)輸出頂點(diǎn)的個(gè)數(shù)?
EdgeNode *e;
int Stack[MAXM];
for (top=i=0; i<MAXM; i++)//將入度為0的頂點(diǎn)入棧?
{
if (book[i] != 0 && GL[i].in == 0)
{
Stack[top++] = i;
}
}
while (top > 0)//採用深度優(yōu)先搜索獲取拓?fù)湫蛄?
{
u = Stack[--top];
topo[count++] = u + 'a';
for (e=GL[u].firstEdge; e!=NULL; e=e->next)//將u的鄰接點(diǎn)入度減1，并將入度為0的頂點(diǎn)入棧?
{
v = e->adjvex;
if (--GL[v].in == 0)
Stack[top++] = v;
}
}
topo[count] = '\0';
return (count == n);//假設(shè)count小于頂點(diǎn)數(shù)，說明存在環(huán)?
}
/*
函數(shù)名稱：TopoLogicalSort_BFS
函數(shù)功能：拓?fù)渑判?#xff0c;採用廣度優(yōu)先搜索獲取拓?fù)湫蛄?br /> 輸入變量：char *topo：用來存儲(chǔ)拓?fù)湫蛄械淖址?
? ? ? ? ? VertexNode *GL ： 頂點(diǎn)表數(shù)組?
? ? ? ? ? int n：頂點(diǎn)個(gè)數(shù)?
輸出變量：用來存儲(chǔ)拓?fù)湫蛄械淖址?br /> 返回值：int ：拓?fù)渑判虺晒Ψ祷卣妗Ｈ舸嬖诃h(huán)則返回假
*/?
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的頂點(diǎn)入棧?
{
if (book[i] != 0 && GL[i].in == 0)
{
topo[rear++] = i + 'a';
}
}
while (front < rear)//採用廣度優(yōu)先搜索獲取拓?fù)湫蛄?
{
u = topo[front++] - 'a';
for (e=GL[u].firstEdge; e!=NULL; e=e->next)//將u的鄰接點(diǎn)入度減1。并將入度為0的頂點(diǎn)入棧?
{
v = e->adjvex;
if (--GL[v].in == 0)
topo[rear++] = v + 'a';
}
}
topo[rear] = '\0';
return (rear == n);//假設(shè)count小于頂點(diǎn)數(shù)，說明存在環(huán)?
}
/*
函數(shù)名稱：CreateGraph_2
函數(shù)功能：把頂點(diǎn)和邊信息讀入到表示圖的邊表集中?
輸入變量：char *data：存儲(chǔ)了N個(gè)關(guān)系式的字符串?
? ? ? ? ? int In[]：存儲(chǔ)了頂點(diǎn)的入度信息?
? ? ? ? ? int first[]：指向以該頂點(diǎn)為弧尾的第一條邊?
? ? ? ? ? EdgeLib edge[]：存儲(chǔ)了邊信息的邊表集?
輸出變量：表示圖的邊表集數(shù)組?
返回值：int ：頂點(diǎn)數(shù)量?
*/?
int CreateGraph_2(char *data, int In[], int first[], EdgeLib edge[])//創(chuàng)建一個(gè)圖
{
int i, j;
int count = 0;//記錄頂點(diǎn)數(shù)量?
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++)//每次讀取兩個(gè)變量 ?
{
edge[j].u = data[i] - 'a'; //字母轉(zhuǎn)換為數(shù)字，'a'相應(yīng)0，'b'相應(yīng)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++)//計(jì)算頂點(diǎn)數(shù)量?
{
if (book[i] != 0)
count++;
}
return count;
}?
void PrintGraph_2(int first[], EdgeLib edge[])//輸出圖
{
int i, j;
for (i=0; i<MAXM; i++)
{
printf("G[%d] = %c: ", i, i+'a');
j = first[i]; //指向i的第一條邊?
while (j != -1)
{
printf("<%c, %c>, ", edge[j].u+'a', edge[j].v+'a');
j = edge[j].next; //指向下一條邊?
}
printf("\n");
}
printf("\n");
}?
/*
函數(shù)名稱：TopoLogicalSort
函數(shù)功能：拓?fù)渑判颉裼脧V度優(yōu)先搜索獲取拓?fù)湫蛄?br /> 輸入變量：char *topo：用來存儲(chǔ)拓?fù)湫蛄械淖址?
? ? ? ? ? EdgeLib edge[]：存儲(chǔ)了邊信息的邊表集?
? ? ? ? ? int In[]：存儲(chǔ)了頂點(diǎn)的入度信息?
? ? ? ? ? int first[]：指向以該頂點(diǎn)為弧尾的第一條邊?
? ? ? ? ? int n：頂點(diǎn)個(gè)數(shù)?
輸出變量：用來存儲(chǔ)拓?fù)湫蛄械淖址?br /> 返回值：int ：拓?fù)渑判虺晒Ψ祷卣妗Ｈ舸嬖诃h(huán)則返回假
*/?
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的頂點(diǎn)入棧?
{
if (book[i] != 0 && In[i] == 0)
{
topo[rear++] = i + 'a';
}
}
while (front < rear)//採用廣度優(yōu)先搜索獲取拓?fù)湫蛄?
{
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);//假設(shè)count小于頂點(diǎn)數(shù)。說明存在環(huán)?
}
int IsTopoSeq(char *data, char *topo)//依據(jù)關(guān)系列表data。推斷topo字符串是否為拓?fù)湫蛄?
{
int pos[MAXM] = {0};
int i;
for (i=0; topo[i]!='\0'; i++)//讀取變量下標(biāo)
pos[topo[i]-'a'] = i;
for (i=0; data[i]!='\0'; i+=2)//每次讀取兩個(gè)變量 ?
{
if (pos[data[i]-'a'] > pos[data[i+1]-'a'])
return false;
}
return true;
}
轉(zhuǎn)載于:https://www.cnblogs.com/liguangsunls/p/7257150.html
總結(jié)
以上是生活随笔為你收集整理的拓扑排序之变量序列代码的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 物联网网络编程和web编程
- 下一篇： bzoj4196:[Noi2015]软件