图论算法讲解

图的基本概念

图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V,E)，其中 V 是非空有限集合，代表顶点，E 是可以为空的有限集合，代表边。

若顶点 vi 和 vj 间的边没有方向，则称这条边为无向边，用无序偶对 (vi,vj) 表示；若顶点 vi 和 vj 间的边有方向，则称这条边为有向边（弧），用有序偶对表示，其中 vi 称为弧头，vj 称为弧尾。

图的存储结构

图的存储结构分为邻接矩阵、邻接表、链式向前星、十字链表、邻接多重表。

邻接矩阵

图的邻接矩阵存储也称数组表示法，其方法是用一个一维数组存储图中的顶点，用一个二维数组存储图中的所有的边，存储顶点之间邻接关系的二维数组称为邻接矩阵。

设图 G=(V,E) 具有 n 个顶点，则其邻接矩阵是一个 n*n 的方阵，定义为

$G[i][j]=\left\{\begin{matrix}1,(v_i,v_j)\in E\:\:or\:\:<v_i,v_j>\in E \\ 0, (v_i,v_j)\notin E\:\:and\:\:<v_i,v_j>\notin E \end{matrix}\right.$

其对确定边操作效率高，但由于其过高的空间复杂度，对稀疏图来说造成了极大的浪费，且由于二维数组可开的空间范围有限，因此邻接矩阵一般适用于点较少的图。


#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"
 
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 /* 最大顶点数，应由用户定义 */
#define INFINITY 65535
 
typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char VertexType; /* 顶点类型应由用户定义  */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct
{
	VertexType vexs[MAXVEX]; /* 顶点表 */
	EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
	int numNodes, numEdges; /* 图中当前的顶点数和边数  */
}MGraph;
 
/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph *G)
{
	int i,j,k,w;
	printf("输入顶点数和边数:\n");
	scanf("%d,%d",&G->numNodes,&G->numEdges); /* 输入顶点数和边数 */
	for(i = 0;i numNodes;i++) /* 读入顶点信息,建立顶点表 */
		scanf(&G->vexs[i]);
	for(i = 0;i numNodes;i++)
		for(j = 0;j numNodes;j++)
			G->arc[i][j]=INFINITY;	/* 邻接矩阵初始化 */
	for(k = 0;k numEdges;k++) /* 读入numEdges条边，建立邻接矩阵 */
	{
		printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
		scanf("%d,%d,%d",&i,&j,&w); /* 输入边(vi,vj)上的权w */
		G->arc[i][j]=w; 
		G->arc[j][i]= G->arc[i][j]; /* 因为是无向图，矩阵对称 */
	}
}
 
int main(void)
{    
	MGraph G;    
	CreateMGraph(&G);
	getchar();
	
	return 0;
}

邻接表

邻接表是一种顺序存储与链接存储相结合的存储方法，类似于树的孩子链表表示法。

对于图 G 的每个顶点 vi，将所有邻接于 vi 的顶点链成一个单链表，称为 vi 的边表，若图 G 是一有向图，则称为 vi 的出边表。

为方便对所有边表的头指针进行存储操作，使用顺序存储，这样，存储边表头指针的数组和存储顶点信息的数组构成了邻接表的表头数组，称为顶点表。

相较于邻接矩阵，其由数组转链表，由定长转不定长，内存利用率高，能较好的处理稀疏图，对不确定的边操作较为方便，但由于存储方式的问题，其对重边不好处理，且对确定边处理效率并不高。


#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"
 
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 100 /* 最大顶点数,应由用户定义 */
 
typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
 
typedef struct EdgeNode /* 边表结点  */
{
	int adjvex;    /* 邻接点域,存储该顶点对应的下标 */
	EdgeType info;		/* 用于存储权值,对于非网图可以不需要 */
	struct EdgeNode *next; /* 链域,指向下一个邻接点 */
}EdgeNode;
 
typedef struct VertexNode /* 顶点表结点 */
{
	VertexType data; /* 顶点域,存储顶点信息 */
	EdgeNode *firstedge;/* 边表头指针 */
}VertexNode, AdjList[MAXVEX];
 
