首页 / 更多教程 / 6-13知识点：数据结构——图
6-13知识点：数据结构——图
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了6-13知识点：数据结构——图，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4747字，纯文字阅读大概需要7分钟。
内容图文
拓扑排序
一.基础知识
1.AOV网（用顶点表示活动的网）
（Activity On Vertex NetWork）
用DAG图（有向无环图）表示?个工程，顶点表示活动，有向边<Vi, Vj>表示活动Vi必须先于活动Vj进行
因此：AOV网一定是有向无环图
如：番茄炒蛋的AOV网
2.拓扑排序
把顶点排成一排，且必须满足以下条件
（1） 每个顶点出现且只出现一次
（2）AOV网中A→B，表示拓扑排序中A排在B之前
这种序列成为原图的一个拓扑排序
注：
（1）有向无环图才有拓扑排序
（2）拓扑排序结果可能不唯一
二.拓扑排序的构建
首先，准备厨具和买菜任选一
如果选择准备厨具
下一个必定选买菜
然后打鸡蛋、洗番茄任选一。如果选择洗番茄
切番茄、打鸡蛋任选一。如果选择切番茄
再依次选择打鸡蛋、下锅炒、吃。完成
描述总结：
①从AOV网中选择一个没有前驱（入度为0）的顶点并输出
②从网中删除该顶点和所有以它为起点的有向边
③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止（存在回路）
如：当前所有顶点的入度>0
三.算法实现
indegree[]：当前顶点入度
print[]：记录拓扑序列
栈S：保存度为0的顶点（也可用队列、数组）
在此图中，indegree[]={0,1,0,2,2}
print[]={-1,-1,-1,-1,-1}
开始
for (int i = 0; i < G.vexnum; i++)
if (indegree[i] == 0)
push(S, i);//将所有入度为0的顶点进栈
此时0、2入栈
int count = 0;//计数，记录当前已经输出的顶点数
while (!IsEmpty(S))
{
Pop(S, i);//栈S中弹出2，剩0
print[count++] = i;//输出顶点i=2
}
回顾：print[]：记录拓扑序列
2出栈，此时count=0，指向0号位的2
print[count++]表示先print[count]（记录2为拓扑序列），再count++（count指向下一个，如图）
然后
通过邻接矩阵，找到2指向的结点（3和4），把这些弧去掉
目的：将所有i=2指向的顶点的入度-1，并且将入度为0的顶点压入栈S
ArcNode* firstarc;//指向第一条依附于该顶点的弧的指针，即2→3的弧
struct ArcNode* nextarc;//指向下一条弧的指针，即2→4的弧
int adjvex;//该弧所指向的顶点位置，即3
当前i=2
for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
//第一次p=第一条依附于2的弧的指针：2→3的箭头
//第一次p=指向下一条弧的指针：2→4的箭头
v = p->adjvex;
//第一次v=该弧所指向的顶点位置,即v=3
//第二次v=该弧所指向的顶点位置,即v=4
if (!(--indegree[v]))
push(S, v);//若该节点入度为0，则入栈
//原来顶点3和顶点4的入读均为2，-1均为1，不入栈
}
if (!(–indegree[v]))相当于if (!(indegree[v]))和–indegree[v]
即：如果顶点3的入度不为0，则顶点3的入度-1
同样第二次：如果顶点4的入度不为0，则顶点4的入度-1
（因为从网中删除顶点2和所有以它为起点的有向边）
更新indegree数组
然后
while (!IsEmpty(S))
{
Pop(S, i);
print[count++] = i;//输出顶点i
}
弹出0，0入print，count向后
此时栈空
for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
//将所有i指向的顶点的入度-1，并且将入度为0的顶点压入栈S
v = p->adjvex;
if (!(--indegree[v]))
push(S, v);//入度为0，则入栈
}
}
G.vertices[i].firstarc->adjvex找到1
1的入度为1≠0，入度-1，此时1的入度为0，压入栈
继续
1出栈，加入print，count++
找到3，入度-1＝0，3入栈
3出栈，加入print，count++
找到4，入度-1=0，4入栈
while (!IsEmpty(S))
{
Pop(S, i);//4出栈
print[count++] = i;//4加入print，count变为5
for (p = G.vertices[i].firstarc; p; p = p->nextarc)
{
v = p->adjvex;
if (!(--indegree[v]))
push(S, v);
}//跳过
}//while结束
if (count < G.vexnum)
return false;//排序失败，有向图中有回路
else
return true;//count=5=顶点数，成功
结果
最终代码
#define MaxVertexNum 100//图中顶点数目的最大值
typedef struct ArcNode {//边表结点
int adjvex;//该弧所指向的顶点位置
struct ArcNode* nextarc;//指向下一条弧的指针
//InfoType info;//边的权值
}ArcNode;
typedef struct VNode {//顶点表结点
VertexType data;//顶点信息
ArcNode* firstarc;//指向第一条依附于该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct {
AdjList vertices;//邻接表
int vexnum, arcnum;//图的顶点数和弧数
}Graph;//Graph是以邻接表存储图类型
bool TopologicalSort(Graph G) {
InitStack(S);//初始化栈，存储入度为0的顶点
for (int i = 0; i < G.vexnum; i++)
if (indegree[i] == 0)
push(S, i);//将所有入度为0的顶点进栈
int count = 0;//计数，记录当前已经输出的顶点数
while (!IsEmpty(S))
{
Pop(S, i);
print[count++] = i;//输出顶点i
for (p = G.vertices[i].firstarc; p; p = p->nextarc) {
//将所有i指向的顶点的入度-1，并且将入度为0的顶点压入栈S
v = p->adjvex;
if (!(--indegree[v]))
push(S, v);//入度为0，则入栈
}
}
if (count < G.vexnum)
return false;//排序失败，有向图中有回路
else
return true;//拓扑排序成功
}
四.时间复杂度
在代码中，每个顶点都需要处理一次，每条边也都需要处理一次，因此对于邻接表的时间复杂度为O(|V|+|E|)
另：邻接矩阵：O(|V|2)
五.逆拓扑排序
改变：从AOV网中选择一个没有后继（出度为0）的顶点并输出
完成
六.逆拓扑排序的实现（DFS算法）
（详情DFS）
第一次走到底，依次访问0134，print4
继续执行3，print3
继续执行1，print1
继续执行0，print0
访问2，print2
完整代码
void DFSTraverse(Graph G) {//对图G进行深度优先遍历
for (v = 0; v < G.vexnum; ++v)
visited[v] = FALSE;//初始化已访问标记数组
for (v = 0; v < G.vexnum; ++v)
if (!visited[v])
DFS(G, v);
}
void DFS(Graph G, int v) {//从顶点v出发，深度优先遍历图G
visited[v] = True;//设已访问标记
for(w=FirstNeigbor(G,v);w>=0;w=NextNeighbor(G,v,w))
if (!visited[w]) {//w为u的尚未访问的邻接顶点
DFS(G, w);
}
print(v);
}
内容总结
以上是互联网集市为您收集整理的6-13知识点：数据结构——图全部内容，希望文章能够帮你解决6-13知识点：数据结构——图所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。