137 lines
2.8 KiB
Plaintext
137 lines
2.8 KiB
Plaintext
/* file name: topologicalSort.c */
|
|
/* 拓樸排序 */
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#define MAX_V 100 /* 最大節點數 */
|
|
#define TRUE 1
|
|
#define FALSE 0
|
|
|
|
/*定義資料結構*/
|
|
typedef struct node_tag {
|
|
int vertex;
|
|
struct node_tag *link;
|
|
} Node;
|
|
|
|
Node *adjlist[MAX_V+1]; /* 宣告相鄰串列 */
|
|
int visited[MAX_V+1]; /* 記錄頂點是否已拜訪 */
|
|
int Top_order[MAX_V+1];
|
|
int N;
|
|
int place;
|
|
|
|
|
|
void build_adjlist(void);
|
|
void show_adjlist(void);
|
|
void topological(void);
|
|
void top_sort(int);
|
|
Node *searchlast(Node *);
|
|
|
|
int main()
|
|
{
|
|
int i;
|
|
|
|
build_adjlist(); /* 以相鄰串列表示圖形 */
|
|
show_adjlist(); /* 顯示串列之資料 */
|
|
topological(); /* 圖形之蹤向優先搜尋，以頂點 1 為啟始頂點 */
|
|
puts("\n------Topological sort------");
|
|
for (i = 0; i < N; i++)
|
|
printf("V%d ", Top_order[i]);
|
|
printf("\n");
|
|
return 0;
|
|
}
|
|
|
|
void build_adjlist()
|
|
{
|
|
FILE *fptr;
|
|
Node *node, *lastnode;
|
|
int vi, vj;
|
|
|
|
fptr = fopen("topologicalSort.dat", "r");
|
|
if (fptr == NULL) {
|
|
perror("topologicalSort.dat");
|
|
exit(0);
|
|
}
|
|
|
|
/* 讀取節點總數 */
|
|
fscanf(fptr, "%d", &N);
|
|
for (vi = 1; vi <= N; vi++) {
|
|
/* 設定陣列及各串列啟始值 */
|
|
adjlist[vi] = (Node *)malloc(sizeof(Node));
|
|
adjlist[vi]->vertex = vi;
|
|
adjlist[vi]->link = NULL;
|
|
}
|
|
|
|
/* 讀取節點資料 */
|
|
while (fscanf(fptr,"%d %d",&vi,&vj) != EOF) {
|
|
node = (Node *)malloc(sizeof(Node));
|
|
node->vertex = vj;
|
|
node->link = NULL;
|
|
if (adjlist[vi]->link == NULL)
|
|
adjlist[vi]->link = node;
|
|
else {
|
|
lastnode = searchlast(adjlist[vi]);
|
|
lastnode->link = node;
|
|
}
|
|
}
|
|
fclose(fptr);
|
|
}
|
|
|
|
/* 顯示各相鄰串列之資料 */
|
|
void show_adjlist()
|
|
{
|
|
int v;
|
|
Node *ptr;
|
|
|
|
puts("Head adjacency nodes");
|
|
puts("--------------------------");
|
|
for (v = 1; v <= N; v++) {
|
|
printf("V%d ",adjlist[v]->vertex);
|
|
ptr = adjlist[v]->link;
|
|
while (ptr != NULL) {
|
|
printf("--> V%d ",ptr->vertex);
|
|
ptr = ptr->link;
|
|
}
|
|
printf("\n");
|
|
}
|
|
}
|
|
|
|
/* 圖形之蹤向優先搜尋 */
|
|
void topological()
|
|
{
|
|
int v;
|
|
|
|
for (v = 1; v <= N; v++)
|
|
visited[v] = FALSE;
|
|
place = N;
|
|
for (v = 1; v <= N; v++)
|
|
if (!visited[v])
|
|
top_sort(v);
|
|
}
|
|
|
|
void top_sort(int k)
|
|
{
|
|
Node *ptr;
|
|
int w;
|
|
|
|
visited[k] = TRUE; /* 設定 v 頂點為已拜訪過 */
|
|
ptr = adjlist[k]->link; /* 拜訪 v 相鄰頂點 */
|
|
while (ptr != NULL) {
|
|
w = ptr->vertex; /* w 為 v 的立即後繼者 */
|
|
if (!visited[w])
|
|
top_sort(w);
|
|
ptr = ptr->link;
|
|
}
|
|
Top_order[--place] = k;
|
|
}
|
|
|
|
/* 搜尋串列最後節點函數 */
|
|
Node *searchlast(Node *linklist)
|
|
{
|
|
Node *ptr;
|
|
|
|
ptr = linklist;
|
|
while (ptr->link != NULL)
|
|
ptr = ptr->link;
|
|
return ptr;
|
|
}
|