一、简介
图状结构是一种比树形结构更复杂的非线性结构。在树形结构中，结点间具有分支层次关系，每一层上的结点只能和上一层的至多一个结点相关，但可能和下一层的多个结点相关。而在图状结构中，任意两个结点之间都可能相关，即结点之间的邻接关系可以是任意的。因此，图是 比树更一般、更复杂的非线性结构，常被用于描述各种复杂的数据对象，在自然科学、社会科学和人文科学等许多领域有着非常广泛的应用。
1.1 定义和术语
（1）定语：
图（Graph）是由非空的顶点集合和一个描述顶点之间的关系——边（或者弧）的集合组成的，其形式化定义为：G=(V,E)、V={v1|v1包含data object}、E={(v1,vj)|(vi,vj 包含V^P(vj,vj)。其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，集合E中P(vi,vj)表示顶点vi和顶点vj之间有一条直接连线，即偶对(v1,vj）表示一条边。如：G2=(V2,E2)、V2={v1,v2,v3,v4}、E2={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}。
（2）术语:
1、无向图：在一个图中，如果任意两个顶点构成的偶对(vi,vj）包含E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图。
2、有向图：在一个图中，如果任意两个顶点构成的偶对<vj,vj>包含E是有序的（有序对常常用尖括号“<>”表示），即顶点之间的连线是有方向的，则称该图为有向图。
3、顶点、边、弧、弧头、弧尾：在图中，数据元素vi称为顶点（Vertex）；（vj，vj）表示在顶点vi和顶点vj之间有一条直接连线。如果是在无向图中，则称这条连线为边；如果是在有向图中，一般称这条连线为弧。边用顶点的无序偶对（vi，vj）来表示，称顶点vi和vj互为邻接点，边<vi,vj>依附于顶点vi与顶点vj；弧用顶点的有序偶对<vi,vj>来表示，有序偶对的第一个节点vi被称为始点(或弧尾），在图中就是不带箭头的一端；有序偶对的第二个节点vj被称为终点(或弧头），在图中就是带箭头的一端。
4、无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。可以证明，在一个含有n个顶点的无向完全图中，有n（n-1）/2条边。
5、有向完全图：在有一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。在一个含有n个顶点的有向完全图中，有n(n-1)条边。
6、顶点的度、入度、出度：顶点的度（Degree）是指依附于某顶点v的边数，通常记为TD(v)。顶点v的入度是指以顶点v为终点的弧的数目，记为ID(V)；出度是指以顶点v为始点的弧的数目，记为OD(V)。有TD(V)=ID(v)+OD(v)。
7、边的权、网：与边有关的数据信息称为权(Weight)。在实际应用中，权值可以有某种含义。例如，在一个反映城市交通线路的图中，边上的权值可以表示该条线路的长度或等级；对于一个电子线路图，边上的权值可以表示两个端点之间的电阻、电流或电压值；对于反映工程进度的图而言，边上的权值可以表示从前一个工程到后一个工程所需要的时间或其他代价等。边上带权的图称为网或网络（network）。
8、路径、路径长度：顶点vp到顶点vq之间的路径（path）是指顶点序列vp、vi1、vi2、···、vim、vq。其中，（vp，vi1）、（vi1，vi2）、···、（vim，vq）分别为图中的边。路径上边的数目称为路径长度。
9、简单路径、回路、简单回路：序列中顶点不重复出现的路径称为简单路径。路径中第一个顶点与最后一个顶点相同的 路径称为回路或环（Cycle）。除第一个顶点与最后一个顶点之外，其他顶点不重复出现的回路称为简单回路，或者简单环。
10、子图：对于图G=（V，E），G'=（V',E'），若存在 V'是V的子集， E'是E的子集，则称图 G'是G的的一个子图。
11、连通、连通图、连通分量：在无向图中，如果从一个顶点vi到另一个顶点vj(i=!j)存在路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。无向图的极大连通子图称为连通分量，极大连通子图是指在保证连通与子图的条件下，包含原图中所有的顶点与边。 如下图：
12、强连通图、强连通分量：对于有向图来说，若图中任意一对顶点vi和vj（i=!j）均存在从一个顶点vi到另一个顶点vj和从vj到vi的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量，极大强连通子图的含义同上。
13、生成树：所谓连通图G的生成树，是G的包含其全部n个顶点的一个极小连通子图，所谓极小连通子图是指在包含所有顶点且保证连通的前提下尽可能少地包含原图中的边。生成树必定包含且仅包含连通图G的n-1条边。在生成树中添加任意一条属于原图中的边必定会产生回路，因为新添加的边使其所依附的两个顶点之间有了第二条路径。若生成树中减少任意一条边，则必然成为非连通的。
14、生成森林：在非连通图中，由每个连通分量都可得到一个极小连通子图，即一棵生成树。这些连通分量的生成树就组成了一个非连通图的生成森林。
二、存储结构
将上图存储到计算机中，请设计一个数据结构并将其合理存储起来？
2.1 邻接矩阵
所谓邻接矩阵（Adjacency Matrix）的存储结构，就是用一维数组存储图中的顶点信息，用矩阵表示图中各顶点的信息，用矩阵表示图中各顶点的信息，用矩阵表示图中各顶点之间的邻接关系。假设图G=(V,E)有n个确定的顶点，即V ={v0,v1，···，vn-1}，则表示G中各顶点相邻关系的矩阵为一个n×n的矩阵，矩阵的元素为：
A[i][j]={1,若(vi,vj)或<vi,vj>是E(G)中的边 ；2，若(vi,vj）或<vi,vj>不是E(G)中的边。
若G是网，则邻接矩阵可定义为：
A[i][j]={wij,若(vi,vj)或<vi,vj>是E(G)中的边 ；0或&，若(vi,vj）或<vi,vj>不是E(G)中的边。
其中，wij表示边(Vi,vj)或<vi,vj>上的权值；表示一个计算机允许的、大于所有边上权值的数。
（1）无向图的邻接矩阵一定是一个对称矩阵。因此，在具体存放邻接矩阵时只需存放上或下三角矩阵的元素即可。
（2）对于无向图，邻接矩阵的第i行或第i列非零元素或非&元素的个数正好是第i个顶点的度TD(vi)。
（3）对于有向图，邻接矩阵的第i行货第i列非零元素或非&元素的个数正好是第i个顶点的出度OD(vi)或如度ID(vi)。
（4）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连；但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。
在实际应用邻接矩阵存储图时，除了用一个二维数组存储用于表示顶点间相邻关系的邻接矩阵外，还需用一个一维数组来存储顶点信息，另外，还有图的顶点树和边树。故可将其形式描述如下：
#define MAXVEX 100 /* 最大顶点数，应由用户定义 */
#define INFINITYC 0
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */
typedef struct{
VertexType vexs[MAXVEX];/*定点表*/
EdgeType arc[MAXVEX][MAXVEX];/*邻接矩阵，可看出边表*/
int numNodes,numEdges;/*图中的顶点数和边数*/
}MYGraph;
void CreateMGraph(MGraph *G){
int i,j,k,w;
printf("输入顶点数和边数:\n");
//1. 输入顶点数/边数
scanf("%d,%d",&G->numNodes,&G->numEdges);
printf("顶点数:%d,边数:%d\n",G->numNodes,G->numEdges);
//2.输入顶点信息/顶点表
for(i = 0; i<= G->numNodes;i++)
scanf("%c",&G->vexs[I]);
//3.初始化邻接矩阵
for(i = 0; i < G->numNodes;i++)
for(j = 0; j < G->numNodes;j++)
G->arc[i][j] = INFINITYC;
//4.输入边表信息
for(k = 0; k < G->numEdges;k++){
printf("输入边(vi,vj)上的下标i,下标j,权w\n");
scanf("%d,%d,%d",&i,&j,&w);
G->arc[i][j] = w;
//如果无向图,矩阵对称;
G->arc[j][i] = G->arc[i][j];
}
/*5.打印邻接矩阵*/
for (int i = 0; i < G->numNodes; i++) {
printf("\n");
for (int j = 0; j < G->numNodes; j++) {
printf("%d ",G->arc[i][j]);
}
}
printf("\n");
}
2.2 邻接表
邻接表（Adjacency List）是图的一种顺序存储于链式存储结合的存储方法。邻接表表示法类似于树的孩子链表表示法。就是对于图G中的每个顶点vi，将所有邻接于vi的顶点vj链成一个单链表，这个单链表就称为顶点vi的邻接表，再将所有顶点的邻接表表头放到数组中，就构成了图邻接表。
在邻接表表示中有两种结点结构：一种是顶点表的结点结构，它由顶点域（vertex）和指向第一条邻接边的指针域（firstedge）构成。另一种是边表即邻接表结点，它由邻接点域（adjvex）和指向下一条邻接边的指针域（next）构成。对于网的边表需再增设一个存储边上的信息（如权值等）的域（info）。
//邻接表的节点
typedef struct Node{
int adj_vex_inex;//弧头下标，也就是被指向的下标
Element data;//权重值
struct Node * next;//边指针
}EdgeNode;
//顶点节点表
typedef struct VNode
{
Element data;//顶点的权重
EdgeNode * next;//顶点的下一个节点的指针
}VertexNode;
//总图的一些信息
typedef struct MyGraph
{
VertexNode adjlist[M];//顶点表
int arc_num;//边的个数,
int node_nume;//节点个数
BOOL is_directed;//是不是有向图
}Graph,*GraphLink;
void creatGraph(GraphLink * g){
//1,顶点，边，是否是有向图
printf("输入顶点数目，边数和有向？：\n");
scanf("%d %d %d",&(*g)->node_num,&(*g)->arc_num,&(*g)->is_directed)
//顶点表
printf("输入顶点信息：\n");
for(int i = 0;i<(*g)->node_num;i++)
{
getchar();
scanf("%c",&(*g)->adjlist[i].data);
(*g)->adjlist[i].firstedge = NULL;
}
//输入边信息
printf("输入边信息：\n");
int i,j;
EdgeNode * p;
for(int k = 0;k<(*g)->arc_num;k++)
{
getchar();
scanf("%d %d",&i,&j);
//①新创建一个节点
p = (EdgeNode*)malloc(sizeof(EdgeNode));
//②弧头的下标
p -> adj_vex_index = j;
//③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
p->next = (*g)->adjlist[i].firstedge;
//④将顶点数组[i].firstedge 设置为p
(*g)->adjlist[i].firstedge = p;
//j->i 如果是无向图
if(!(*g)->is_directed)
{
// j -----> i
//①新建一个节点
p = (EdgeNode *)malloc(sizeof(EdgeNode));
//②弧头的下标i
p->adj_vex_index = i;
//③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
p->next = (*g)->adjlist[j].firstedge;
//④将顶点数组[i].firstedge 设置为p
(*g)->adjlist[j].firstedge = p;
}
}
}
