图的存储及遍历

源代码

实现图的邻接矩阵和邻接表存储 #include<stdio.h> #include<stdlib.h> #include<malloc.h> #define INF 32767 #define MAXV 100 typedef char InfoType; typedef struct { int no; InfoType info; }VertexType; typedef struct { int edges[MAXV][MAXV]; int n, e; VertexType vexs[MAXV]; }MatGraph; typedef struct ANode { int adjvex; struct ANode *nextarc; int weight; }ArcNode; typedef struct Vnode { InfoType info; int count; ArcNode * firstarc; }VNode; typedef struct { VNode adjlist[MAXV]; int n, e; }AdjGraph; void CreateMat(MatGraph &g, int A[MAXV][MAXV], int n, int e) { int i, j; g.n = n; g.e = e; for (i = 0; i < g.n; i++) for (j = 0; j < g.n; j++) g.edges[i][j] = A[i][j]; } void DispMat(MatGraph g) { int i, j; for (i = 0; i < g.n; i++) { for (j = 0; j < g.n; j++) if (g.edges[i][j] != INF) printf("M", g.edges[i][j]); else printf("%4s", "∞"); printf("\n"); } } void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e) { int i, j; ArcNode *p; G = (AdjGraph *)malloc(sizeof(AdjGraph)); for (i = 0; i < n; i++) G->adjlist[i].firstarc = NULL; for (i = 0; i < n; i++) for (j = n - 1; j >= 0; j--) if (A[i][j] != 0 && A[i][j] != INF) { p = (ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = j; p->weight = A[i][j]; p->nextarc = G->adjlist[i].firstarc; G->adjlist[i].firstarc = p; } G->n = n; G->e = n; } void DispAdj(AdjGraph *G) { ArcNode *p; for (int i = 0; i < G->n; i++) { p = G->adjlist[i].firstarc; printf("=:", i); while (p != NULL) { printf("=[%d]->", p->adjvex, p->weight); p = p->nextarc; } printf("∧\n"); } } void DestroyAdj(AdjGraph *&G) { ArcNode *pre, *p; for (int i = 0; i < G->n; i++) { pre = G->adjlist[i].firstarc; if (pre != NULL) { p = pre->nextarc; while (p != NULL) { free(pre); pre = p; p = p->nextarc; } free(pre); } } free(G); } int main() { MatGraph g; AdjGraph *G; int A[MAXV][MAXV] = { {0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},{8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0} }; int n = 6, e = 10; CreateMat(g, A, n, e); printf("(1)图G的邻接矩阵：\n"); DispMat(g); CreateAdj(G, A, n, e); printf("(2)图G的邻接表：\n"); DispAdj(G); printf("(3)销毁图G的邻接表\n"); DestroyAdj(G); system("pause"); return 1; } 实现图的遍历算法 #include<stdio.h> #include<stdlib.h> #include<malloc.h> #define INF 32767 #define MAXV 100 typedef char InfoType; typedef struct { int no; InfoType info; }VertexType; typedef struct { int edges[MAXV][MAXV]; int n, e; VertexType vexs[MAXV]; }MatGraph; typedef struct ANode { int adjvex; struct ANode *nextarc; int weight; }ArcNode; typedef struct Vnode { InfoType info; int count; ArcNode * firstarc; }VNode; typedef struct { VNode adjlist[MAXV]; int n, e; }AdjGraph; void CreateMat(MatGraph &g, int A[MAXV][MAXV], int n, int e) { int i, j; g.n = n; g.e = e; for (i = 0; i < g.n; i++) for (j = 0; j < g.n; j++) g.edges[i][j] = A[i][j]; } void DispMat(MatGraph g) { int i, j; for (i = 0; i < g.n; i++) { for (j = 0; j < g.n; j++) if (g.edges[i][j] != INF) printf("M", g.edges[i][j]); else printf("%4s", "∞"); printf("\n"); } } void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e) { int i, j; ArcNode *p; G = (AdjGraph *)malloc(sizeof(AdjGraph)); for (i = 0; i < n; i++) G->adjlist[i].firstarc = NULL; for (i = 0; i < n; i++) for (j = n - 1; j >= 0; j--) if (A[i][j] != 0 && A[i][j] != INF) { p = (ArcNode *)malloc(sizeof(ArcNode)); p->adjvex = j; p->weight = A[i][j]; p->nextarc = G->adjlist[i].firstarc; G->adjlist[i].firstarc = p; } G->n = n; G->e = n; } void DispAdj(AdjGraph *G) { ArcNode *p; for (int i = 0; i < G->n; i++) { p = G->adjlist[i].firstarc; printf("=:", i); while (p != NULL) { printf("=[%d]->", p->adjvex, p->weight); p = p->nextarc; } printf("∧\n"); } } void DestroyAdj(AdjGraph *&G) { ArcNode *pre, *p; for (int i = 0; i < G->n; i++) { pre = G->adjlist[i].firstarc; if (pre != NULL) { p = pre->nextarc; while (p != NULL) { free(pre); pre = p; p = p->nextarc; } free(pre); } } free(G); } int visited[MAXV]; void DFS(AdjGraph *G, int v) { ArcNode *p; printf("=", v); visited[v] = 1; p = G->adjlist[v].firstarc; while (p != NULL) { if (visited[p->adjvex] == 0) DFS(G, p->adjvex); p = p->nextarc; } } void DFS1(AdjGraph *G, int v) { ArcNode *p; int St[MAXV]; int top = -1, w, x, i; for (i = 0; i < G->n; i++)visited[i] = 0; printf("=", v); visited[v] = 1; top++; St[top] = v; while (top > -1) { x = St[top]; p = G->adjlist[x].firstarc; while (p != NULL) { w = p->adjvex; if (visited[w] == 0) { printf("=", w); visited[w] = 1; top++; St[top] = w; break; } p = p->nextarc; } if (p == NULL)top--; } printf("\n"); } void BFS(AdjGraph *G, int v) { ArcNode *p; int queue[MAXV], front = 0, rear = 0; int visited[MAXV]; int w, i; for (i = 0; i < G->n; i++)visited[i] = 0; printf("=", v); visited[v] = 1; rear = (rear + 1) % MAXV; queue[rear] = v; while (front != rear) { front = (front + 1) % MAXV; w = queue[front]; p = G->adjlist[w].firstarc; while (p != NULL) { if (visited[p->adjvex] == 0) { printf("=", p->adjvex); visited[p->adjvex] = 1; rear = (rear + 1) % MAXV; queue[rear] = p->adjvex; } p = p->nextarc; } } printf("\n"); } int main() { AdjGraph *G; int A[MAXV][MAXV] = { {0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},{8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0} }; int n = 6, e = 10; CreateAdj(G, A, n, e); printf("图G的邻接表：\n"); DispAdj(G); printf("从顶点0开始的DFS（递归算法）：\n"); DFS(G, 0); printf("\n"); printf("从顶点0开始的DFS（非递归算法）：\n"); DFS1(G, 0); printf("从顶点0开始的BFS：\n"); BFS(G, 0); DestroyAdj(G); system("pause"); return 1; }

备注： 有问题可以评论，看到后我会尽力及时回复的，谢谢！