标签：结点 int 连通 ++ 邻接 第六章 顶点 数据结构

数据结构（第六章）

图

• 定义：图是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为G（V,E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
• 特性：
  1. ​ 在图中数据元素，我们称之为顶点。
  2. 任意两个顶点之间都有可能有关系，顶点之间的逻辑关系用边来表示。

无向图

定义：如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。

无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对(Vi，Vj)来表示。

有向图

若E是有向边（也称弧）的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v,w>,其中v,是顶点，v称为弧尾，w称为弧头，<v,w>称为v到w的弧，也称v邻接到w

图的其他特性

1. 简单图

一个图G如果满足：1.不存在重复边 2.不存在顶点到自身的边 ，那么称图G为简单图。

2. 完全图

对于无向图，|E|的取值范围为0到n(n-1)/2,有n(n-1)/2条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。对于有向图，|E|的取值范围为0到n(n-1),有n(n-1)条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。

3. 连通图、连通分量

图G中任意两个顶点都是连通的，则称图G为连通图。无向图中的极大连通子图称为连通分量。

4. 强连通图、强连通分量

在有向图中，如果一对顶点v和w，从v到w和从w到v之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。

注意：极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边；极小连通子图是既要保持图连通又要使得边数最少的子图。

5. 生成树、生成森林

连通图的生成树是包含图中全部项点的一个极小连通子图。若图中顶点数为n，则它的生成树含有n-1条边。包含图中全部顶点的极小连通子图，只有生成树满足这个极小条件，对生成而言。若砍去它的一条边，则会变成非连通图，着加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。

6. 顶点的度、入度和出度

在无向图中，顶点v的度是指依附于顶点v的边的条数，记为TD(v)。对于具有n个顶点-e条边的无向图，∑TD(v)=2e，即无向图的全部顶点的度的和等于边数的2倍，因为每条边和两个项点相关联。在有向图中，顶点v的度分为入度和出度，入度是以顶点v为终点的有向边的数目，记为I(v)；而出度是以顶点v为起点的有向边的数目，记为OD(v)。顶点v的度等于其入度与出度之和，即TD(V)=ID(v)+OD(v)。对于具有n个顶点、e条边的有向图，∑ID(v)-∑OD(v)=e，即有向图的全部顶点的入度之和与出度之和相等，并且等于边数，这是因为每条有向边都有一个起点和终点。

7. 边的权和网

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

8. 稠密图和稀疏图

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图G满足|E|<|V|log|V|时，可以将G视为稀疏图。

9. 路径、路径长度和回路

路径上边的数目称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有n个顶点，并且有大于n-1条边，则此图一定有环。

10. 简单路径、简单回路

在路径序列中，顶点不重复出现的路径称为简单单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

11. 距离

从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。若从u到v根本不存在路径，则记该距离为无穷。

12. 有向树

一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

图的存储及基本操作

一、邻接矩阵表示法（重点）

• 主要适用于稠密网

• 定义：邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即个顶点间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。

邻接矩阵的存储结构：

#define MAXSIZE  //最大顶点数
#define INFINITY 65535 //代表无穷
typedef int VertexType; //顶点类型
typedef int EdgeType ; //边的权值大小
typedef struct {
    VertexType vexs[MAXSIZE] ; //顶点个数
    EdgeType arc[MAXSIZE][MAXSIZE] ; //邻接矩阵 ，边的个数
    int numvexs , numarcs; //图中当前顶点数和边数
}MGraph;

创建邻接矩阵：

void CreateMGraph(MGraph &G){
    int k ,w ;  //邻接矩阵的坐标点
    EdgeType e; //边的权值大小
    cout<<"输入顶点个数和边数:\n";
    cin>>G.numvexs>>G.numarcs;
    for (int i = 0; i < G.numvexs; ++i) { //输入顶点值，创建顶点表
       cin>> G.vexs[i];
    }
    for (int i = 0; i < G.numvexs; ++i) { //邻接矩阵初始化
        for (int j = 0; j < G.numvexs; ++j) {
            G.arc[i][j]=INFINITY;
        }
    }
    for (int i = 0; i < G.numarcs; ++i) {
        G.arc[k][w]=e;
        G.arc[w][k]=G.arc[k][w];//无向图带权值的邻接矩阵创建方法
    }
}

