(创作不易，感谢有你，你的支持，就是我前行的最大动力，如果看完对你有帮助，请留下您的足迹）
目录
图的概念（http://t.csdn.cn/CH4Bv）
图的顺序存储结构
数组（邻接矩阵）表示法
定义
建立一个顶点表和一个邻接矩阵（表示各个顶点之间关系）。
设图A=(V,E)有n个顶点，则图的邻接矩阵是一个二维数组A.Edge[n][n],
/** 图的类型枚举 */ typedef enum { DG, //有向图 0 UDG, //无向图 1 DN, //有向网 2 UDN //无向网 3 }GraphKind; /** 图的邻接矩阵存储表示 */ typedef struct { char* verTexs[100]; //顶点数组 int arcs[100][100]; //邻接矩阵（权数组） int verTexCount; //图的顶点数 int arcCount; //图的边/弧数 GraphKind kind; //图的类型 }MatrixGraph;
无向图
特点：
1 、无向图的邻接矩阵是 对称 的
2 、顶点i的度=第i行（列）中1的个数
完全图的领接矩阵中，对角元素为0，其余1
/** 使用邻接矩阵表示法创建无向图 */ int CreateUDG(MatrixGraph* G) { G->kind = UDG; //设置当前创建图的类型为无向图 printf("请输入无向图的顶点数："); scanf("%d", &G->verTexCount); printf("请输入边的数量："); scanf("%d", &G->arcCount); printf("依次输入顶点信息\n"); for (int i = 0; i < G->verTexCount; i++) { G->verTexs[i] = (char *)malloc(sizeof(char) * 10); printf("顶点%d：", i + 1); scanf("%s", G->verTexs[i]); } //初始化邻接矩阵，所有边的权值设置为0 for (int i = 0; i < G->verTexCount; i++) { for (int j = 0; j < G->verTexCount; j++) { G->arcs[i][j] = 0; } } printf("请输入顶点和邻接顶点信息，构建邻接矩阵\n"); for (int i = 0; i < G->arcCount; i++) { char * vex1 = (char *)malloc(sizeof(char) * 10); char * vex2 = (char *)malloc(sizeof(char) * 10); printf("顶点："); scanf("%s", vex1); printf("邻接点："); scanf("%s", vex2); //分别获得两个顶点在顶点数组中的坐标 int x = LocateVex(G, vex1); int y = LocateVex(G, vex2); if (x == -1 || y == -1) { return 0; } G->arcs[x][y] = 1; G->arcs[y][x] = G->arcs[x][y]; //无向图的邻接矩阵是对称的 free(vex1); free(vex2); } return 1; }
有向图
特点：
1 、 有向图的邻接矩阵 可能是不对称 的
2 、 顶点的 出度=第i行元素之和
顶点的 入度=第i 列元素之和
顶点的度= 第i 行元素之和+ 第i列元素之和
/** 使用邻接矩阵表示法创建有向图 */ int CreateDG(MatrixGraph* G) { G->kind = DG; //设置当前创建图的类型为有向图 printf("请输入有向图的顶点数："); scanf("%d", &G->verTexCount); printf("请输入边的数量："); scanf("%d", &G->arcCount); printf("依次输入顶点信息\n"); for (int i = 0; i < G->verTexCount; i++) { G->verTexs[i] = (char *)malloc(sizeof(char) * 10); printf("顶点%d：", i + 1); scanf("%s", G->verTexs[i]); } //初始化邻接矩阵，所有边的权值设置为0 for (int i = 0; i < G->verTexCount; i++) { for (int j = 0; j < G->verTexCount; j++) { G->arcs[i][j] = 0; } } printf("请输入顶点和邻接顶点信息，构建邻接矩阵\n"); for (int i = 0; i < G->arcCount; i++) { char * vex1 = (char *)malloc(sizeof(char) * 10); char * vex2 = (char *)malloc(sizeof(char) * 10); printf("顶点："); scanf("%s", vex1); printf("邻接点："); scanf("%s", vex2); //分别获得两个顶点在顶点数组中的坐标 int x = LocateVex(G, vex1); int y = LocateVex(G, vex2); if (x == -1 || y == -1) { return 0; } G->arcs[x][y] = 1; //G->arcs[y][x] = G->arcs[x][y]; //有向图的邻接矩阵有可能不对称 free(vex1); free(vex2); } return 1; }
网的邻接矩阵表示法
图的链式存储结构
邻接表表示法
定义：
指数组与链表相结合的储存方法
对每个顶点V𝑗 建立一个单链表，把与V 𝑗 有关联的边的信息链接起来，每个结点设为3个域
1 、每个单链表有一个 头结点 （设为 2个域）），存V𝒋 信息
2 、每个单链表的头结点另外用顺序存储结构存储
/** 图的类型枚举 */ typedef enum { DG, //有向图 0 UDG, //无向图 1 DN, //有向网 2 UDN //无向网 3 }GraphKind; /** 边/弧的结点 */ typedef struct node { int adjVex; //该边指向这条边邻接点的下标 struct node* nextEdge; //指向下一条边结点的指针 struct node* nextArc; //指向下一个弧结点的指针 int weight; //权重 }EdgeNode, ArcNode; /** 顶点结点 */ typedef struct vexNode { char* vex; //顶点值 EdgeNode* firstEdge; //指向第一条边的指针 ArcNode* firstArc; //指向第一条弧的指针 }VNode, AdjList[100]; /** 邻接表实现的图结构 */ typedef struct adjGraph { AdjList vexes; //顶点数组 int vexCount; //顶点数量 int edgeCount; //图的边数 int arcCount; //图的弧数 GraphKind kind; //图的类型 }AdjListGraph;
无向图;
注意：邻接表不唯一，因为各个边结点的链入顺序是任意的
TD(V𝒋 ) = 单链表中链接的结点个数
/** 返回顶点vex在顶点数组中的下标，没有找到返回-1 */ int LocateVex_AdjList(AdjListGraph* G, char* vex) { int index = -1; for (int i = 0; i < G->vexCount; i++) { if (strcmp(vex, G->vexes[i].vex) == 0) { index = i; break; } } return index; } /** 采用邻接表表示法创建无向图 */ int CreateUDG_AdjList(AdjListGraph* G) { G->kind = UDG; printf("请输入顶点数量："); scanf("%d", &G->vexCount); printf("请输入边的数量："); scanf("%d", &G->edgeCount); printf("请依次输入顶点信息\n"); for (int i = 0; i < G->vexCount; i++) { G->vexes[i].vex = (char*)malloc(sizeof(char) * 10); printf("顶点%d：", i + 1); scanf("%s", G->vexes[i].vex); //初始化邻接表，把边置空 G->vexes[i].firstEdge = NULL; } printf("请输入顶点和邻接点信息，构建邻接表\n"); for (int i = 0; i < G->edgeCount; i++) { char* vex1 = (char*)malloc(sizeof(char) * 10); char* vex2 = (char*)malloc(sizeof(char) * 10); printf("顶点："); scanf("%s", vex1); printf("邻接点："); scanf("%s", vex2); int x = LocateVex_AdjList(G, vex1); int y = LocateVex_AdjList(G, vex2); if (x == -1 || y == -1) { free(vex1); free(vex2); return 0; } EdgeNode* edgeNode = (EdgeNode*)malloc(sizeof(EdgeNode)); edgeNode->adjVex = x; edgeNode->nextEdge = G->vexes[y].firstEdge; edgeNode->weight = 0; G->vexes[y].firstEdge = edgeNode; edgeNode = (EdgeNode*)malloc(sizeof(EdgeNode)); edgeNode->adjVex = y; edgeNode->nextEdge = G->vexes[x].firstEdge; edgeNode->weight = 0; G->vexes[x].firstEdge = edgeNode; free(vex1); free(vex2); } return 1; }
有向图：
TD(V𝒋 ) = OD(V𝒋 ) + ID（V𝒋 ）
小结：
