Đồ thị và các thuật toán – Phần phụ lục A: Thư viện Graph.h

Phần này cung cấp cho người học thư viện Graph.h bao goomg các cấu trúc dữ liệu và các thủ tục cần thiết hỗ trợ việc cài đặt các thuật toán trong giáo trình "Đồ thị và các thuật toán". Mời các bạn cùng tham khảo để biết thêm nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Đồ thị và các thuật toán – Phần phụ lục A: Thư viện Graph.h `an phu. lu.c APhˆThu. viˆ e.n Graph.hDu.´o.i d¯ˆay l`a thu. viˆe.n gˆ `om c´ac cˆa´u tr´ u. liˆe.u v`a c´ac thu˙’ tu.c cˆ uc d˜ `an thiˆe´t hˆo˜ tro.. viˆe.c c`ai d¯aˇ. tc´ac thuˆa.t to´an trong gi´ao tr`ınh./**************************************************Luu y: Tat ca cac file du lieu dung voi Thu vien nay phai duoc tao bang trinh Norton Commander.**************************************************/#if !defined(graph_h)#define graph_h#include #include #include #include /****** Phan dinh nghia cac hang *****/#define TRUE 1#define FALSE 0#define INFTY 32767#define MAXEDGES 50 // So cuc dai cac canh#define MAXVERTICES 25 // So cuc dai cac ddir nh#define MAXSTRINGS 16 // Chieu dai cuc dai xau ky tu 197 http://www.ebook.edu.vn/****** Phan dinh nghia cac kieu du lieu *****/typedef unsigned char byte;typedef byte Boolean;typedef char DataType[MAXSTRINGS+1]; // Them mot ma ket thuc chuoi/*******************************Cau truc du lieu: don lien ket*******************************/typedef struct VertexNode *AdjPointer;struct VertexNode{ byte Vertex; int Length; int Flow; AdjPointer Next;};typedef struct{ DataType Data; AdjPointer Next;} HeadNode;typedef HeadNode *HeadPointer;typedef HeadPointer ArrayOfPointer[MAXVERTICES];typedef struct QueueType *QueueNode;struct QueueType{ byte Vertex; QueueNode Next;};typedef struct{ QueueNode Head, Tail;} Queue;typedef byte Path[MAXVERTICES]; 198 http://www.ebook.edu.vntypedef byte SetOfVertices[(MAXVERTICES%8)?((MAXVERTICES/8)+1):(MAXVERTICES/8)];/***********************************Danh sach da lien ket cho cac canh***********************************/typedef struct EdgeNode *EdgePointer;struct EdgeNode{ byte Vertex[2]; EdgePointer Link[2];};typedef struct{ char Data; EdgePointer Next;} ListEdge;typedef ListEdge *ListEdgePointer;typedef ListEdgePointer ArrayOfEdge[MAXVERTICES];/***** Phan khai bao prototype ham *****/void Create(AdjPointer *List);Boolean Empty(AdjPointer List);void Push(AdjPointer *List, byte Item);void Pop(AdjPointer *List, byte *Item);void CreatQueue(Queue *Q);Boolean EmptyQueue(Queue Q);void PushQueue(Queue *Q, byte Item);void PopQueue(Queue *Q, byte *Item);Boolean EmptySet(SetOfVertices S);Boolean InSet(SetOfVertices S, byte Value);void InitSet(SetOfVertices S, byte MaxValue);void AddSet(SetOfVertices S, byte Value);void SubSet(SetOfVertices S, byte Value);void MakeV_out(char *FileName, ArrayOfPointer V_out, byte *NumVertices, 199 http://www.ebook.edu.vn Boolean Weight);void MakeV_in(char *FileName, ArrayOfPointer V_in, ArrayOfPointer V_out, byte *NumVertices);void BuildGraph(char *FileName, ArrayOfEdge E, byte *NumVertices);void DisplayV_out(ArrayOfPointer V_out, byte NumVertices, Boolean Weight);void DisplayV_in(ArrayOfPointer V_in, byte NumVertices);void DFS(ArrayOfEdge E, byte Start, SetOfVertices S);void PathTwoVertex(Path Pred, byte Start, byte Terminal);void PopHeadPtr(byte NumVertices, ArrayOfPointer V_out);/***** Phan cai dat cac ham *****/void Create(AdjPointer *List){ (*List) = NULL;}Boolean Empty(AdjPointer List){ return((List == NULL) ? TRUE : FALSE);}void Push(AdjPointer *List, byte Item){ AdjPointer TempPtr; TempPtr = (AdjPointer) malloc(sizeof(struct VertexNode)); TempPtr->Vertex = Item; TempPtr->Next = (*List); (*List) = TempPtr;}void Pop(AdjPointer *List, byte *Item){ AdjPointer TempPtr; if (Empty(*List)) { printf( Thao tac con tro khong hop le ); return; 200 http://www.ebook.edu.vn } TempPtr = (*List); (*Item) = TempPtr->Vertex; (*List) = TempPtr->Next; free(TempPtr);}void CreatQueue(Queue *Q){ (*Q).Head = NULL;}Boolean EmptyQueue(Queue Q){ return((Q.Head == NULL) ? TRUE : FALSE);}void PushQueue(Queue *Q, byte Item){ QueueNode TempPtr; TempPtr = (QueueNode) malloc(sizeof(struct QueueType)); TempPtr->Vertex = Item; TempPtr->Next = NULL; if ((*Q).Head == NULL) (*Q).Head = TempPtr; else (*Q).Tail->Next = TempPtr; (*Q).Tail = TempPtr;}void PopQueue(Queue *Q, byte *Item){ QueueNode TempPtr; if (EmptyQueue(*Q)) { printf( Thao tac con tro khong hop le ); return; } TempPtr = (*Q).Head; (*Item) = TempPtr->Vertex; (*Q).Head = TempPtr->Next; free(TempPtr); 201 http://www.ebook.edu.vn}Bo ...