杂谈：最近清明小长假，好好的放松了一下。节前 和 节后 都有点 松懈。不好，不好。贵在坚持。加油。
图的邻接矩阵表示法是用 两个数组 来表示 图的数据结构。一个是顶点数组，另一个是邻接矩阵数组。邻接矩阵 里存放着 顶点的关系。
用邻接矩阵表示图，在 看 顶点之间 是否有边，或者 求顶点的度等操作时比较简单。但空间浪费巨大，在插入，删除 顶点 和边 操作时 需要 移动大量数据，造成不便。所以在插入删除比较多，节点数比较多的时候 不宜 使用这种结构。
下面上代码：
源代码网盘地址：点击打开链接
// MGraph2.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <climits>#include <cstring>#define INFINITY INT_MAX#define MAX_VERTEX_NUM 20enum E_State{E_State_Error = 0,E_State_Ok = 1,};enum E_Graph_Kind{DG = 0,//有向图DN,//有向网UDG,//无向图UDN,//无向网};//边（弧）单元typedef struct ArcCell{int adj;//表示顶点的关系类型，对于无权图，0，1表示是否相邻，，对于有权图，表示权值类型char * info;//边,弧其余信息.}AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//定义图struct MGraph{char vexs[MAX_VERTEX_NUM];//顶点集AdjMatrix arcs;//图的邻接矩阵int vexNum,arcNum;E_Graph_Kind kind;};int graphLocation(MGraph graph,char vex);void createDG(MGraph * graph);void createDN(MGraph * graph);void createUDG(MGraph * graph);void createUDN(MGraph * graph);void graphCreate(MGraph * graph){E_Graph_Kind kind;printf("请输入要创建的图的类型（有向图：0，有向网：1，无向图：2，无向网：3）\n");scanf("%d",&kind);switch (kind){case DG:createDG(graph);break;case DN:createDN(graph);break;case UDG:createUDG(graph);break;case UDN:createUDN(graph);break;default:break;}}//返回顶点vex的第一个邻接点char firstAdjVex(MGraph graph,char vex){int location = graphLocation(graph,vex);int i = 0;for (; i < graph.vexNum; i++){if ((graph.kind == DG || graph.kind == UDG) && graph.arcs[location][i].adj == 1){return graph.vexs[i];}else if((graph.kind == DN || graph.kind == UDN) && graph.arcs[location][i].adj != INFINITY){return graph.vexs[i];}}return ' ';}//返回顶点vex1 相对于 vex2的下一个邻接点.char nextAdjVex(MGraph graph,char vex1,char vex2){int location1 = graphLocation(graph,vex1);int location2 = graphLocation(graph,vex2);int i = location2+1;for (; i < graph.vexNum; i++){if ((graph.kind == DG || graph.kind == UDG) && graph.arcs[location1][i].adj == 1){return graph.vexs[i];}else if((graph.kind == DN || graph.kind == UDN) && graph.arcs[location1][i].adj != INFINITY){return graph.vexs[i];}}return ' ';}//查找顶点的位置int graphLocation(MGraph graph,char vex){for (int i = 0; i < graph.vexNum; i++){if (graph.vexs[i] == vex){return i;}}return -1;}//创建图 子函数//有向图void createDG(MGraph * graph){graph->kind = DG;printf("请输入顶点数，边(弧)数\n");scanf("%d%d%*c",&graph->vexNum,&graph->arcNum);//初始化邻接矩阵for (int i = 0; i < MAX_VERTEX_NUM; i++){for (int j = 0; j < MAX_VERTEX_NUM; j++){graph->arcs[i][j].adj = 0;graph->arcs[i][j].info = NULL;}}//构造顶点集printf("请输入顶点集\n");for (int i = 0; i < graph->vexNum; i++){scanf("%c",&graph->vexs[i]);}//构造顶点关系fflush(stdin);printf("请输入顶点的关系\n");for (int i = 0; i < graph->arcNum; i++){char vex1,vex2;scanf("%c%c%*c",&vex1,&vex2);int location1 = graphLocation(*graph,vex1);int location2 = graphLocation(*graph,vex2);graph->arcs[location1][location2].adj = 1;}}//有向网void createDN(MGraph * graph){graph->kind = DN;printf("请输入顶点数，边(弧)数\n");scanf("%d%d%*c",&graph->vexNum,&graph->arcNum);//初始化邻接矩阵for (int i = 0; i < MAX_VERTEX_NUM; i++){for (int j = 0; j < MAX_VERTEX_NUM; j++){graph->arcs[i][j].adj = INFINITY;graph->arcs[i][j].info = NULL;}}//构造顶点集printf("请输入顶点集\n");for (int i = 0; i < graph->vexNum; i++){scanf("%c",&graph->vexs[i]);}//构造顶点关系fflush(stdin);printf("请输入顶点的关系\n");for (int i = 0; i < graph->arcNum; i++){char vex1,vex2;int weight;scanf("%c%c%d%*c",&vex1,&vex2,&weight);int location1 = graphLocation(*graph,vex1);int location2 = graphLocation(*graph,vex2);graph->arcs[location1][location2].adj = weight;}}//无向图void createUDG(MGraph * graph){graph->kind = UDG;printf("请输入顶点数，边(弧)数\n");scanf("%d%d%*c",&graph->vexNum,&graph->arcNum);//初始化邻接矩阵for (int i = 0; i < MAX_VERTEX_NUM; i++){for (int j = 0; j < MAX_VERTEX_NUM; j++){graph->arcs[i][j].adj = 0;graph->arcs[i][j].info = NULL;}}//构造顶点集printf("请输入顶点集\n");for (int i = 0; i < graph->vexNum; i++){scanf("%c",&graph->vexs[i]);}fflush(stdin);//构造顶点关系printf("请输入顶点的关系\n");for (int i = 0; i < graph->arcNum; i++){char vex1,vex2;scanf("%c%c%*c",&vex1,&vex2);int location1 = graphLocation(*graph,vex1);int location2 = graphLocation(*graph,vex2);graph->arcs[location1][location2].adj = graph->arcs[location2][location1].adj = 1;}}//无向网void createUDN(MGraph * graph){graph->kind = UDN;printf("请输入顶点数，边(弧)数\n");scanf("%d%d%*c",&graph->vexNum,&graph->arcNum);//初始化邻接矩阵for (int i = 0; i < MAX_VERTEX_NUM; i++){for (int j = 0; j < MAX_VERTEX_NUM; j++){graph->arcs[i][j].adj = INFINITY;graph->arcs[i][j].info = NULL;}}//构造顶点集printf("请输入顶点集\n");for (int i = 0; i < graph->vexNum; i++){scanf("%c",&graph->vexs[i]);}//构造顶点关系fflush(stdin);printf("请输入顶点的关系\n");for (int i = 0; i < graph->arcNum; i++){char vex1,vex2;int weight;scanf("%c%c%d%*c",&vex1,&vex2,&weight);int location1 = graphLocation(*graph,vex1);int location2 = graphLocation(*graph,vex2);graph->arcs[location1][location2].adj =graph->arcs[location2][location1].adj = weight;}}//查看顶点数据之间是否相邻bool graphIsAdj(MGraph graph,char vex1,char vex2){E_Graph_Kind kind = graph.kind;int weight = (kind == DG || kind == UDG) ? 0 : INFINITY;int location1 = graphLocation(graph,vex1);int location2 = graphLocation(graph,vex2);return graph.arcs[location1][location2].adj != weight ? true : false;}int graphDegree(MGraph graph,char vex){int location = graphLocation(graph,vex);E_Graph_Kind kind = graph.kind;int weight = (kind == DG || kind == UDG) ? 0 : INFINITY;int degree = 0;for (int i = 0; i < graph.vexNum; i++){//计算行if (graph.arcs[location][i].adj != weight){degree++;}}for (int i = 0; i < graph.vexNum; i++){//计算列if (graph.arcs[i][location].adj != weight){degree++;}}if (kind == UDG || kind == UDN){degree /= 2;}return degree;}//当有以下操作时，不适合 用邻接矩阵的方式来处理。void insertVex(MGraph * graph,char vex){graph->vexs[graph->vexNum++] = vex;}//需要移动很多元素.void deleteVex(MGraph * graph,char vex){int location = graphLocation(*graph,vex);//删除顶点集for (int i = location+1; i < graph->vexNum; i++){graph->vexs[i-1] = graph->vexs[i];}//计算删除的边（弧）数graph->arcNum -= graphDegree(*graph,vex);//删除边（弧）//vex下面的上移for (int i = location+1; i < graph->vexNum; i++){for (int j = 0; j < graph->vexNum; j++){graph->arcs[i-1][j] = graph->arcs[i][j];}}//vex右边的左移for (int i = location + 1; i < graph->vexNum; i++){for (int j = 0; j < graph->vexNum; j++){graph->arcs[j][i-1] = graph->arcs[j][i];}}//清理垃圾数据(第vexNum行 和 第vexNum列）int maxVexNum = graph->vexNum;E_Graph_Kind kind = graph->kind;int weight = (kind == DG || kind == UDG) ? 0 : INFINITY;for (int i = 0; i < maxVexNum; i++){graph->arcs[maxVexNum-1][i].adj = weight;graph->arcs[i][maxVexNum-1].adj = weight;}graph->vexNum–;}//插入边（弧）void insertArc(MGraph * graph,char vex1,char vex2,int weight){int location1 = graphLocation(*graph,vex1);int location2 = graphLocation(*graph,vex2);E_Graph_Kind kind = graph->kind;if (kind == DG || kind == UDG){graph->arcs[location1][location2].adj = 1;}else{graph->arcs[location1][location2].adj = weight;}if (kind == UDG || kind == UDN){graph->arcs[location2][location1].adj = graph->arcs[location1][location2].adj;}}//删除边（弧）void deleteArc(MGraph * graph,char vex1,char vex2){int location1 = graphLocation(*graph,vex1);int location2 = graphLocation(*graph,vex2);E_Graph_Kind kind = graph->kind;if (kind == DG || kind == UDG){graph->arcs[location1][location2].adj = 0;}else{graph->arcs[location1][location2].adj = INFINITY;}if (kind == UDG || kind == UDN){graph->arcs[location2][location1].adj = graph->arcs[location1][location2].adj;}}void printAdjMatrix(MGraph graph){for (int i = 0; i < graph.vexNum; i++){for (int j = 0; j < graph.vexNum; j++){printf("%d\t",graph.arcs[i][j]);}printf("\n");}}int _tmain(int argc, _TCHAR* argv[]){MGraph graph;graphCreate(&graph);printAdjMatrix(graph);printf("图 有 %d个顶点,%d个边（弧）\n",graph.vexNum,graph.arcNum);char * isAdj = graphIsAdj(graph,'a','d')? "相邻":"不相邻";int degree = graphDegree(graph,'c');printf("a 和 d %s,c的度数是：%d\n",isAdj,degree);char vexFirst = firstAdjVex(graph,'c');char vexNext = nextAdjVex(graph,'c','a');printf("c的第一个邻接点是%c\nc的相对于a的下一个邻接点是%c\n",vexFirst,vexNext);insertVex(&graph,'e');printf("插入节点e之后：\n");printAdjMatrix(graph);printf("插入边(e,d)之后:\n");insertArc(&graph,'e','d',1);printAdjMatrix(graph);printf("删除顶点c之后：\n");deleteVex(&graph,'c');printAdjMatrix(graph);deleteArc(&graph,'a','b');printf("删除弧(a,b)之后：\n");printAdjMatrix(graph);return 0;}运行截图：
别人失去了信心，他却下决心实现自己的目标。
