main.rar

#include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define MAX_VERTAX_SIZE 20 typedef char VerElemType; typedef char ElemType; typedef int Status; typedef struct Graph { VerElemType VertaxMatrix[MAX_VERTAX_SIZE]; int AdjacentMatrix[MAX_VERTAX_SIZE][MAX_VERTAX_SIZE]; int VertaxNum; int EageNum; }Graph; typedef struct QueueNode{ ElemType data; struct QueueNode* next; }QueueNode, *QueueNodePtr; typedef struct Queue{ QueueNodePtr front; QueueNodePtr rear; }Queue; Status InitQueue(Queue* q){ (*q).front = (QueueNodePtr)malloc(sizeof(struct QueueNode)); (*q).rear = (*q).front; (*q).rear->next = NULL; return OK; } Status EnterQueue(Queue* q, ElemType e){ QueueNodePtr n; n = (QueueNode*)malloc(sizeof(struct QueueNode)); n->data = e; n->next = q->rear->next; q->rear->next = n; q->rear = n; return OK; } Status DeleteQueue(Queue* q, ElemType* e){ QueueNodePtr p; if( q->front == q->rear ){ printf("Empty\n"); return ERROR; } p = q->front->next; *e = p->data; q->front->next = p->next; free(p); if( p == q->rear ) q->rear = q->front; return OK; } Status IsQueueEmpty(Queue q){ return q.front == q.rear ? OK : ERROR; } int LocateVertax(Graph G, VerElemType ver){ int i; for( i = 0; i < G.VertaxNum; i++ ){ if( G.VertaxMatrix[i] == ver ) return i; } return -1; } Status Create(Graph* G){ int i,j,k; VerElemType x,y; printf("Please input quantity of Vertex : \n"); scanf("%d%*c",&(*G).VertaxNum); printf("Please input quantity of Edge :\n"); scanf("%d%*c", &(G->EageNum)); printf("Please input each node name :\n"); for( i = 0; i <=G->VertaxNum; i++ ){ scanf("%c", &(G->VertaxMatrix[i])); } for( i = 0; i < G->VertaxNum; i++ ) for( j = 0; j < G->VertaxNum; j++ ) G->AdjacentMatrix[i][j] = 0; printf("Please input node pair of each edge ( format : i,j ): \n"); for( k = 0; k < G->EageNum; k++ ) { scanf("%c,%c%*c", &x,&y); i = LocateVertax(*G, x); j = LocateVertax(*G, y); G->AdjacentMatrix[i][j] = G->AdjacentMatrix[j][i] = 1; } return OK; } int FirstAdjacentVertax(Graph G, VerElemType v){ int index_v = LocateVertax(G, v); int i; for( i = 0; i < G.VertaxNum; i++ ){ if( G.AdjacentMatrix[index_v][i] == 1) return i; } return -1; } int NextAdjacentVertax(Graph G, VerElemType v, VerElemType w){ int index_v = LocateVertax(G, v); int index_w = LocateVertax(G, w); int i; for( i = index_w + 1; i < G.VertaxNum; i++ ){ if( G.AdjacentMatrix[index_v][i] == 1 ) return i; } return -1; } int visitedArray[MAX_VERTAX_SIZE]; void visit(VerElemType c){ printf("%c", c); } VerElemType GetVertaxValue(Graph G, int position){ return G.VertaxMatrix[position]; } Status DFS(Graph G, VerElemType v){ VerElemType w; visit(v); visitedArray[LocateVertax(G, v)] = 1; for(w = GetVertaxValue(G, FirstAdjacentVertax(G, v)); LocateVertax(G, w) != -1; w = GetVertaxValue(G, NextAdjacentVertax(G, v, w))) { if( visitedArray[LocateVertax(G, w)] != 1 ) DFS(G, w); } return OK; } Status DFSTraverse(Graph G){ int i; for( i = 0; i < G.VertaxNum; i++ ){ visitedArray[i] = 0; } for( i = 0; i < G.VertaxNum; i++){ if( visitedArray[i] == 0 ){ DFS(G, GetVertaxValue(G, i)); } } return OK; } Status BFSTraverse(Graph G){ int i,j; ElemType c; Queue q; InitQueue(&q); for( i = 0; i < G.VertaxNum; i++ ) visitedArray[i] = 0; for( i = 0; i < G.VertaxNum; i++ ){ if( visitedArray[i] == 0 ){ EnterQueue(&q, G.VertaxMatrix[i]); visitedArray[i] = 1; while( IsQueueEmpty(q) != OK ){ DeleteQueue(&q, &c); visit(c); for( j = FirstAdjacentVertax(G, c); j != -1; j = NextAdjacentVertax(G, c, GetVertaxValue(G, j))){ if( visitedArray[j] == 0 ){ EnterQueue(&q, GetVertaxValue(G, j)); visitedArray[j] = 1; } } } } } return 0; } int main(){ Graph G; Create(&G); printf("DFS : "); DFSTraverse(G); printf("\n"); printf("BFS : "); BFSTraverse(G); printf("\n"); return 0; }