v = e->adjvex;
printf("<%c, %c>, ", GL[u].data, GL[v].data);
}
printf("\n");
}
printf("\n");
}
/*
函数名称：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
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
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小于顶点数，说明存在环
}
/*
函数名称：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;
for (i=0; 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
if (book[i] != 0)
count++;
}
return count;
}
void PrintGraph_2(int first[], EdgeLib edge[])//输出图
{
int i, j;
for (i=0; 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");
}
/*
函数名称：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
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小于顶点数，说明存在环
}
int IsTopoSeq(char *data, char *topo)//根据关系列表data，判断topo字符串是否为拓扑序列
{
int pos[MAXM] = {0};
int i;
for (i=0; topo[i]!='\0'; i++)//读取变量下标
pos[topo[i]-'a'] = i;
for (i=0; data[i]!='\0'; i+=2)//每次读取两个变量
{
if (pos[data[i]-'a'] > pos[data[i+1]-'a'])
return false;
}
return true;
}