資料結構C語言版_拓撲排序
資料結構C語言版_拓撲排序
#include
#include
// 輸出有向圖的一個拓撲序列。實作算法7.12的程式
// 圖的鄰接表存儲表示
#define MAX_NAME 3// 頂點字元串的最大長度+1
#define MAX_VERTEX_NUM 20
typedef int InfoType;// 存放網的權值
typedef char VertexType[MAX_NAME];// 字元串類型
typedef enum{DG,DN,AG,AN}GraphKind; // {有向圖,有向網,無向圖,無向網}
typedef struct ArcNode
{
int adjvex;// 該弧所指向的頂點的位置
struct ArcNode *nextarc;// 指向下一條弧的指針
InfoType *info;// 網的權值指針)
}ArcNode;// 表結點
typedef struct VNode
{
VertexType data;// 頂點資訊
ArcNode *firstarc;// 第一個表結點的位址,指向第一條依附該頂點的弧的指針
}VNode,AdjList[MAX_VERTEX_NUM];// 頭結點
typedef struct
{
AdjList vertices;
int vexnum,arcnum;// 圖的目前頂點數和弧數
int kind;// 圖的種類标志
}ALGraph;
// 若G中存在頂點u,則傳回該頂點在圖中位置;否則傳回-1。
int LocateVex(ALGraph G,VertexType u)
{
int i;
for(i=0;i
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
// 采用鄰接表存儲結構,構造沒有相關資訊的圖G(用一個函數構造4種圖)。
int CreateGraph(ALGraph *G)
{
int i,j,k;
int w;// 權值
VertexType va,vb;
ArcNode *p;
printf("請輸入圖的類型(有向圖:0,有向網:1,無向圖:2,無向網:3): ");
scanf("%d",&(*G).kind);
printf("請輸入圖的頂點數和邊數:(空格)\n");
scanf("%d%d", &(*G).vexnum, &(*G).arcnum);
printf("請輸入%d個頂點的值(
for(i = 0; i < (*G).vexnum; ++i)// 構造頂點向量
{
scanf("%s", (*G).vertices[i].data);
(*G).vertices[i].firstarc = NULL;
}
if((*G).kind == 1 || (*G).kind == 3) // 網
printf("請順序輸入每條弧(邊)的權值、弧尾和弧頭(以空格作為間隔):\n");
else // 圖
printf("請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):\n");
for(k = 0;k < (*G).arcnum; ++k)// 構造表結點連結清單
{
if((*G).kind==1||(*G).kind==3) // 網
scanf("%d%s%s",&w,va,vb);
else// 圖
scanf("%s%s",va,vb);
i = LocateVex(*G,va); // 弧尾
j = LocateVex(*G,vb); // 弧頭
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
if((*G).kind == 1 || (*G).kind == 3) // 網
{
p->info = (int *)malloc(sizeof(int));
*(p->info) = w;
}
else
p->info = NULL; // 圖
p->nextarc = (*G).vertices[i].firstarc;