二、邻接表表示法（重点）

• 主要适用于存储稀疏图
• 所谓邻接表，是指对图G中的每个顶点v建立一个单链表，第i个单链表中的结点表示依附于顶点v的边（对于有向图则是以顶点vi为尾的弧），这个单链表就称为顶点v的边表（对于有向图则称为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点。顶点表结点由顶点域（data）和指向第一条邻接边的指针（firstarc）构成，边表（邻接表）结点由邻接点域（adjvex）和指向下一条邻接边的指针域（nextarc）构成。

表的结构:

顶点域	边表头指针
data	firstarc

邻接点域	指针域
adjvex	nextarc

• 特点：邻接表不唯一。若无向图中有n个顶点，e条边，则其邻接表需要n个头结点和2e个表结点。

邻接表的存储结构：

#define MaxVertexNum 100 //图中顶点数目的最大值
typedef int VertexType; //顶点类型
typedef  int EdgeType; //边上的权值类型
typedef struct ArcNode{ //边表结点
    int adjvex;  //该弧所指向顶点的位置
    struct ArcNode *next; //指向下一条弧的指针
}ArcNode;
typedef struct VNode{  //顶点表结点
    VertexType data; //顶点信息
    ArcNode *first; //指向第一条依附在该顶点的弧的指针
}VNode , AdjList[MaxVertexNum];
typedef struct {
    AdjList vertices; //邻接表
    int vexnums ,arcnums; //图的顶点和弧数
}ALGraph; //邻接表结构

创建无向图的邻接表：

//创建无向图的邻接表
void CreateALGraph(ALGraph &A){
    int k ,w ;//定义边上的顶点的序号(k,w)
    ArcNode *a;
    cout<<"输入顶点数和边数:"<<endl;
    cin>>A.vexnums>>A.arcnums;
    for (int i = 0; i < A.arcnums; ++i) { //读入顶点信息，创建空表
        cin>>A.vertices[i].data;//输入顶点信息
        A.vertices[i].first=NULL; //将边表置为空表
    }
    //这里主要用到了头插法的思想
    for (int i = 0; i < A.arcnums; ++i) { //创建边表
        cout<<"输入边表上的顶点序号:"<<endl;
        cin>>k>>w;
        a=new ArcNode ; //开辟一个结点空间
        a->adjvex=k; //邻接序号
        a->next=A.vertices[w].first; //表示将a的指针指向当前顶点指向的结点
        A.vertices[w].first=a;//将当前顶点的指针指向e
        a=new ArcNode ;
        a->adjvex=w;//邻接序号
        a->next=A.vertices[k].first;//表示将a的指针指向当前顶点指向的结点
        A.vertices[k].first=a;//将当前顶点的指针指向e
    }
}

三、十字链表法

• 主要适用于有向图
• 十字链表是有向图的一种链式存储结构。在十字链表中，对应有向图中的每一条弧有一个结点，对应于每个顶点也有一个结点。

表的结构：

弧结点：

tailvex	headvex	hlink	tlink	info

顶点结点：

data	firstin	firstout

四、邻接多重表

• 主要适用于无向图
• 在邻接多重表中，所有依附于同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，因此每个边结点同时链接在两个链表中。对无向图而言，其邻接多重表和邻接表的差别仅在于，同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

表的结构：

边结点：

mark	ivex	ilink	jvex	jlink	info

顶点结点：

data	firstedge

图的遍历

一、深度优先搜索（DFS）

• 特点：按照路径依次向更深层次访问
• 算法性能分析：DFS算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为0(|V|).
  遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所用的存储结构。以邻接矩阵表示时，查找每个顶点的邻接点所需的时间为O(|V|)，故总的时间复杂度为0(|V|^2).以邻接表表示时，查找所有顶点的邻接点所需的时间为0(|E|)，访问顶点所需的时间为0(|V|).此时，总的时间复杂度为0(|V|）+（|E|)。

