图论之拓扑排序基础
也可以定义为:拓扑排序是对有向无环图的顶点的一种排序,它使得如果存在一条从顶点A到顶点B的路径,那么在排序中B出现在A的后面。
是不是觉得看完概念还是很晕的感觉,下面就用一个实例来讲具体的拓扑排序样例。
(a)有向图网(AOV) (b)输出v6后 (c)输出v1后 (d)输出v4后 (e)输出v3后 (f)输出v2后
输出排序结果:v6-v1-v4-v3-v2-v5
有向图存储:
此拓扑排序的思想是:
(1)从有向图中选取一个没有前驱的顶点,并输出之;
(2)从有向图中删去此顶点以及所有以它为尾的弧;
重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。没有前驱 -- 入度为零,删除顶点及以它为尾的弧-- 弧头顶点的入度减1。
何谓入度?
我觉得得先明白什么是度?度(Degree):一个顶点的度是指与该顶点相关联的边的条数,顶点v的度记作d(v)。
入度:对于有向图来说,一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中,以其为终点的边数。
出度:出度则是相对的概念,指以该顶点为起点的边数。
以v6这个顶点为例,它的入度为0,出度为2。
以v5这个顶点为例,它的入度为3,出度为0。
以v4这个顶点为例,它的入度为2,出度为1。
以v3这个顶点为例,它的入度为1,出度为2。
以v2这个顶点为例,它的入度为2,出度为0。
以v1这个顶点为例,它的入度为0,出度为3。
经验证,一个有向五环图中所有顶点的入度之和(0+3+2+1+2+0=8)等于所有顶点的出度之和(2+0+1+2+0+3=8)。
有先后,比如在实际生活中的选课问题,比如大一时一定要修完这门课,大二才学第二门课,这种排课问题就是拓扑排序问题。
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<memory.h>
using namespace std;
#define MAX 9999
stack<int>mystack;
int indegree[MAX];
struct node
{
int adjvex;
node* next;
}adj[MAX];
int Create(node adj[],int n,int m)//邻接表建表函数,n代表定点数,m代表边数
{
int i;
node *p;
for(i=1;i<=n;i++)
{
adj[i].adjvex=i;
adj[i].next=NULL;
}
for(i=1;i<=m;i++)
{
cout<<"请输入第"<<i<<"条边:";
int u,v;
cin>>u>>v;
p=new node;
p->adjvex=v;
p->next=adj[u].next;
adj[u].next=p;
}
return 1;
}
void print(int n)//邻接表打印函数
{
int i;
node *p;
for(i=1;i<=n;i++)
{
p=&adj[i];
while(p!=NULL)
{
cout<<p->adjvex<<' ';
p=p->next;
}
cout<<endl;
}
}
void topsort(node adj[],int n)
{
int i;
node *p;
memset(indegree,0,sizeof(indegree));
for(i=1;i<=n;i++)
{
p=adj[i].next;
while(p!=NULL)
{
indegree[p->adjvex]++;
p=p->next;
}
}
for(i=1;i<=n;i++)
{
if(indegree[i]==0)
mystack.push(i);
}
int count=0;
while(mystack.size()!=0)
{
i=mystack.top();
mystack.pop();
cout<<i<<' ';
count++;
for(p=adj[i].next;p!=NULL;p=p->next)
{
int k=p->adjvex;
indegree[k]--;
if(indegree[k]==0)
mystack.push(k);
}
}
cout<<endl;
if(count<n)cout<<"有回路"<<endl;
}
int main()
{
int n;
int m;
cout<<"请输入顶点数及边数:";
cin>>n>>m;
Create(adj,n,m);
cout<<"输入的邻接表为:"<<endl;
print(n);
cout<<"拓扑排序结果为:"<<endl;
topsort(adj,n);
system("pause");
return 0;
}