数据结构重读 - 有向无环图、AOV网和拓扑排序

DAG和概念

有向无环图:顾名思义,有向图,且不含环,directed acycline graph,简称DAG图。

无向图检查环:若深度优先遍历过程遇到回边(先前访问过的顶点的边),则必定存在环。

有向图检查环:从某个顶点v出发,在dfs(v)结束前,出现一条从顶点u到顶点v的回边,由于u在生成树上是v的子孙,则有向图必定存在包含顶点v和u之间的环。

DAG图是描述工程的有效工具。一个工程可以用一个DAG图表示,每一个顶点是一个子工程,工程的先后关系用弧表示。

围绕着工程,两个关心的问题是:

1、工程能否顺利进行(拓扑排序问题)

2、工程完成所必须的最短时间(关键路径问题)

 

AOV网和拓扑排序

偏序:集合中仅有部分成员之间可以比较。

全序:集合中全体成员均可比较。

比如下图左边是偏序,右边是全序。

拓扑有序:全序上面的排序

拓扑排序:由于集合上一个偏序得到该集合上的一个全序。

AOV网(Activity On Vertex Network):用顶点表示活动,用弧表示活动之间的优先关系的有向图称为顶点表示活动的网。

在AOV网上不应该出现有向环,因此,给定一个AOV网,要先判断是否存在环。

AOV图求拓扑排序的算法如下

1、从有向图中选取一个没有前驱的顶点(入度为0的)。

2、从图中删除该顶点和所有以它为尾的弧(此时可能会产生新的无前驱顶点)。

循环上述两步,直到

(1)所有顶点都全部输出。

Or

(2)不存在无前驱的顶点,说明图中有环。

上述算法非常简单明了,连AOV图的环判定也一起做了。

具体到实现,我们可以增添两个数据结构:

(1) 存放各个顶点入度的集合indegree。

(2)一个暂存入度为0的栈。

算法变成了:

1、扫描所有顶点的入度。

2、将入度为0的,入栈。

3、循环直到栈空

弹出栈、输出。

将关联的边入度减1,如果为0,入栈。

4、最终检查输出了多少个结点,如果小于nvexs,说明有环。

代码如下:

注意这里是有向图,图的创建不能在用无向图的双边了!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VEXS 100
#define MAX_QUEUE 1000

// Arc
struct Arc
{
	int ivex; // The vex position in vexs array
	struct Arc* next;
};

// Vex
struct Vex
{
	int data;
	struct Arc* first_arc;
};

// Graph
struct Graph
{
	struct Vex vexs[MAX_VEXS];
	int nvexs;
	int narcs;
};

int graph_locate(struct Graph* g, int val)
{
	int i;
	for(i=0; i<g->nvexs; i++)
	{
		if(g->vexs[i].data==val)
		{
			return i;
		}
	}
	return -1;
}

void graph_add_arc(struct Graph* g, int x, int y)
{
	// New arc
	struct Arc* new_arc = (struct Arc*)malloc(sizeof(struct Arc));
	struct Arc* ptr = NULL;
	if(!new_arc)
	{
		return ;
	}
	new_arc->ivex = y;
	new_arc->next = NULL;
	// Find vexs[x]'s tail
	if(!g->vexs[x].first_arc)
	{
		g->vexs[x].first_arc = new_arc;
	}else
	{
		ptr = g->vexs[x].first_arc;
		while(ptr->next!=NULL)
		{
			ptr = ptr->next;
		}
		ptr->next = new_arc;
	}
}

void graph_create(struct Graph* g)
{
	int i;
	int x, y;
	struct Arc* ptr;
	// Get n vexs
	printf("Please enter n for number of vexs:\n");
	scanf("%d", &g->nvexs);
	for(i=0; i<g->nvexs; i++)
	{
		printf("Please enter a int for vexs(%d):\n", i);
		scanf("%d", &g->vexs[i].data);
		g->vexs[i].first_arc = NULL;
	}
	// Get m arcs;
	printf("Please enter m for number of vexs:\n");
	scanf("%d", &g->narcs);
	for(i=0; i<g->narcs; i++)
	{
		printf("Please enter x y for arcs(%d):\n", i);
		scanf("%d %d", &x, &y);
		x = graph_locate(g, x);
		y = graph_locate(g, y);
		if(x==-1 || y==-1)
		{
			printf("Wrong x or y for arcs(%d).\n", i);
			i--;
		}
		// arc x->y
		graph_add_arc(g, x, y);
	}
}

