Lí thuyết đồ thị part 10

Danh sách kề (Adjacency list) - Mỗi đỉnh của đồ thị có một danh sách các đỉnh kề nó (nghĩa là có một cạnh nối từ đỉnh này đến mỗi đỉnh đó). Trong đồ thị vô hướng, cấu trúc này có thể gây trùng lặp. Chẳng hạn nếu đỉnh 3 nằm trong danh sách của đỉnh 2 thì đỉnh 2 cũng phải có trong danh sách của đỉnh 3. Lập trình viên có thể chọn cách sử dụng phần không gian thừa, hoặc có thể liệt kê các quan hệ kề cạnh chỉ một lần. Biểu diễn dữ liệu này...
Nội dung trích xuất từ tài liệu:
Lí thuyết đồ thị part 10typedef 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 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 } 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}Boolean EmptySet(SetOfVertices S){ int i, k = (MAXVERTICES %8 ) ? ((MAXVERTICES / 8) + 1) : (MAXVERTICES / 8); for (i = 0; i < k; i++) if (S[i] != 0) return(FALSE); return(TRUE);}Boolean InSet(SetOfVertices S, byte Value){ if ((Value < 1) || (Value > MAXVERTICES)) return(FALSE); return((S[(Value - 1) / 8] & (0x80 >> ((Value - 1) % 8))) ? TRUE : FALSE);}void InitSet(SetOfVertices S, byte MaxValue){ int i; if (MaxValue>MAXVERTICES) { printf( Gia tri khong thuoc tap hop ); return; } for (i = 0; i < MaxValue; i++) S[i/8] |= 0x80 >> (i%8);}void AddSet(SetOfVertices S, byte Value){ int i; if ((Value < 1) || (Value > MAXVERTICES)) { printf( Gia tri khong thuoc tap hop ); return; } 202 S[(Value-1)/8] |= 0x80 >> ((Value-1)%8);}void SubSet(SetOfVertices S, byte Value){ if ((Value < 1) || (Value > MAXVERTICES)) { printf( Gia tri khong thuoc tap hop ); return; } S[(Value-1)/8] &= ~(0x80 >> ((Value-1)%8));}int feoln(FILE *fp){ char c; if ((c=fgetc(fp))==10) { fseek(fp, -2, 1); return(TRUE); } else if (c==EOF) return(TRUE); else { fseek(fp, -1, 1); return(FALSE); }}void freadln(FILE *fp){ char c; while (((c=fgetc(fp))!=10)&&(c!=EOF));}void MakeV_out(char *FileName, ArrayOfPointer V_out, byte *NumVertices, Boolean Weight){ 203 byte NumVert; HeadPointer HeadPtr; AdjPointer VerPtr; FILE *FileData; if ((FileData = fopen(FileName, rt)) == NULL) { printf( File khong tim thay ); return; } NumVert = 0; while (!feof(FileData)) { HeadPtr = (HeadPointer) malloc(sizeof(HeadNode)); ...