邻接矩阵的深度优先递归算法

bool visited[MAXSize]; //代表该顶点是否被访问
//邻接矩阵的深度优先递归算法
/*思想：一直往里面走，类似于树的先序遍历算法，只有当此路径上的所有顶点都被访问，才退回到上一个顶点
 * */
void DFS(MGraph G,int i){ // i表示起始的顶点位置
    visited[i]= true;
    cout<<"输出遍历的顶点值为："<<G.vexs[i];
    for (int j = 0; j < G.numvexs; ++j) {
        if (G.arc[i][j]==1&&!visited[i]) //判断路径是否存在且并未被访问过
            DFS(G,j);  //递归的遍历
    }
}
//邻接矩阵的深度遍历操作
void DFSTraverse(MGraph G){
    for (int i = 0; i < G.numvexs; ++i) {
        visited[i]= false;
    }
    for (int i = 0; i < G.numvexs; ++i) {
        if (!visited[i]) //当存在非连通图时判断，所有顶点是否都已被访问
         DFS(G,i);
    }
}

邻接表的深度优先递归算法

bool visited[MaxVertexNum]; //访问的标志数组
//邻接表的深度优先递归算法
void DFS(ALGraph A ,int i){
    ArcNode *p ;//边表结点
    visited[i]=true; //标识该结点被访问
    cout<<"打印遍历到的顶点"<<A.vertices[i].data;
    p=A.vertices[i].first; //起始邻接表的遍历
    while(p){
        if (!visited[p->adjvex])
            DFS(A,p->adjvex);//对未访问的邻接顶点递归调用
        p=p->next;
    }
}
void DFSTraverse(ALGraph A){
    for (int i = 0; i < A.vexnums; ++i) {
        visited[i]= false;  //初始所有顶点都是未被访问的状态
    }
    for (int i = 0; i < A.vexnums; ++i) {
        if (!visited[i])  //对未访问的顶点调用DFS，若是连通图，只会执行一次
            DFS(A,i);
    }
}

二、广度优先搜索（BFS）

