面包屑导航的网站,东道设计官网,网页设计素材怎么算侵权,星子县网站建站公司拓扑排序 有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列。
无向图没有拓扑序列。
首先我们先来解释一下什么是有向无环图#xff1a;
有向就是我们两个结点之间的边是有方向的#xff0c;无环的意思就是整个序列中没有几个结点通过边形成一个圆环。
下图就是一个…拓扑排序 有向无环图一定是拓扑序列,有向有环图一定不是拓扑序列。
无向图没有拓扑序列。
首先我们先来解释一下什么是有向无环图
有向就是我们两个结点之间的边是有方向的无环的意思就是整个序列中没有几个结点通过边形成一个圆环。
下图就是一个有向无环图它也一定是拓扑序列。 下图就是有向有环图 总结一下拓扑排序就是只有从前指向后的边没有从后指向前的边。
满足事件的先后顺序类似于哈夫曼树的构建
如果是一个有向无环图那么一定有一个点的入度为0如果找不到一个入度为0的点这个图一定是带环的。
拓扑排序满足每条边(x,y)x在序列中都在y前面。
拓扑排序的思路
一个有向图如果图中有入度为 0 的点就把这个点删掉同时也删掉这个点所连的边。
一直进行上面出处理如果所有点都能被删掉则这个图可以进行拓扑排序。
举例 ABD
首先我们的有向无环图是这样的 我们发现A的入度为0那么A就可以作为源点不会有边在它前面然后删除A和A上所连的边如下图
然后我们发现B和C的入度都是0那么同样删除BC和BC上所连的边如下图 然后D的入度为0我们同样操作最后图被删除干净证明可以拓扑排序。 解题思路
首先记录各个点的入度
然后将入度为 0 的点放入队列
将队列里的点依次出队列然后找出所有出队列这个点发出的边删除边同时边的另一侧的点的入度 -1。
如果所有点都进过队列则可以拓扑排序输出所有顶点。否则输出-1代表不可以进行拓扑排序。
其他操作
计算入度 拓扑排序模板 在初始化的FOR循环中先遍历所有点然后在WHILE中遍历所有边
bool topsort()
{int hh 0, tt -1;// d[i] 存储点i的入度for (int i 1; i n; i)if (!d[i])q[tt] i;//先遍历d数组然后把初始的d数组中所有入度为0的元素都加入到队列当中I就是节点的编号while (hh tt){int t q[hh];//队列头节点//H数组记录对应节点的第一条出边Ne数组记录每条边的下一个索引//h记录的是for (int i h[t]; i ! -1; i ne[i]){int j e[i];if (--d[j] 0)//先--再判断是否为0q[tt] j;}}// 如果所有点都入队了说明存在拓扑序列否则不存在拓扑序列。return tt n - 1;//tt从-1开始有n个节点时最终停在n-1
}
//d数组记录的是目前每个节点的入度
//q数组记录的是待处理节点的编号是源点
//h数组记录的是以下标为起点编号的第一条边
//ne数组记录的是同一起点下每条出边所指向的下一条出边它的下标标号就是边的标号
//e数组记录的是i边所指向的终点下标为边的编号记录的是边的终点
时间复杂度
该代码的时间复杂度是O(VE)其中V表示节点的数量E表示边的数量。
在代码的第一个for循环中遍历了所有的节点所以时间复杂度是O(V)。
在代码的while循环中每个节点的邻接链表中的每个边都会被访问一次。由于每个边会被访问一次且仅一次所以总的边数是O(E)。因此while循环的时间复杂度是O(E)。
综上所述整个代码的时间复杂度是O(VE)。这是因为该算法的主要操作是遍历节点和边每个节点和每条边都只会被处理一次。所以时间复杂度与节点数和边数成正比。
这样的复杂度意味着遍历所有的点和所有的边
#includeiostream
#includecstring
#includealgorithm
using namespace std;
const int N1e510;
int h[N],e[N],ne[N],idx; //邻接表存储图
int n,m; //n个点m个边
int q[N],d[N];//q表示队列,d表示点的入度
void add(int a,int b)
{e[idx]b;ne[idx]h[a];h[a]idx;
}
bool topsort()
{int hh0,tt-1;for(int i1;in;i){if(!d[i])//如果i这个点的入度为0那么我们就入队q[tt]i;}while(hhtt) //如果队列不为空{int tq[hh];//用t来接收队头的元素同时队头指针hhfor(int ih[t];i!-1;ine[i])//我们来从t结点开始遍历它的边{int je[i];//t有一条边指向jd[j]--;//删除掉t指向j的这条边j的入度-1if(d[j]0) //如果j的入度为0那么我们就将j入队q[tt]j;}}return ttn-1;//表示如果n个点都入队了话,那么该图为拓扑图,返回true,否则返回false//我们的tt初始值是-1当插入一个值的时候tt先在插入所以我们一个有n个结点全部入队的话tt指针应该是n-1
}
int main()
{cinnm;//保存点的个数和边的个数memset(h,-1,sizeof(h));//初始化邻接表for(int i0;im;i)//我们一共有m个边所以我们循环插入边{int a,b;scanf(%d%d,a,b);add(a,b);d[b];//插入的边是由a指向b的所以b的入度}if(topsort()){for(int i0;in;i) printf(%d ,q[i]);puts();}elseputs(-1);return 0;}例题 拓扑排序的特点是根节点比孩子节点先访问。ACD若采用后续遍历即只要反转一次即可
