图（G）由顶点集（V）和边集（E）组成，G=(V,E)
常用概念：
①V(G)表示图G中顶点的有限非空集，V永不为空；
②用|V|表示图G中顶点的个数，也称为图G的阶；
③E(G)表示图G中顶点之间关系（边）的集合；
④用|E|表示图G中边的条数。
图分为：
①有向图：有向边（弧）的有限集合<V,W>；
②无向图：无向边（边）的有限集合(V,W)。
简单图：不存在顶点到自身的边，同一条边不重复出现。
多重图：某两个结点之间的边数多于一条，又允许顶点通过一条边和自己关联。
完全图：任意两个结点之间都有边，其分为：
①无向完全图：如果任意两个顶点之间都有边，其有n个结点，n*(n-1)/2条边；
②有向完全图：如果任意两个顶点之间都存在方向相反的两条弧，其有n个结点，n*(n-1)条边。
子图：若G=(V,E)，G'=(V',E')，其中V'为V的子集，E'为E的子集，若V(G')=V(G)，则G'为G的子图。
连通图：图中任意两个顶点都是连通的。
连通分量：无向图中的极大连通子图，有以下特点：①子图；②连通；③顶点足够多；④包含这些依附在顶点的所有边。
强连通：顶点V到顶点W和顶点W到顶点V都有路径。
强连通图：图中任意一对顶点都是强连通的。
强连通分量：有向图中的极大强连通子图，有以下特点：①子图；②强连通；③顶点足够多；④包含这些依附在顶点的所有弧。
度：以该顶点为一个端点的边数目。
在无向图中：顶点V的度是依附于该顶点的边条数，记为TD；
在有向图中：①入度：以顶点V为终点的有向边的条数，记为ID；
②出度：以顶点V为起点的有向边的条数，记为OD。
图的存储结构有以下几种：
①图的顺序存储结构：邻接矩阵，其顶点用一位数组来存储，边或弧用二维数组来存储，例如a[i][j]=1表示(vi,vj)或<vi,vj>是图的边。
#define MaxVertexNum 100 //顶点数目最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //整数表示权值或者连通性
typedef struct{
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表
int vexnum,arcnum; //图的当前顶点数和弧度
}MGraph;
②图的链式存储结构：邻接表，由顶点表和边表（单链表）组成，无法遍历，只有出弧。
#define MaxVertexNum 100
typedef struct VNode{ //顶点表结点
VertexType data; //顶点表信息
ArcNode *firstedge; //单链表头指针
}VNode,AdjList[MaxVertexNum];
typedef struct ArcNode{ //边表结点
int adjvex; //该弧所指向顶点的位置
struct ArcNode *next; //指向下一条弧的指针
}ArcNode;
typedef struct{
AdjList vertices; //邻接表
int vexnum,arcnum; //图的顶点数和弧数
}ALGraph; //以邻接表存储的图类型
③有向图的优化链式存储结构：十字链表
#define MaxVertexNum 100
typedef struct VNode{
VertexType data; //顶点数据
ArcNode *first,*firstout; //该顶点的入边表头指针和出边表头指针
}VNode;
typedef struct ArcNode{
int tailvex,headvex; //这条弧的起点所在顶点表下标和终点所在顶点表下标
struct ArcNode *hlink,*tlink; //终点相同的下一条弧以及起点相同的下一条弧
}ArcNode;
typedef struct{
VNode xlist[MaxVertexNum]; //顶点依旧用顺序存储
int vexnum,arcnum; //图的顶点数与弧数
}GLGraph; //十字链表存储的图类型
④无向图的优化链式存储结构：邻接多重表
#define MaxVertexNum 100
typedef struct VNode{ //顶点表结点
VertexType data; //顶点表信息
ArcNode *firstedge; //单链表头指针
}VNode;
typedef struct ArcNode{ //边表结点
int ivex,jvex; //这条边依附的两个顶点在顶点表的下标
struct ArcNode *ilink,*jlink; //对应两个顶点的下一条边
}ArcNode;
typedef struct{
VNode xlist[MaxVertexNum];
int vexnum,arcnum; //图的顶点数和弧数
}DLGraph;
图的遍历：因为图的顶点没有特殊性，所以可以设置一个访问数组，记录遍历过程中访问过的顶点。
广度优先遍历（BFS）：类似于树中的层序遍历算法。
#define MaxSize 100
bool visited[MaxSize];
void BFS(Graph G,int v){
ArcNode *p; //工作指针p
InitQueue(Q); //初始化第一个队列
visit(v); //访问第一个顶点v
visited[v]=true; //对v做已访问标记
Enqueue(Q,v); //顶点v入队列
while(!isEmpty(Q)){ //只要队列不空
DeQueue(Q,v); //顶点v出队列
p=G->adjlist[v].firstedge; //指针p指向当前顶点的边表链表头指针
while(p){
if(!visited[p->adjvex]){ //p所指向顶点如果未被访问
visit(p->adjvex); //访问p所指向的顶点
visited[p->adjvex]=true; //对这个顶点做已访问标记
EnQueue(Q,p->adjvex); //这个顶点入队列
}
p=p->next; //p指向该顶点的下一条边
}
}
}
void BFSTraverse(Graph G){
int i; //单独定义是方便多个循环使用
for(i=;i<G->vexnum;i++) visited[i]=false; //将标志数组初始化（全局数组）
for(i=;i<G->vexnum;i++){
if(!visited[i]) BFS(G,i); //为避免非连通图一些顶点访问不到，若是连通图只会执行一次
}
}
BFS的应用：解决单源非带权图最短路径问题。
深度优先遍历（DFS）：类似于树的先序遍历算法。
#define MaxSize 100
bool visited[MaxSize];
void DFS(Graph G,int v){
ArcNode *p;
visit(v);
visited[v]=true;
p=G->adjlist[v].firstarc;
while(p!=NULL){
if(!visited[p->adjvex]){
DFS(G,p->adjvex);
}
p=p->nextarc;
}
}
void DFSTraverse(Graph G){
int i;
for(i=;i<G->vexnum;i++) visited[i]=false; //将标志数组初始化（全局数组）
for(i=;i<G->vexnum;i++){
if(!visited[i]) DFS(G,i);
}
}