• 特点：依次访问邻接点
• 算法性能分析：无论是邻接表还是邻接矩阵的存储方式，BFS 算法都需要借助一个辅助队列Q，n个顶点均需入队一次，在最坏的情况下，空间复杂度为0(|V|)。采用邻接表存储方式时，每个顶点均需搜索一次（或入队一次)，故时间复杂度为0(|V|），在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为0(|E|），算法总的时间复杂度为0（|V|+|E|），采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为0（|V|），故算法意的时间复杂度为0(|V|^2）。

邻接矩阵的广度优先搜索

//邻接矩阵的广度优先算法
//其思想类似于图的层序遍历
bool visited[MAXSIZE]; //访问标记数组
void BFS(MGraph G ,int v){ //从顶点v出发，广度优先遍历图G
    visit(v);//访问初始顶点v
    visited[v]= false;//标记访问过的结点
    EnQueue(Q,v); //顶点v入队
    while(!IsEmpty(Q)){
        DeQueue(Q,v); //将队首元素出队
        for (int i = 0; i < G.numvexs; ++i) {  //判断其他顶点是否与当前顶点存在边且未被访问
            if (G.arc[v][i]==1&&!visited[i]){
                visited[i]=true; //找到顶点，标记为已访问
                cout<<"打印遍历到的顶点："<<G.vexs[i];//visit(v)
                EnQueue(Q,i);//将找到的此顶点入队
            }
        }
    }
}
void BFSTraverse(MGraph G){ //对图进行广度优先遍历
    for (int i = 0; i < G.numvexs; ++i) { //访问标记数组初始化
        visited[i]= false;
    }
    InitQueue(Q); //初始化队列
    for (int i = 0; i < G.numvexs; ++i) { //从0号结点开始遍历
        if (!visited[i]) //对每个连通分量调用一次BFS
            BFS(G,i);
    }
}

邻接表的广度优先搜索

//邻接表的广度优先遍历搜索
bool visited[MaxVertexNum]; //访问标记数组
void BFS(ALGraph A , int v){
        ArcNode *p; //定义边表结点
        visit(v);
        visited[v]= true;
        EnQueue(Q,v);
        while(!IsEmpty(Q)){
            DeQueue(Q,v);
            p=A.vertices[v].first;//找到当前顶点的边表链的表头指针
            while(p){
                if (!visited[p->adjvex]) //此顶点未被访问
                {
                    visited[p->adjvex]=true;
                    cout<<A.vertices[p->adjvex].data;//visit(p->adjvex)访问该顶点
                    Enqueue(Q,p->adjvex);
                }
                p=p->next; //指向下一个邻接点
            }
        }
}
void BFSTraverse(ALGraph A){ //对图A进行广度优先遍历
    for (int i = 0; i < A.vexnums; ++i) { //访问标记数组初始化
        visited[i]= false; 
    }
    for (int i = 0; i < A.vexnums; ++i) {
        if (!visited[i]) //每个连通分量调用一次BFS
            BFS(A,i);
    }
}

最小生成树(MST)

一、Prim算法

• 主要用于稠密图

• 从所有的顶点中，任选一点为起点先将该顶点加入表中，比较与之连接的边中权值最小的一条与之连接，将连接之后的顶点也加入到表中，再次比较与之相连接的边，选出其中权值最小的边，依此类推。

Prim算法：

void Prim(MGraph G){
    int min , i ,j ,k;
    int adjvex[MAXVEX]; //用于保存相关顶点间边的权值点的下标
    int lowcost[MAXVEX];//用于保存相关顶点间的权值
    lowcost[0]=0; //初始化第一个的权值为0，即将第一个顶点V0加入最小生成树
    adjvex[0]=0;//初始化第一个顶点V0的下标为0
    for ( i = 1; i <G.vexnums; ++i) {
        lowcost[i]=G.arc[0][i];//将与第一个顶点V0有关的所有边的权值都存入到数组中
        adjvex[i]=0;//初始化都为V0的下标
    }
    for ( i = 1; i < G.vexnums; ++i) {
        min=INF;//初始化最小值为无穷
        j=1;k=0;
        while(j<G.vexnums){ //循环全部的顶点
            if (lowcost[j]!=0&&lowcost[j]<min){ //如果权值不为0并且权值小于最小值，则让当前权值为最小值
                min=lowcost[j];
                k=j; //将当前最小值的权值存入k
            }
            j++;
        }
        cout<<"当前顶点边中权值最小的边: ("<<adjvex[k]<<" "<<k<<")\n";
        lowcost[k]=0; //将当前顶点权值设置为0，表示此点任务完成，加入到了最小生成树当中
        for ( j = 1; j <G.vexnums ; ++j) { 
            //更新lowcost表，将与下标为k的顶点相连的边的权值，与lowcost表中进行比较，更新其中权值更大的
            if (lowcost[j]!=0&&lowcost[j]>G.arc[k][j]){
                lowcost[j]=G.arc[k][j]; //将较小的权值存入lowcost相应的位置
                adjvex[j]=k; //将下标为k的顶点存入表中
            }
        }
    }
}

二、Kruskal算法

• 主要用于稀疏图

• 从所有边中选择权值最小的边，使这条边的两头连通（原本就连通的就不需要选），直到所有的顶点都连通。

Kruskal算法：

#define MAXEDGE 100 //定义边的数量的极大值
typedef struct {
    int begin;
    int end;
    int weight;
}Edge;
//查找连接顶点的尾部下标，即为0的根结点
int Find(int *parent , int f){
      while(parent[f]>0){
          f=parent[f];
      }
      return f;
}
//Krusual算法
void Krusual(MGraph G){
    Edge edges[MAXEDGE]; //定义边集数组
    int parent[MAXVEX]; //定义数组来判断边与边是否形成环路
    //将邻接矩阵转换为边集数组edges并按权由大到小排序
    for (int i = 0; i < G.vexnums; ++i) {
        for (int j =i+1; j < G.vexnums; ++j) {
            if (G.arc[i][j]!=0&&G.arc[i][j]!=INF){
                edges[i].begin=i;
                edges[i].end=j;
                edges[i].weight=G.arc[i][j];
            }
        }
    }
    //进行排序,从小到大的顺序
    for (int i = 0; i < G.vexnums; ++i) {
        for (int j = i+1; j <G.vexnums ; ++j) {
            if (edges[i].weight>edges[j].weight){
                int temp;
                temp=edges[j].weight;
                edges[j].weight=edges[i].weight;
                edges[i].weight=temp;
            }
        }
    }
    for (int i = 0; i < G.vexnums; ++i) { //初始化数组值为0
        parent[i]=0;
    }
    for (int i = 0; i < G.arcnums; ++i) { //循环每一条边
        int n,m;
        n= Find(parent,edges[i].begin);
        m= Find(parent,edges[i].end);
        if (n!=m){ //当n与m不等时，说明这条边没有与现有生成树生成环路
            parent[n]=m;//将此边的结尾顶点放入下标为起点的parent中，表示此顶点已经在生成树集合中。
            cout<<edges[i].begin<<edges[i].end<<edges[i].weight<<endl;
        }
    }
}

最短路径

一、Dijkstra算法

• 按照路径长度递增的次序产生最短路径的算法。
• 时间复杂度为：0（n^2）
• 主要用于求单源最短路径问题

Dijkstra算法：

typedef int Path[MAXVEX] ; //用于存储最短路径的前驱
typedef int Distance[MAXVEX]; //用于存储各点最短路径的权值和
//Dijkstra算法，求有向网G的V0顶点到其余顶点V的最短路径P[V]及带权长度
//P[V]的值为前驱结点的下标，D[V]表示V0到V的最短路径长度和
void Dijkstra(MGraph G ,int V0 ,Path *P,Distance *D){
    int final[MAXVEX]; //标记该结点是否已经访问
    for (int i = 0; i < G.numvexs; ++i) {
        final[i]=0;  //全部顶点初始化为0
        (*D)[i]=G.arc[V0][i]; //该邻接矩阵中的权值
        (*P) [i]=V0; //初始化前驱结点
    }
    final[V0]=1; //表示该顶点被访问，标记
    //开始主循环，每次求得V0到某个顶点V的最短路径（权值最小）
     int min=INFINITY; //初始化最小值为INF，用于表示所知距离V0顶点的最近距离（权值最小的边）
     int k ; //用于更新标记点
    for (int i = 0; i <G.numvexs; ++i) {
        for (int j = 0; j < G.numvexs; ++j) { //寻找距离V0最近的顶点
            if (!final[j]&&(*D)[i]<min){
                k=j; //获取最小权值的下标
                min=(*D)[j];//将最短路径赋值给min
            }
        }
        final[k]=1; //标记该顶点被访问，此时开始从此 顶点寻找最短路径
        for (int j = 0; j < G.numvexs; ++j) { //更新权值表Distance和路径前驱Path
            if (!final[j]&&min+G.arc[k][j]<(*D)[j]) //如果经过V顶点的路径比现在这条路径段则进行更新
            {
                (*D)[j]=min+G.arc[k][j];//更新Distance表
                (*P)[j]=k; //更新前驱顶点
            }

        }
    }
}
//打印路径 从后往前需要栈
void Print(int path[],int j)
{
int stc[MAXVEX];
int top=-1;
while(path[j]!=-1)//有路径
{
stc[++top]=j;
j=path[j];
}
stc[++top]=j;
while(top!=-1)
{
cout<<stc[top--]<<' ';
}
cout<<endl;
}

二、Floyd算法

• 允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。
• 适用于带权无向图
• 时间复杂度为：0(n^2)
• 主要用于求各顶点之间最短路径问题

Floyd算法：

typedef int Path[MAXVEX][MAXVEX]; //前驱
typedef int Distance[MAXVEX][MAXVEX]; //带权路径长度
//Floyd算法，求网图G各顶点到其余顶点w的最短路径P[v][w]及带权长度D[v][w]
void Floyd(MGraph G ,Path *P ,Distance *D){
    for (int v = 0; v < G.numvexs; ++v) { //初始化D和P
        for (int w = 0; w < G.numvexs; ++w) {
            (*D)[v][w]=G.arc[v][w]; //D[v][w]的值为对应边上的权值
            (*P)[v][w]=-1; //初始化P
        }
    }
    for (int k = 0; k < G.numvexs; ++k) { //考虑已K为中转点
        for (int v = 0; v <G.numvexs; ++v) { //v表示行号
            for (int w = 0; w < G.numvexs; ++w) { //w表是列号
                if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w]){ //如果经过下标k的路径比原来的路径短
                    (*D)[v][w]=(*D)[v][k]+(*D)[k][w];//更新最短路径
                    (*P)[v][w]=k;//更新中转点
                }
            }
        }
    }
}
void Print(int u,int v,int path[][],int Distance[][])//运用递归与中间结点输出路径
{
if(Distance[u][v]==INF)//无路径直接返回
return;
else if(path[u][v]==-1)//无中间结点直接输出
cout<<u<<' '<<v;
else//运用递归与中间结点输出路径
{
int mid=path[u][v];
Print(u,mid,path,A);
print(mid,v,path,A);
}
}

拓扑排序

• AOV网：若用DAG图表示一个工程，其顶点表示活动，用有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行的这样一种关系，则将这种有向图称为顶点表示活动网络，记为AOV网。

• 拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序：
  ①每个顶点出现且只出现一次。
  ②若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。

• 对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：

  ①从AOV网中选择一个没有前驱的顶点并输出。
  ②从网中删除该顶点和所有以它为起点的有向边。
  ③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。后一种情况说
  明有向图中必然存在环。

拓扑排序：

#define MAXVEX 100
//采用邻接表的结构进行存储
typedef struct ArcNode{ //边表结点
    int adjvex;  //邻接点域，存储该顶点对应的下标
    int weight;  //用于存储权值，对于非网图可以不需要
    struct ArcNode *next; //链域，用于指向下一个邻接点
}ArcNode;
typedef struct VertexNode{ //顶点表结点
    int in; //顶点的入度
    int data; //顶点域，存储顶点信息
    ArcNode *firstedge; //边表头指针
}VertexNode ,AdjList[MAXVEX];
typedef struct {
    AdjList vertices;
    int numvexs, numarc; //图中当前顶点数和边数
}ALGraph;

//拓扑排序，若G无回路，则输出拓扑排序序列并返回1，若有回路则返回0
int TopologicalSort(ALGraph *G){
 
        int n=0;
        int stc[MAXVEX],top=-1; //栈指针的下标
        for(int i=0;i<G->numvexs;i++)
        {
            if(G->vertices[i].in==0) //将入度为0的点入栈
            {
                stc[++top]=i;
            }
        }
        ArcNode *p; //定义边表结点
        while(top!=-1)
        {
            int k=stc[top--]; //将所有与入度为0的顶点的度减一
            visit(k); //访问此顶点
            n++; //统计顶点数
            p=G->vertices[k].firstedge;
            while(p!=NULL) //对顶点弧表进行遍历
            {
                int j=p->adjvex;
                --G->vertices[j].in; //将该顶点的入度减一
                if(G->vertices[j].in==0) //若为0则出栈，以便后续的visit操作
                {
                    stc[++top]=j;
                }
                p=p->next;
            }
        }
        if(n==G->numvexs) //n小于顶点数说明存在环
        {
            return 1;
        }
        else
            return 0;
    }

标签：结点,int,连通,++,邻接,第六章,顶点,数据结构
From： https://www.cnblogs.com/wfy-studying/p/17529924.html