void graph_print(struct Graph* g)
{
	int i;
	struct Arc* ptr;
	// Just print arcs
	for(i=0;i<g->nvexs;i++)
	{
		ptr = g->vexs[i].first_arc;
		while(ptr)
		{
			printf("%d->%d\n", g->vexs[i].data, g->vexs[ptr->ivex].data);
			ptr = ptr->next;
		}
	}
}

void graph_init(struct Graph* g)
{
	int i;
	for(i=0; i<MAX_VEXS; i++)
	{
		g->vexs[i].first_arc = NULL;
	}
	g->nvexs = 0;
	g->narcs = 0;
}

void graph_free(struct Graph* g)
{
	int i;
	struct Arc* ptr;
	struct Arc* free_node;
	g->nvexs = 0;
	g->narcs = 0;
	for(i=0; i<MAX_VEXS; i++)
	{
		ptr = g->vexs[i].first_arc;
		while(ptr!=NULL)
		{
			free_node = ptr;
			ptr = ptr->next;
			free(free_node);
		}
	}
}

#define MAX_STACK 100

struct Stack
{
	int top;
	int data[MAX_STACK];
};

void stack_init(struct Stack* stk)
{
	stk->top = 0;
}

int stack_push(struct Stack* stk, int v)
{
	if(stk->top>=MAX_STACK)
	{
		return -1;
	}else
	{
		stk->data[stk->top++] = v;
		return 0;
	}
}

int stack_pop(struct Stack* stk, int* v)
{
	if(stk->top==0)
	{
		return -1;
	}else
	{
		*v = stk->data[--stk->top];
		return 0;
	}
}

int stack_is_empty(struct Stack* stk)
{
	return stk->top==0;
}

void topo_sort(struct Graph* g)
{
	// Count indegree for all vex
	int* indeg = (int*)malloc(sizeof(int)*g->nvexs);
	int i;
	int cnt = 0;
	struct Arc* ptr = NULL;
	for(i=0;i<g->nvexs;i++)
	{
		indeg[i] = 0;
	}
	for(i=0;i<g->nvexs;i++)
	{
		ptr = g->vexs[i].first_arc;
		while(ptr!=NULL)
		{
			indeg[ptr->ivex]++;
			ptr = ptr->next;
		}
	}
	// Stack push all 0-indegree
	struct Stack* stk = (struct Stack*)(malloc(sizeof(struct Stack)));
	stack_init(stk);
	for(i=0;i<g->nvexs;i++)
	{
		if(indeg[i]==0)
		{
			if(-1==stack_push(stk, i))
			{
				printf("Push fail...\n");
				break;
			}
		}
	}
	// While !stack.empty()
	while(!stack_is_empty(stk))
	{
		int tmp;
		if(-1==stack_pop(stk, &tmp))
		{
			printf("Pop fail...\n");
			break;
		}else
		{
			// Output an vex
			printf("%d\n", g->vexs[tmp].data);
			cnt++;
			// Count-- for every vex[tmp]'s neigbhour
			ptr = g->vexs[tmp].first_arc;
			while(ptr!=NULL)
			{
				if(--indeg[ptr->ivex]==0)
				{
					stack_push(stk, ptr->ivex);
				}
				ptr = ptr->next;
			}
		}
	}
	// Free malloc resource
	free(stk);
	free(indeg);
	if(cnt<g->nvexs)
	{
		printf("This graph has cycle!!!\n");
	}
}

int main()
{
	struct Graph g;
	graph_init(&g);
	graph_create(&g);
	topo_sort(&g);
	graph_free(&g);
	return 0;
}

测试的AVO图:

测试数据:

6
1
2
3
4
5
6
8
1 2
1 3
1 4
3 2
3 5
4 5
6 4
6 5

测试输出:

6  1  4  3  5  2

 

 

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *