图数据结构的两种实现方式

一、 使用矩阵实现图结构

使用一个数组放置搜有顶点； 使用一个二维数组放置所有的边， 二维数组的两个下标指示边的两个顶点：

#include <stdio.h> #include <stdlib.h> #define MAXVEX 100 #define INFINITY 65535 typedef char VertexType; typedef int EdgeType; typedef struct MGraph { VertexType vexes[MAXVEX]; EdgeType arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; }MGraph; void CreateMGraph(MGraph* G) { int i, j, k, w; scanf("%d, %d", &G->numVertexes, &G->numEdges); //建立顶点 for (k = 0; k < G->numVertexes; k++) scanf("%d", G->vexes[i]); //建立边 for (i = 0; i < G->numVertexes; i++) for (j = 0; j < G->numVertexes; j++) G->arc[i][j] = INFINITY; for (k = 0; k < G->numEdges; k++) { scanf("%d, %d, %d", &i, &j, &k); G->arc[i][j] = w; G->arc[j][i] = w; } }

二、使用数组+链表结构实现图结构

使用一个数组存储所有的顶点； 使用链表存储所有的边；

#include <stdio.h> #include <stdlib.h> #define MAXVEX 100 typedef char VertexType; typedef int EdgeType; typedef struct EdgeNode { int adjvex; EdgeType weight; EdgeNode* next; }EdgeNode; typedef struct VertexNode { VertexType data; EdgeNode* firstedge; }VertexNode, AdjList[MAXVEX]; typedef struct GraphAdjList { AdjList adjList; int numVertexes, numEdges; }GraphAdjList; void CreateAdjList(GraphAdjList* G) { scanf("%d, %d", &G->numVertexes, &G->numEdges); int i, j, k, w; EdgeNode* e = NULL; for (i = 0; i < G->numVertexes; i++) scanf(&G->adjList[i].data); for (k = 0l; k < G->numVertexes; k++) { scanf("%d，%d, %d", &i, &j, &w); e = (EdgeNode*)malloc(sizeof(EdgeNode)); e->adjvex = j; e->weight = w; e->next = G->adjList[i].firstedge; G->adjList[i].firstedge = e; e = (EdgeNode*)malloc(sizeof(EdgeNode)); e->adjvex = j; e->weight = w; e->next = G->adjList[j].firstedge; G->adjList[j].firstedge = e; } }