（一） 相关知识点

图（graph）：图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中的顶点的集合，E是图G中边的集合，E可以为空集。

数据结构形式化定义：

G = ( V , E )        其中 V = { x | x dataobject }        E ={VR}              

VR={<x,y>| p(x,y) ∩ ( x , y∈V ) }    

VR是两顶点间的关系的集合，即边的集合。

顶点(Vertex)：图中的数据元素。线性表中数据元素叫元素，树中数据元素叫结点。

    端点和邻接点： 在一个无向图中，若存在一条边<vi,vj>, 则称vi,vj为该边的两个端点,并称它们互为邻结点。

   起点和终点 ：在一个有向图中，若存在一条边<vi,vj>, 则称该边是顶点vi的一条出边， 是vj的一条入边，称vi是起始端点（或起点），称vj是终止端点（或终点）, 并称它们互为邻结点.

边：顶点之间的逻辑关系用边来表示，边集可以是空的。

无向边(Edge)：若顶点V1到V2之间的边没有方向，则称这条边为无向边。

  边和顶点的关系：

      设n为顶点数，e为边或弧的条数    对无向图有：0 ≤ e ≤  n(n-1)/2        有向图有：0≤ e ≤ n(n-1)

无向图(Undirected graphs)：图中任意两个顶点之间的边都是无向边。 （A,D）=（D,A）

      对于无向图G来说，G1=（V1,{E1}），其中顶点集合V1={A,B,C,D}；边集和E1={（A,B),（B,C），（C,D），（D,A），（A,C）}   注意：无向边用“（）”，而有向边用“< >”表示。

有向边：若从顶点V1到V2的边有方向，则称这条边为有向边，也称弧(Arc)。用<V1,V2>表示，V1为弧尾(Tail)（箭尾为尾），V2为弧头(Head)（箭头为弧头）   注意：（V1，V2）≠（V2，V1） 
有向图(Directed graphs)：图中任意两个顶点之间的边都是有向边。

           
简单图：图中不存在顶点到其自身的边，且同一条边不重复出现(没有自环和不含多重边)。

完全图：每对顶点之间都恰连有一条边的图

   无向完全图：无向图中，任意两个顶点之间都存在边。

   有向完全图：有向图中，任意两个顶点之间都存在方向互为相反的两条弧。

 

稀疏图：有很少条边。

稠密图：有很多条边。

权（Weight）：与图的边或弧相关的数。

网（Network）：带权的图。

子图（Subgraph）:假设G=（V,{E}）和G‘=（V',{E'}），如果V'包含于V且E'包含于E，则称G'为G的子图。

度（Degree）：无向图中，与顶点V相关联的边的数目。有向图中，入度表示指向自己的边的数目，出度表示指向其他边的数目，该顶点的度等于入度与出度的和。

路径    非空有限点、弧交替序列，               W=v0, a1,v1, … , ak,vk   使得i=1,2,…k ,               弧ai的头vi , 尾为vi-1   。        

    简单路径：除首尾两点外，其他各点都不相同的路径称为简单路径。

    回路:无重复边的闭路径。

    环：闭的简单路径，称为环。

   

 

路径的长度：一条路径上边或弧的数量。
连通图：图中任意两个顶点都是连通的。

     
连通分量：无向图中的极大连通子图。（子图必须是连通的且含有极大顶点数）。图1有两个连通分量
强连通分量：有向图中的极大强连通子图。
 

（二）图的存储结构       

图有两种存储结构分别为矩阵法和邻接表。

矩阵法

#include <stdio.h>
#include <malloc.h>
#define INF 32767 //定义正无穷
#define MAXV 100//最大顶点数
typedef char InfoType;//定义邻接矩阵
typedef struct
{int no;//顶点编号InfoType info;//顶点其他信息
}Vertextype;//顶点类型typedef struct
{int edges[MAXV][MAXV];//邻接矩阵数组int n, e;//顶点数、边数Vertextype vexs[MAXV];//存放顶点信息
}MatGraph; //完整的图邻接矩阵类型//邻接矩阵的基本运算算法
void CreateMat(MatGraph& g, int A[MAXV][MAXV], int n, int e)
{int i, j;g.n = n; g.e = e;for ( i = 0; i < g.n; i++){for (j = 0; j < g.n; j++) {g.edges[i][j] = A[i][j];}}
}void  DispMat(MatGraph  g)
{int i, j;for (i = 0; i < g.n; i++){for (j = 0; j < g.n; j++) {if (g.edges[i][j] != INF)printf("%4d", g.edges[i][j]);else{printf("%4s","∞");}}puts("\n");}
}int main()
{MatGraph g;int A[MAXV][MAXV] = {{0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},{8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}};int n = 6, e = 10;CreateMat(g, A, n, e);printf("邻接矩阵运算：\n"); DispMat(g);return 0;
}

  

领接表

 

#include <stdio.h>
#include <malloc.h>
#define INF 32767 //定义正无穷
#define MAXV 100//定义最大顶点个数
typedef char InfoType;//定义邻接表类型
typedef struct ANode
{int adjvex;//该边的邻接点的编号struct ANode* nextarc;//指向下一条边的指针int weight;//该边的权值
}ArcNode;typedef struct Vnode
{InfoType info;//顶点其他信息int count;//存放顶点入度，仅用于拓扑排序ArcNode* firstarc;//指向第一条边
}VNode;
typedef struct
{VNode adjlist[MAXV];//邻接表头结点数组int n, e;//图中顶点数n和边数e
}AdjGraph;
//邻接表的基本运算算法void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
{int i, j;ArcNode* p;G = (AdjGraph*)malloc(sizeof(AdjGraph));for (int i = 0; i < n; i++){G->adjlist[i].firstarc = NULL;}  for ( i = 0; i < n; i++){for (j = n - 1; j >= 0; j--) {if (A[i][j] != 0 && A[i][j] != INF){p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;p->weight = A[i][j];p->nextarc = G->adjlist[i].firstarc;G->adjlist[i].firstarc = p;}}}G->n = n; G->e = e;
}
void  DispAdj(AdjGraph*  G )
{ArcNode* p;for (int i = 0; i < G->n; i++){p = G->adjlist[i].firstarc;printf("%3d", i);while (p != NULL){printf("%3d[%d]->", p->adjvex, p->weight);p = p->nextarc;}printf("▽\n");}
}void DestroyAdj(AdjGraph*& G)
{ArcNode* pre, * p;for (int i = 0; i < G->n; i++){pre= G->adjlist[i].firstarc;//if (pre != NULL){p = pre->nextarc;while (p != NULL){free(pre);pre = p;p = p->nextarc;}free(pre);}}free(G);
}
int main()
{AdjGraph* G;int A[MAXV][MAXV] = {{0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},{8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}};int n = 6, e = 10;CreateAdj(G, A, n, e);printf("邻接表运算：\n"); DispAdj(G);DestroyAdj(G);return 0;
}