拓?fù)渑判?/h1>
一浙值、什么是拓?fù)渑判颍?/h2>
在圖論中，拓?fù)渑判?/code>是一個有向無環(huán)圖的所有頂點的線性序列檩小，且該序列必須滿足
- 每個頂點有且只出現(xiàn)一次
- 若存在一條從頂點 A 到頂點 B 的路徑开呐，那么在序列中頂點 A 出現(xiàn)在頂點 B 的前面
有向無環(huán)圖（DAG）才有拓?fù)渑判颍荄AG圖沒有拓?fù)渑判蜻@一說
比如下面這個無環(huán)圖
20150507001028284.png
如何寫出它的拓?fù)渑判颍?/p>
- 從 DAG 圖中選擇一個
沒有前驅(qū)（即入度為0）的頂點并輸出规求。 - 從圖中刪除該頂點和所有以它為起點的有向邊筐付。
- 重復(fù) 1 和 2 直到當(dāng)前的 DAG 圖為空或當(dāng)前圖中不存在無前驅(qū)的頂點為止。后一種情況說明有向圖中必然存在環(huán)阻肿。
20150507001759702.png
于是瓦戚，得到拓?fù)渑判蚝蟮慕Y(jié)果是 { 1, 2, 4, 3, 5 }
通常，一個有向無環(huán)圖可以有一個或多個拓?fù)渑判蛐蛄小?/p>
代碼：
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#define M 30 /*預(yù)定義圖的最大頂點數(shù)*/
//拓?fù)渑判? typedef struct node { //邊結(jié)點類型定義
int adjvex;
struct node *next;
}edgenode;
typedef struct de { //待定點入度的頭節(jié)點定義
edgenode* FirstEdge;
char vertex;
int id; //頂點的入度域
}vertexnode;
typedef struct { //AOV網(wǎng)的鄰接表結(jié)構(gòu)
vertexnode adjlist[M];
int n, e;
}AovGraph;
//類似于鄰接表的常見方式丛塌，不同的是在這里從文件多讀入了一個頂點的入度域
void createTop(AovGraph *g, char *filename, int c)
{
int i, j, k;
edgenode *s;
FILE *fp;
fp = fopen(filename,"r");
if (fp)
{
fscanf(fp, "%d%d\n", &g->n, &g->e);
for (i = 0; i < g->n; i++)
{
fscanf(fp, "%c%d ", &g->adjlist[i].vertex,&g->adjlist[i].id);
g->adjlist[i].FirstEdge = NULL;
}
for (k = 0; k < g->e;k ++)
{
fscanf(fp, "%d%d", &i, &j);
s = (edgenode *)malloc(sizeof(edgenode));
s->adjvex = j;
s->next = g->adjlist[i].FirstEdge;
g->adjlist[i].FirstEdge = s;
if (c == 0) //無向圖
{
s = (edgenode *)malloc(sizeof(edgenode));
s->adjvex = i;
s->next = g->adjlist[j].FirstEdge;
g->adjlist[i].FirstEdge = s;
}
}
fclose(fp); //關(guān)閉文件流
}
else
{
g->n = 0;
printf("文件打開失斀辖狻！\n");
}
}
//拓?fù)渑判虻乃惴?
int TopSort(AovGraph g)
{
int k = 0, i, j, v, flag[M];
int queue[M]; //定義隊列
int front, rear;
edgenode *p;
front = rear = 0; //初始化隊列
for (i = 0; i < g.n; i++)
flag[i] = 0; //訪問標(biāo)記初始化
for (i = 0; i < g.n; i++)
{
if (g.adjlist[i].id == 0 && flag[i] == 0)
{
queue[rear++] = i;
flag[i] = 1;
}
}
printf("\n該AOV網(wǎng)的拓?fù)渑判驗椋篭n");
while (front < rear) // 如果當(dāng)前隊列不為空
{
v = queue[front++]; //隊列首位元素出列
printf("%c ", g.adjlist[v].vertex);
k++; //計數(shù)器加1
p = g.adjlist[v].FirstEdge;
while (p) //將所有于v鄰接的頂點的入度減1
{
j = p->adjvex;
if (--g.adjlist[j].id == 0 && flag[j] == 0) //如果入度為0則將進(jìn)隊
{
queue[rear++] = j;
flag[j] = 1; //標(biāo)記已經(jīng)被訪問過
}
p = p->next;
}
}
return k; //返回輸出的結(jié)點個數(shù)
}
int main()
{
AovGraph g;
char filename[20] = "D:\\Desktop\\Test.txt";
createTop(&g, filename, 1);
printf("拓?fù)渑判虻墓?jié)點個數(shù)：%d\n", TopSort(g));
system("pause");
return 0;
}
文件結(jié)構(gòu)：
image.png
輸出結(jié)果：
image.png