typedef struct
{
	AdjList adjList; 
	int numNodes,numEdges; /* 图中当前顶点数和边数 */
}GraphAdjList;
 
/* 建立图的邻接表结构 */
void  CreateALGraph(GraphAdjList *G)
{
	int i,j,k;
	EdgeNode *e;
	printf("输入顶点数和边数:\n");
	scanf("%d,%d",&G->numNodes,&G->numEdges); /* 输入顶点数和边数 */
	for(i = 0;i < G->numNodes;i++) /* 读入顶点信息,建立顶点表 */
	{
		scanf(&G->adjList[i].data); 	/* 输入顶点信息 */
		G->adjList[i].firstedge=NULL; 	/* 将边表置为空表 */
	}
	
	
	for(k = 0;k < G->numEdges;k++)/* 建立边表 */
	{
		printf("输入边(vi,vj)上的顶点序号:\n");
		scanf("%d,%d",&i,&j); /* 输入边(vi,vj)上的顶点序号 */
		e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */
		e->adjvex=j;					/* 邻接序号为j */                         
		e->next=G->adjList[i].firstedge;	/* 将e的指针指向当前顶点上指向的结点 */
		G->adjList[i].firstedge=e;		/* 将当前顶点的指针指向e */               
		
		e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */
		e->adjvex=i;					/* 邻接序号为i */                         
		e->next=G->adjList[j].firstedge;	/* 将e的指针指向当前顶点上指向的结点 */
		G->adjList[j].firstedge=e;		/* 将当前顶点的指针指向e */               
	}
}
 
int main(void)
{    
	GraphAdjList G;    
	CreateALGraph(&G);
	
	return 0;
}

这里对边表结点的赋值使用到了头插法。

十字链表与邻接多重表也是图的一种存储方法，但由于操作复杂、内存利用率不高等因素常不被使用。

十字链表

十字链表是有向图的一种存储方法，其实质上是邻接表与逆邻接表的结合，每条边对应的边结点分别组织到出边表与入边表中，其顶点表和边表结点结构如下：

对于顶点表来说，data 为数据域，存放顶点信息；firstIn 为入边表头指针，指向以该顶点为终点的弧构成的链表中的第一个结点；firstOut 为出边表头指针，指向以该顶点为始点的弧构成的链表中的第一个结点。

对于边表来说，tailPos 代表弧的起点在顶点表中的下标；headPos 代表弧的终点在顶点表中的下标；headLink 为入边表指针域，指向终点相同的下一条边；tailLink 为出边表指针域，指向起点相同的下一条边。

用邻接表存储无向图，每条边的两个顶点分别在以该边所依附的两个顶点的边表中，这种重复存储给图的某些操作带来不便，因此有了邻接多重表。

邻接多重表

邻接多重表主要用于存储无向图，其存储结构与邻接表类似，也有顶点表和边表组成，每条边用一个边表结点表示，其顶点表和边表的结点结构如下：

对于顶点表而言，data 为数据域，存放顶点信息；firstEdge 为边表头指针，指向依附于该顶点的第一条边的边表结点。

对于边表而言，iPos、jPos 为与某边依附的两顶点在顶点表中的下标；iLink 为指针域，指向依附于顶点 iPos 的下一条边；jLink 为指针域，指向依附于顶点 jPos 的下一条边

图的搜索

根据搜索方法的不同，分为深度优先遍历（DFS）、广度优先遍历（BFS），两者时间复杂度都是 O(N*N)，通常采用深度优先遍历。

深度优先遍历

图的深度优先遍历的基本过程为：

1.从图中某个顶点 v0 出发，首先访问 v0
2.访问结点 v0 的第一个邻接点，以这个邻接点 vt 作为一个新节点，访问 vt 所有邻接点，直到以 vt 出发的所有节点都被访问
3.回溯到 v0 的下一个未被访问过的邻接点，以这个邻结点为新节点，重复步骤 2，直到图中所有与 v0 相通的所有节点都被访问
4.若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点，重复步骤 1，直到图中的所有节点均被访问

深度优先遍历其实就是递归过程。这里就像是树的前序遍历。


#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"
 
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
 
typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码，如OK等 */  
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
 
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
 
#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535
 
typedef struct
{
	VertexType vexs[MAXVEX]; /* 顶点表 */
	EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
	int numVertexes, numEdges; /* 图中当前的顶点数和边数 */ 
}MGraph;
 
/* 用到的队列结构与函数********************************** */
 
/* 循环队列的顺序存储结构 */
typedef struct
{
	int data[MAXSIZE];
	int front;    	/* 头指针 */
	int rear;		/* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}Queue;
 
/* 初始化一个空队列Q */
Status InitQueue(Queue *Q)
{
	Q->front=0;
	Q->rear=0;
	return  OK;
}
 
/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(Queue Q)
{ 
	if(Q.front==Q.rear) /* 队列空的标志 */
		return TRUE;
	else
		return FALSE;
}
 
/* 若队列未满，则插入元素e为Q新的队尾元素 */
Status EnQueue(Queue *Q,int e)
{
	if ((Q->rear+1)%MAXSIZE == Q->front)	/* 队列满的判断 */
		return ERROR;
	Q->data[Q->rear]=e;			/* 将元素e赋值给队尾 */
	Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置， */
								/* 若到最后则转到数组头部 */
	return  OK;
}
 
/* 若队列不空，则删除Q中队头元素，用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{
	if (Q->front == Q->rear)			/* 队列空的判断 */
		return ERROR;
	*e=Q->data[Q->front];				/* 将队头元素赋值给e */
	Q->front=(Q->front+1)%MAXSIZE;	/* front指针向后移一位置， */
									/* 若到最后则转到数组头部 */
	return  OK;
}
/* ****************************************************** */
 
 
void CreateMGraph(MGraph *G)
{
	int i, j;
 
	G->numEdges=15;
	G->numVertexes=9;
 
	/* 读入顶点信息，建立顶点表 */
	G->vexs[0]='A';
	G->vexs[1]='B';
	G->vexs[2]='C';
	G->vexs[3]='D';
	G->vexs[4]='E';
	G->vexs[5]='F';
	G->vexs[6]='G';
	G->vexs[7]='H';
	G->vexs[8]='I';
 
 
	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		for ( j = 0; j < G->numVertexes; j++)
		{
			G->arc[i][j]=0;
		}
	}
 
	G->arc[0][1]=1;
	G->arc[0][5]=1;
 
	G->arc[1][2]=1; 
	G->arc[1][8]=1; 
	G->arc[1][6]=1; 
	
	G->arc[2][3]=1; 
	G->arc[2][8]=1; 
	
	G->arc[3][4]=1;
	G->arc[3][7]=1;
	G->arc[3][6]=1;
	G->arc[3][8]=1;
 
	G->arc[4][5]=1;
	G->arc[4][7]=1;
 
	G->arc[5][6]=1; 
	
	G->arc[6][7]=1; 
 
	
	for(i = 0; i < G->numVertexes; i++)
	{
		for(j = i; j < G->numVertexes; j++)
		{
			G->arc[j][i] =G->arc[i][j];
		}
	}
 
}
 
Boolean visited[MAXVEX]; /* 访问标志的数组 */
 
/* 邻接矩阵的深度优先递归算法 */
void DFS(MGraph G, int i)
{
	int j;
 	visited[i] = TRUE;
 	printf("%c ", G.vexs[i]);/* 打印顶点，也可以其它操作 */
	for(j = 0; j < G.numVertexes; j++)
		if(G.arc[i][j] == 1 && !visited[j])
 			DFS(G, j);/* 对为访问的邻接顶点递归调用 */
}
 
/* 邻接矩阵的深度遍历操作 */
void DFSTraverse(MGraph G)
{
	int i;
 	for(i = 0; i < G.numVertexes; i++)
 		visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */
	for(i = 0; i < G.numVertexes; i++)
 		if(!visited[i]) /* 对未访问过的顶点调用DFS，若是连通图，只会执行一次 */ 
			DFS(G, i);
}
 
