原文链接（点击原文链接获取更多学习干货）：
?http://blog.bools.cn/archives/897
一、什么是图？
图是地图的图吗？我拿着地图想去哪就去哪吗？是滴，图是多对多的情况，对于去一个地方有不同的路径到达，两个地方往返都有不同的路径。图是由顶点和边或弧两部分组成的，可以分两个结构来分别存储。另外图上的任何顶点都可以被看作是第一个顶点，任一顶点的邻接点之间也不存在次序关系。图分为无向图、有向图、网图。
二、常用的图--邻接矩阵、邻接表
1、邻接矩阵
- 原理：顶点用一维数组来存储，边或弧用二维数组存储。
typedef struct
{
VertexType vexs[MAXVEX]; /* 顶点表 */
EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
int numNodes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;- 画图分析：
邻接矩阵（无向图）
相邻两个顶点有边则存储1，否则存储0
求法：
问：要判定任意两个顶点是否有无边
答：判断相应数组存储的是否为1
问：要知道某个顶点的度
答：这个顶点Vi在邻接矩阵中第i行（第i列）的元素之和
问：要知道顶点Vi的所有邻接点
答：将邻接矩阵中第i行元素遍历，arc[i][j]为1就是邻接点
?邻接矩阵（有向图）
有向图要考虑入度和出度，入度是第Vi列的各数之和，出度是第Vi行的各数之和。
邻接矩阵（网图）
每条边上带有权的图叫网图，“∞”表示一个计算机允许的、大于所有边上权值的值。
?邻接矩阵建立的代码
#include <stdio.h>
#define MAXVEX 100 /* 最大顶点数，应由用户定义 */
#define INFINITY 65535
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct
{
VertexType vexs[MAXVEX]; /* 顶点表 */
EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
int numNodes, numEdges; /* 图中当前的顶点数和边数 */
}MGraph;
/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph *G)
{
int i,j,k,w;
printf("输入顶点数和边数:\n");
scanf("%d,%d",&G->numNodes,&G->numEdges); /* 输入顶点数和边数 */
for(i = 0;i <G->numNodes;i++) /* 读入顶点信息,建立顶点表 */
scanf(&G->vexs[i]);
for(i = 0;i <G->numNodes;i++)
for(j = 0;j <G->numNodes;j++)
G->arc[i][j]=INFINITY; /* 邻接矩阵初始化 */
for(k = 0;k <G->numEdges;k++) /* 读入numEdges条边，建立邻接矩阵 */
{
printf("输入边(vi,vj)上的下标i，下标j和权w:\n");
scanf("%d,%d,%d",&i,&j,&w); /* 输入边(vi,vj)上的权w */
G->arc[i][j]=w;
G->arc[j][i]= G->arc[i][j]; /* 因为是无向图，矩阵对称 */
}
}
int main(void)
{
MGraph G;
CreateMGraph(&G);
return 0;
}2、邻接表
邻接表是数组与链表结合的存储结构，因为邻接矩阵对边数相对顶点较少的图，存在对存储空间的极大浪费，所以用邻接表更加优化。?
邻接表（无向图）
?邻接表（有向图）
把顶点当弧尾建立的邻接表，表示每个顶点的出度。
逆邻接表
为了便于确定顶点的入度或以顶点为弧头的弧，可以建立一个有向图的逆邻接表
邻接表（网图）
对于带权值的网图，可以在边表结点定义中再增加一个数据域来存储权值
?创建邻接表的代码
#include <stdio.h>
#define MAXVEX 100 /* 最大顶点数,应由用户定义 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct EdgeNode /* 边表结点 */
{
int adjvex; /* 邻接点域,存储该顶点对应的下标 */
EdgeType info; /* 用于存储权值,对于非网图可以不需要 */
struct EdgeNode *next; /* 链域,指向下一个邻接点 */
}EdgeNode;
typedef struct VertexNode /* 顶点表结点 */
{
VertexType data; /* 顶点域,存储顶点信息 */
EdgeNode *firstedge;/* 边表头指针 */
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numNodes,numEdges; /* 图中当前顶点数和边数 */
}GraphAdjList;
/* 建立图的邻接表结构 */
void CreateALGraph(GraphAdjList *G)
{
int i,j,k;
EdgeNode *e;
printf("输入顶点数和边数:\n");
scanf("%d,%d",&G->numNodes,&G->numEdges); /* 输入顶点数和边数 */
for(i = 0;i < G->numNodes;i++) /* 读入顶点信息,建立顶点表 */
{
scanf(&G->adjList[i].data); /* 输入顶点信息 */
G->adjList[i].firstedge=NULL; /* 将边表置为空表 */
}
for(k = 0;k < G->numEdges;k++)/* 建立边表 */
{
printf("输入边(vi,vj)上的顶点序号:\n");
scanf("%d,%d",&i,&j); /* 输入边(vi,vj)上的顶点序号 */
e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */
e->adjvex=j; /* 邻接序号为j */
e->next=G->adjList[i].firstedge; /* 将e的指针指向当前顶点上指向的结点 */
G->adjList[i].firstedge=e; /* 将当前顶点的指针指向e */
e=(EdgeNode *)malloc(sizeof(EdgeNode)); /* 向内存申请空间,生成边表结点 */
e->adjvex=i; /* 邻接序号为i */
e->next=G->adjList[j].firstedge; /* 将e的指针指向当前顶点上指向的结点 */
G->adjList[j].firstedge=e; /* 将当前顶点的指针指向e */
}
}
int main(void)
{
GraphAdjList G;
CreateALGraph(&G);
return 0;
}
欢迎关注技术公众号，获取更多硬件学习干货！
我们能为你提供什么？
技术辅导：C++、Java、嵌入式软件/硬件
项目辅导：软件/硬件项目、大厂实训项目
就业辅导：就业全流程辅导、技术创业支持
对接企业HR：培养输送优质性人才