文章目录

一、图结构介绍二、邻接矩阵三、代码实现    

一、图结构介绍

图的定义与术语（必看）：http://www.360doc.com/content/17/0714/10/17799864_671231489.shtml

 

二、邻接矩阵

  简单理解就是用一个二维矩阵（二维数组）来存储。按照标记来查看此边是否存在。邻接矩阵为每一种情况都做好了空间预存。

  适用场景：使用于稠密的图，可以快速定位到指定的边，但是如果是稀疏的图，会比较浪费空间。

 

三、代码实现

matrixGraph.h：

#ifndef __GRAPH__H #define __GRAPH__H /*邻接矩阵*/ #define MAX_VERTEX 100 /*最大顶点数*/ typedef char vertexType; /*顶点类型（如a,b,c则是char类型）*/ typedef int weightType; /*权重*/ typedef struct _matrixGraph { vertexType vertex[MAX_VERTEX]; weightType martix[MAX_VERTEX][MAX_VERTEX]; int numEages, numVertex; }matrixGraph; #endif

matrixGraph.c

#include <stdio.h> include <stdlib.h> include "graph.h" include <string.h> #define OrthogonalList #ifdef MATRIX int locateGraph(matrixGraph *graph, vertexType c) { int i; for (i = 0; i < graph->numVertex; i++) { if (graph->vertex[i] == c) return i; } return -1; } int printfGraph(matrixGraph *graph) { int i, j; for(i = 0; i < graph->numVertex; i ++) { for (j = 0; j < graph->numVertex; j ++) { printf("%d ", graph->martix[i][j]); } printf("\n"); } return 0; } /*创建邻接矩阵*/ int crateMatrixGraph(matrixGraph *graph) { int i, j, k, w; vertexType x,y; printf("input numEages:"); /*输入边数与顶点数量 int类型*/ scanf("%d", &(graph->numEages)); printf("input numVertex:"); scanf("%d", &(graph->numVertex)); if (graph->numVertex > MAX_VERTEX) return -1; for (i = 0; i < graph->numVertex; i++) { /*输入顶点*/ printf("input vertex:"); graph->vertex[i] = getchar(); while(graph->vertex[i] == '\n') graph->vertex[i] = getchar(); } for (i = 0; i < graph->numVertex; i ++) { /*初始化矩阵*/ for (j = 0; j < graph->numVertex; j ++) graph->martix[i][j] = 0; } getchar(); for (k = 0; k < graph->numEages; k ++) { printf("input vertex and weight:\n"); /*输入边的两个顶点和权重*/ // 顶点x x = getchar(); while(x == '\n') x = getchar(); // 顶点y y = getchar(); while(y == '\n') y = getchar(); // 权重w scanf("%d", &w); //scanf("%c,%c,%d", &x, &y, &w); i = locateGraph(graph, x); // 定位x在数组中的位置 j = locateGraph(graph, y); // ... if (i == -1 || j == -1) { printf("input error\n"); k --; continue; } /*无向图 对称矩阵*/ graph->martix[i][j] = w; graph->martix[j][i] = graph->martix[i][j]; } return 0; } #endif

              关注公众号"小败日记"，搬砖过程遇到的问题，大家一起探讨，资源共享