/* 邻接矩阵的广度遍历算法 */
void BFSTraverse(MGraph G)
{
	int i, j;
	Queue Q;
	for(i = 0; i < G.numVertexes; i++)
       	visited[i] = FALSE;
    InitQueue(&Q);		/* 初始化一辅助用的队列 */
    for(i = 0; i < G.numVertexes; i++)  /* 对每一个顶点做循环 */
    {
		if (!visited[i])	/* 若是未访问过就处理 */
		{
			visited[i]=TRUE;		/* 设置当前顶点访问过 */
			printf("%c ", G.vexs[i]);/* 打印顶点，也可以其它操作 */
			EnQueue(&Q,i);		/* 将此顶点入队列 */
			while(!QueueEmpty(Q))	/* 若当前队列不为空 */
			{
				DeQueue(&Q,&i);	/* 将队对元素出队列，赋值给i */
				for(j=0;j
				{ 
					/* 判断其它顶点若与当前顶点存在边且未访问过  */
					if(G.arc[i][j] == 1 && !visited[j]) 
					{ 
 						visited[j]=TRUE;			/* 将找到的此顶点标记为已访问 */
						printf("%c ", G.vexs[j]);	/* 打印顶点 */
						EnQueue(&Q,j);				/* 将找到的此顶点入队列  */
					} 
				} 
			}
		}
	}
}
 
 
int main(void)
{    
	MGraph G;
	CreateMGraph(&G);
	printf("\n深度遍历：");
	DFSTraverse(G);
	printf("\n广度遍历：");
	BFSTraverse(G);
	return 0;
}

广度优先遍历

图的广度优先遍历的基本过程为：

1.从图中某个顶点 v0 出发，首先访问 v0，将 v0 加入队列
2.将队首元素的未被访问过的邻接点加入队列，访问队首元素并将队首元素出队，直到队列为空
3.若此时图中仍有未被访问的结点，则另选图中的一个未被访问的顶点作为起始点，重复步骤 1，直到图中的所有节点均被访问过。


#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"
 
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
 
#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535
 
typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
 
typedef char VertexType; /* 顶点类型应由用户定义 */   
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
 
/* 邻接矩阵结构 */
typedef struct
{
	VertexType vexs[MAXVEX]; /* 顶点表 */
	EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵,可看作边表 */
	int numVertexes, numEdges; /* 图中当前的顶点数和边数 */ 
}MGraph;
 
/* 邻接表结构****************** */
typedef struct EdgeNode /* 边表结点 */ 
{
	int adjvex;    /* 邻接点域,存储该顶点对应的下标 */
	int weight;		/* 用于存储权值,对于非网图可以不需要 */
	struct EdgeNode *next; /* 链域,指向下一个邻接点 */ 
}EdgeNode;
 
typedef struct VertexNode /* 顶点表结点 */ 
{
	int in;	/* 顶点入度 */
	char data; /* 顶点域,存储顶点信息 */
	EdgeNode *firstedge;/* 边表头指针 */   
}VertexNode, AdjList[MAXVEX];
 
typedef struct
{
	AdjList adjList; 
	int numVertexes,numEdges; /* 图中当前顶点数和边数 */
}graphAdjList,*GraphAdjList;
/* **************************** */
 
/* 用到的队列结构与函数********************************** */
/* 循环队列的顺序存储结构 */
typedef struct
{
	int data[MAXSIZE];
	int front;    	/* 头指针 */
	int rear;		/* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
}Queue;
 
/* 初始化一个空队列Q */
Status InitQueue(Queue *Q)
{
	Q->front=0;
	Q->rear=0;
	return  OK;
}
 
/* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
Status QueueEmpty(Queue Q)
{ 
	if(Q.front==Q.rear) /* 队列空的标志 */
		return TRUE;
	else
		return FALSE;
}
 
/* 若队列未满,则插入元素e为Q新的队尾元素 */
Status EnQueue(Queue *Q,int e)
{
	if ((Q->rear+1)%MAXSIZE == Q->front)	/* 队列满的判断 */
		return ERROR;
	Q->data[Q->rear]=e;			/* 将元素e赋值给队尾 */
	Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置, */
								/* 若到最后则转到数组头部 */
	return  OK;
}
 
/* 若队列不空,则删除Q中队头元素,用e返回其值 */
Status DeQueue(Queue *Q,int *e)
{
	if (Q->front == Q->rear)			/* 队列空的判断 */
		return ERROR;
	*e=Q->data[Q->front];				/* 将队头元素赋值给e */
	Q->front=(Q->front+1)%MAXSIZE;	/* front指针向后移一位置, */
									/* 若到最后则转到数组头部 */
	return  OK;
}
/* ****************************************************** */
 
 
 
void CreateMGraph(MGraph *G)
{
	int i, j;
 
	G->numEdges=15;
	G->numVertexes=9;
 
	/* 读入顶点信息,建立顶点表 */ 
	G->vexs[0]='A';
	G->vexs[1]='B';
	G->vexs[2]='C';
	G->vexs[3]='D';
	G->vexs[4]='E';
	G->vexs[5]='F';
	G->vexs[6]='G';
	G->vexs[7]='H';
	G->vexs[8]='I';
 
 
	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		for ( j = 0; j < G->numVertexes; j++)
		{
			G->arc[i][j]=0;
		}
	}
 
	G->arc[0][1]=1;
	G->arc[0][5]=1;
 
	G->arc[1][2]=1; 
	G->arc[1][8]=1; 
	G->arc[1][6]=1; 
	
	G->arc[2][3]=1; 
	G->arc[2][8]=1; 
	
	G->arc[3][4]=1;
	G->arc[3][7]=1;
	G->arc[3][6]=1;
	G->arc[3][8]=1;
 
	G->arc[4][5]=1;
	G->arc[4][7]=1;
 
	G->arc[5][6]=1; 
	
	G->arc[6][7]=1; 
 
	
	for(i = 0; i < G->numVertexes; i++)
	{
		for(j = i; j < G->numVertexes; j++)
		{
			G->arc[j][i] =G->arc[i][j];
		}
	}
 
}
 
/* 利用邻接矩阵构建邻接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{
	int i,j;
	EdgeNode *e;
 
	*GL = (GraphAdjList)malloc(sizeof(graphAdjList));
 
	(*GL)->numVertexes=G.numVertexes;
	(*GL)->numEdges=G.numEdges;
	for(i= 0;i /* 读入顶点信息,建立顶点表 */   
	{
		(*GL)->adjList[i].in=0;
		(*GL)->adjList[i].data=G.vexs[i];
		(*GL)->adjList[i].firstedge=NULL; 	/* 将边表置为空表 */
	}
	
	for(i=0;i/* 建立边表 */
	{ 
		for(j=0;j
		{
			if (G.arc[i][j]==1)
			{
				e=(EdgeNode *)malloc(sizeof(EdgeNode));
				e->adjvex=j;					/* 邻接序号为j */                         
				e->next=(*GL)->adjList[i].firstedge;	/* 将当前顶点上的指向的结点指针赋值给e */
				(*GL)->adjList[i].firstedge=e;		/* 将当前顶点的指针指向e */   
				(*GL)->adjList[j].in++;
				
			}
		}
	}
	
}
 
Boolean visited[MAXSIZE]; /* 访问标志的数组 */
 
/* 邻接表的深度优先递归算法 */
void DFS(GraphAdjList GL, int i)
{
	EdgeNode *p;
 	visited[i] = TRUE;
 	printf("%c ",GL->adjList[i].data);/* 打印顶点,也可以其它操作 */
	p = GL->adjList[i].firstedge;
	while(p)
	{
 		if(!visited[p->adjvex])
 			DFS(GL, p->adjvex);/* 对为访问的邻接顶点递归调用 */
		p = p->next;
 	}
}
 
/* 邻接表的深度遍历操作 */
void DFSTraverse(GraphAdjList GL)
{
	int i;
 	for(i = 0; i < GL->numVertexes; i++)
 		visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */
	for(i = 0; i < GL->numVertexes; i++)
 		if(!visited[i]) /* 对未访问过的顶点调用DFS,若是连通图,只会执行一次 */ 
			DFS(GL, i);
}
 
/* 邻接表的广度遍历算法 */
void BFSTraverse(GraphAdjList GL)
{
	int i;
    EdgeNode *p;
	Queue Q;
	for(i = 0; i < GL->numVertexes; i++)
       	visited[i] = FALSE;
    InitQueue(&Q);
   	for(i = 0; i < GL->numVertexes; i++)
   	{
		if (!visited[i])
		{
			visited[i]=TRUE;
			printf("%c ",GL->adjList[i].data);/* 打印顶点,也可以其它操作 */
			EnQueue(&Q,i);
			while(!QueueEmpty(Q))
			{
				DeQueue(&Q,&i);
				p = GL->adjList[i].firstedge;	/* 找到当前顶点的边表链表头指针 */
				while(p)
				{
					if(!visited[p->adjvex])	/* 若此顶点未被访问 */
 					{
 						visited[p->adjvex]=TRUE;
						printf("%c ",GL->adjList[p->adjvex].data);
						EnQueue(&Q,p->adjvex);	/* 将此顶点入队列 */
					}
					p = p->next;	/* 指针指向下一个邻接点 */
				}
			}
		}
	}
}
 
int main(void)
{    
	MGraph G;  
	GraphAdjList GL;    
	CreateMGraph(&G);
	CreateALGraph(G,&GL);
 
	printf("\n深度遍历:");
	DFSTraverse(GL);
	printf("\n广度遍历:");
	BFSTraverse(GL);
	return 0;
}

AOV 网与拓扑排序

AOV 网

一个有向无环图称为无环图（Directed Acyclic Graph），简称 DAG 图，因此一个 AOV 网必定是一个有向无环图，即不带有回路。

拓扑排序

选择一个入度为 0 的顶点并输出。
从 AOV 网中删除此顶点及以此顶点为起点的所有关联边（即相邻边的入度减1）。
重复上述两步，直到不存在入度为 0 的顶点为止。
若输出的顶点数小于 AOV 网中的顶点数，则说明 AOV 网中回路，不是一个标准的 AOV 网。

整个拓扑排序的时间复杂度是o(n+e). n个定点e条弧的AOV网。


#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"
 
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXEDGE 20
#define MAXVEX 14
#define INFINITY 65535
 
typedef int Status;	/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
 
/* 邻接矩阵结构 */
typedef struct
{
	int vexs[MAXVEX];
	int arc[MAXVEX][MAXVEX];
	int numVertexes, numEdges;
}MGraph;
 
/* 邻接表结构****************** */
typedef struct EdgeNode /* 边表结点  */
{
	int adjvex;    /* 邻接点域，存储该顶点对应的下标 */
	int weight;		/* 用于存储权值，对于非网图可以不需要 */
	struct EdgeNode *next; /* 链域，指向下一个邻接点 */
}EdgeNode;
 
typedef struct VertexNode /* 顶点表结点 */
{
	int in;	/* 顶点入度 */
	int data; /* 顶点域，存储顶点信息 */
	EdgeNode *firstedge;/* 边表头指针 */
}VertexNode, AdjList[MAXVEX];
 
typedef struct
{
	AdjList adjList; 
	int numVertexes,numEdges; /* 图中当前顶点数和边数 */
}graphAdjList,*GraphAdjList;
/* **************************** */
 
 
void CreateMGraph(MGraph *G)/* 构件图 */
{
	int i, j;
	
	/* printf("请输入边数和顶点数:"); */
	G->numEdges=MAXEDGE;
	G->numVertexes=MAXVEX;
 
	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		G->vexs[i]=i;
	}
 
	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		for ( j = 0; j < G->numVertexes; j++)
		{
			G->arc[i][j]=0;
		}
	}
 
	G->arc[0][4]=1;
	G->arc[0][5]=1; 
	G->arc[0][11]=1; 
	G->arc[1][2]=1; 
	G->arc[1][4]=1; 
	G->arc[1][8]=1; 
	G->arc[2][5]=1; 
	G->arc[2][6]=1;
	G->arc[2][9]=1;
	G->arc[3][2]=1; 
	G->arc[3][13]=1;
	G->arc[4][7]=1;
	G->arc[5][8]=1;
	G->arc[5][12]=1; 
	G->arc[6][5]=1; 
	G->arc[8][7]=1;
	G->arc[9][10]=1;
	G->arc[9][11]=1;
	G->arc[10][13]=1;
	G->arc[12][9]=1;
 
}
 
/* 利用邻接矩阵构建邻接表 */
void CreateALGraph(MGraph G,GraphAdjList *GL)
{
	int i,j;
	EdgeNode *e;
 
	*GL = (GraphAdjList)malloc(sizeof(graphAdjList));
 
	(*GL)->numVertexes=G.numVertexes;
	(*GL)->numEdges=G.numEdges;
	for(i= 0;i /* 读入顶点信息，建立顶点表 */
	{
		(*GL)->adjList[i].in=0;
		(*GL)->adjList[i].data=G.vexs[i];
		(*GL)->adjList[i].firstedge=NULL; 	/* 将边表置为空表 */
	}
	
	for(i=0;i/* 建立边表 */
	{ 
		for(j=0;j
		{
			if (G.arc[i][j]==1)
			{
				e=(EdgeNode *)malloc(sizeof(EdgeNode));
				e->adjvex=j;					/* 邻接序号为j  */                        
				e->next=(*GL)->adjList[i].firstedge;	/* 将当前顶点上的指向的结点指针赋值给e */
				(*GL)->adjList[i].firstedge=e;		/* 将当前顶点的指针指向e  */  
				(*GL)->adjList[j].in++;
				
			}
		}
	}
	
}
 
 
/* 拓扑排序，若GL无回路，则输出拓扑排序序列并返回1，若有回路返回0。 */
Status TopologicalSort(GraphAdjList GL)
{    
	EdgeNode *e;    
	int i,k,gettop;   
	int top=0;  /* 用于栈指针下标  */
	int count=0;/* 用于统计输出顶点的个数  */    
	int *stack;	/* 建栈将入度为0的顶点入栈  */   
	stack=(int *)malloc(GL->numVertexes * sizeof(int) );    
 
	for(i = 0; inumVertexes; i++)                
		if(0 == GL->adjList[i].in) /* 将入度为0的顶点入栈 */         
			stack[++top]=i;    
	while(top!=0)    
	{        
		gettop=stack[top--];        
		printf("%d -> ",GL->adjList[gettop].data);        
		count++;        /* 输出i号顶点，并计数 */        
		for(e = GL->adjList[gettop].firstedge; e; e = e->next)        
		{            
			k=e->adjvex;            
			if( !(--GL->adjList[k].in) )  /* 将i号顶点的邻接点的入度减1，如果减1后为0，则入栈 */                
				stack[++top]=k;        
		}
	}   
	printf("\n");   
	if(count < GL->numVertexes)        
		return ERROR;    
	else       
		return OK;
}
 
 
int main(void)
{    
	MGraph G;  
	GraphAdjList GL; 
	int result;   
	CreateMGraph(&G);
	CreateALGraph(G,&GL);
	result=TopologicalSort(GL);
	printf("result:%d",result);
	getchar();
 
	return 0;
}

AOE 网与关键路径

AOE 网

用顶点表示事件，用弧表示活动，权值表示活动的持续时间，这样的有向图即为 AOE 网。

在 AOE 网中，只有一个入度为 0 的点表示工程的开始，即源点，也只有一个出度为 0 的点表示工程的结束，即汇点。

关键路径

在 AOE 网上，从源点到汇点的具最大路径长度（该路径上行各活动持续时间的和）的路径称为关键路径，关键路径上的活动称为关键活动。

相关阅读:
JavaSE之数组
 模拟登陆系统
 医院陪诊小程序源码医院陪诊陪护系统源码
 芒果改进YOLOv7系列：首发改进特征融合网络BiFPN结构，融合更多有效特征
 【linux下centos7.9安装docker，docker-composed（root用户）】
跟我学c++初级篇——别名的使用
 c++ fstream 文件追加模式
 Python使用SQLAlchemy操作sqlite
U-Net: Convolutional Networks for Biomedical Images Segmentation
RTT学习笔记11- gpio使用和GPIO设备驱动框架层
原文地址：https://blog.csdn.net/baidu_16370559/article/details/126059777