图的基本概念
1. 图的定义
图(Graph)G由两个集合V和E组成，记为G=(V, E)，其中：V是顶点的有穷非空集合，E是V中顶点偶对(称为边)的有穷集。
通常，也将图G的顶点集和边集分别记为V(G)和E(G)。E(G)可以是空集。若E(G)为空，则图G只有顶点而没有边。
图中的结点之间是多对多的关系。
2. 有向图与无向图
有向图：若图G中的每条边都是有方向的，则称G为有向图(Digraph)。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。有向边也称为弧(Arc)，边的始点称为弧尾(Tail)，终点称为弧头(Head)。
【例】<vi，vj>表示一条有向边，vi是边的始点(起点)，vj是边的终点。因此，<vi，vj>和<vj，vi>是两条不同的有向边。
【例】下面图中G1是一个有向图。图中边的方向是用从始点指向终点的箭头表示的，该图的顶点集和边集分别为：
V(G1)={v1，v2，v3} E(G1)={<v1，v2>，<v2，v1>，<v2，v3>}
attachment:G1.jpg
无向图：若图G中的每条边都是没有方向的，则称G为无向图(Undigraph)。无向图中的边均是顶点的无序对，无序对通常用圆括号表示。
【例】无序对(vi，vj)和(vj，vi)表示同一条边。
【例】下面图中的G2和G3均是无向图，它们的顶点集和边集分别为：
- V(G2)={v1，v2，v3，v4} E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}
- V(G3)={v1，v2，v3，v4，v5，v6，v7} E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}
attachment:G2.jpg
attachment:G3.jpg
注意：在以下讨论中，不考虑顶点到其自身的边。即若(v1，v2)或<vl，v2>是E(G)中的一条边，则要求v1≠v2。此外，不允许一条边在图中重复出现，即只讨论简单的图。
3. 顶点和边的关系
图G的顶点数n和边数e的关系
- 若G是无向图，则0≤e≤n(n-1)/2。恰有n(n-1)/2条边的无向图称无向完全图(Undireet-ed Complete Graph)
- 若G是有向图，则0≤e≤n(n-1)。恰有n(n-1)条边的有向图称为有向完全图(Directed Complete Graph)。
注意：完全图具有最多的边数。任意一对顶点间均有边相连。
【例】图G2就是具有4个顶点的无向完全图。
图的边和顶点的关系
无向边和顶点关系：若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接点(Adjacent)，或称vi和vj相邻接；并称(vi,vj)依附或关联(Incident)于顶点vi和vj，或称(vi，vj)与顶点vi和vj相关联。
【例】图G2中：
- 与顶点v1相邻接的顶点是v2，v3和v4
- 关联于顶点v2的边是(v1，v2)，(v2，v3)和(v2，v4)
有向边和顶点关系：若<vi，vj>是一条有向边，则称顶点vi邻接到vj，顶点vi邻接于顶点vj；并称边<vi，vj>关联于vi和vj或称<vi，vj>与顶点vi和vj相关联。
【例】在图G1中，关联于顶点v2的弧是<v1，v2>，<v2，v1>和<v2，v3>。
4. 顶点的度
无向图中顶点v的度(Degree)：无向图中顶点v的度(Degree)是关联于该顶点的边的数目，记为D(v)。
【例】图G2中顶点v1的度为3
有向图顶点v的入度(In Degree)：有向图中，以顶点v为终点的边的数目称为v的入度，记为ID(v)。 【例】图G1中顶点v2的人度为l
有向图顶点v的出度(Out Degree)：有向图中，以顶点v为始点的边的数目，称为v的出度，记为OD(v)
【例】图G1中顶点v2的出度为2
有向图顶点v的度定义为该顶点的入度和出度之和，即D(v)=ID(v)+OD(v)。
【例】图G1中顶点v2的人度为l，出度为2，则度为3。
无论有向图还是无向图，顶点数n、边数e和度数之间有如下关系： latex($$e=\frac{1}{2}\sum_{i=1}^nD(v_i)$$)
5. 子图
子图: 设G=(V，E)是一个图，若V'是V的子集，E'是E的子集，且E'中的边所关联的顶点均在V'中，则G'=(V'，E')也是一个图，并称其为G的子图(Subgraph)。
【例】给出有向图Gl的若干子图；给出无向图G2的若干个子图。
attachment:subgraph.jpg
6. 路径
无向图的路径:在无向图G中，若存在一个顶点序列vp,vi1，vi2,…，vim，vq，使得(vp，vi1)，(vi1，vi2)，…，(vim，vq)均属于E(G)，则称顶点vp到vq存在一条路径(Path)。
有向图的路径:在有向图G中，路径也是有向的,它由E(G)中的有向边<vp，vi1>，<vi1，vi2>，…，<vim，vq>组成。
路径长度:路径长度定义为该路径上边的数目。
简单路径:若一条路径上除了vp和vq可以相同外，其余顶点均不相同，则称此路径为一条简单路径。
【例】在图G2中顶点序列vl，v2，v3，v4是一条从顶点v1到顶点v4的长度为3的简单路径
【例】在图G2中，顶点序列v1，v2，v4，v1，v3是一条从顶点v1到顶点v3的长度为4的路径，但不是简单路径；
简单回路或简单环(Cycle):起点和终点相同(vp=vq)的简单路径称为简单回路或简单环(Cycle)。
【例】图G2中，顶点序列v1，v2，v4，v1是一个长度为3的简单环
【例】有向图G1中，顶点序列v1，v2，v1是一长度为2的有向简单环。
有根图和图的根:在一个有向图中，若存在一个顶点v，从该顶点有路径可以到达图中其它所有顶点，则称此有向图为有根图，v称作图的根。
顶点间的连通性:在无向图G中，若从顶点vi到顶点vj有路径(当然从vj到vi也一定有路径)，则称vi和vj是连通的。
7. 连通图和连通分量
连通图:若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)，则称G为连通图(Con-nected Graph)。
【例】图G2，和G3是连通图。
连通分量:无向图G的极大连通子图称为G的连通分量(Connected Component)。
注意：① 任何连通图的连通分量只有一个，即是其自身 ② 非连通的无向图有多个连通分量。
【例】下图中的G4是非连通图，它有两个连通分量H1和H2。
强连通图:有向图G中，若对于V(G)中任意两个不同的顶点vi和vj，都存在从vi到vj以及从vj到vi的路径，则称G是强连通图。
强连通分量:有向图的极大强连通子图称为G的强连通分量。
注意：① 强连通图只有一个强连通分量，即是其自身。② 非强连通的有向图有多个强连分量。
【例】图G1不是强连通图，因为v3到v2没有路径，但它有两个强连通分量，如右图所示。
8. 网络
网络(Network):若将图的每条边都赋上一个权，则称这种带权图为网络(Network)。
注意：权是表示两个顶点之间的距离、耗费等具有某种意义的数。
【例】下图就是一个网络的例子。
9. 练习
给定图7.28，求每个结点的入度、出度，强连通分量。
图的存储结构
以下假定顶点序号从0开始，即图G的顶点集的一般形式是V(G)={v0，vi，…，Vn-1}。
1. 图的邻接矩阵表示法
在图的邻接矩阵表示法中：
- 用邻接矩阵表示顶点间的相邻关系
- 用一个顺序表来存储顶点信息
图的邻接矩阵(Adacency Matrix)：设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：latex($$A[i,j] = \left\{ \begin{array}{ll} 1 & \textrm{if (vi,vj) or $<vi,vj>$ exists} \\ 0 & \textrm{if (vi,vj) or $<vi,vj>$ not exists} \end{array} \right. $$)
网络的邻接矩阵: 若G是网络，则邻接矩阵可定义为：latex($$A[i,j] = \left\{ \begin{array}{ll} wij & \textrm{if (vi,vj) or $<vi,vj>$ exists} \\ 0 or \infty & \textrm{if (vi,vj) or $<vi,vj>$ not exists} \end{array} \right. $$)。其中：wij表示边上的权值；∞表示一个计算机允许的、大于所有边上权值的数。
【例】下面带权图的两种邻接矩阵分别为A3和A4。
attachment:net.jpg
图的邻接矩阵存储结构实现
注意：
- 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点表及顶点数等均可省略）。
当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeType可定义为值为0和1的枚举类型。
- 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。
邻接矩阵表示法的空间复杂度S(n)=0(n2)。
创建无向网络的算法
1 void CreateMGraph(MGraph *G) {
2 int i, j, k, w;
3 scanf("%d%d", &G->n, &G->e); //输入顶点数和边数
4 for(i=0; i<G->n; i++) //读人顶点信息，建立顶点表
5 scanf("%d", &G->vexs[i]);
6 for(i=0; i<G->n; i++)
7 for(j=0; j<G->n; j++)
8 G->edges[i][j]=0; //邻接矩阵初始化
9 for(k=0; k<G->e; k++){ //读入e条边，建立邻接矩阵
10 scanf("%d%d%d", &i, &j, &w); //输入边(vi,vj)上的权w
11 G->edges[i][j]=w;
12 G->edges[j][i]=w;
13 }
14 }
该算法的执行时间是0(n+n2+e)，由于e<n2，算法的时间复杂度是0(n2)。
2. 邻接表
图的邻接表表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表(Adjacency List)。
邻接表的边结点结构
┌────┬───┐
│adjvex │next │
└────┴───┘邻接表中每个表结点均有两个域:邻接点域adjvex：存放与vi相邻接的顶点vj的序号j；链域next：将邻接表的所有表结点链在一起。
注意：若要表示边上的信息(如权值)，则在表结点中还应增加一个数据域。
头结点结构
┌────┬─────┐
│vertex │firstedge │
└────┴─────┘顶点vi邻接表的头结点包含两个域：顶点域vertex：存放顶点vi的信息；指针域firstedge：vi的邻接表的头指针。
注意：
- 为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。
- 有时希望增加对图的顶点数及边数等属性的描述，可将邻接表和这些属性放在一起来描述图的存储结构。
无向图的邻接表：对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。
n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。
【例】对于无向图G5，其邻接表表示如下面所示，其中顶点v0的边表上三个表结点中的顶点序号分别为1、2和3，它们分别表示关联于v0的三条边(v0，v1)，(v0，v2)和(v0，v3)。
有向图的邻接表：对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。
n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。
【例】有向图G6的邻接表表示如下面(a)图所示，其中顶点v1的邻接表上两个表结点中的顶点序号分别为0和4，它们分别表示从v1射出的两条边(简称为v1的出边)：<v1，v0>和<v1，v4>。
有向图的逆邻接表：在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。
n个顶点e条边的有向图，它的逆邻接表表示中有n个顶点表结点和e个边表结点。
【例】G6的逆邻表如上面(b)图所示，其中v0的人边表上两个表结点1和3分别表示射人v0的两条边(简称为v0的入边)：<v1，v0>和<v3，v0>。
邻接表的实现
1 typedef struct node{//边表结点
2 int adjvex; //邻接点域
3 struct node *next; //链域
4 int weight; //若要表示边上的权，则应增加一个数据域
5 }EdgeNode;
6
7 typedef struct vnode{ //顶点表结点
8 VertexType vertex; //顶点域
9 EdgeNode *firstedge; //边表头指针
10 }VertexNode;
11
12 typedef VertexNode AdjList[MaxVertexNum]; //AdjList是邻接表类型
13
14 typedef struct{
15 AdjList adjlist; //邻接表
16 int n, e; 图中当前顶点数和边数
17 }ALGraph; //对于简单的应用，无须定义此类型，可直接使用AdjList类型。
18
建立无向图的邻接表算法
1 void CreateALGraPh(ALGrahp *G) {
2 int i, j, k;
3 EdgeNode *s;
4 scanf("%d%d", &G->n, &G->e); //读人顶点数和边数
5 for(i=0; i<G->n; i++){
6 scanf("%d", &G->adjlist[i].vertex); //读入顶点信息
7 G->adjlist[i].firstedge=NULL;//边表置为空表
8 }
9 for(k=0; k<G->e; k++){
10 scanf("%d%d", &i, &j); 读入边(vi，vj)的顶点对序号
11 s=(EdgeNode *)malloc(sizeof(EdgeNode)); //生成边表结点
12 s->adjvex=j; //邻接点序号为j
13 s->next=G->adjlist[i].firstedge;
14 G->adjlist[i].firstedge=s; //将新结点*s插入顶点vi的边表头部
15 s=(EdgeNode *)malloc(sizeof(EdgeNode));
16 s->adjvex=i; //邻接点序号为i
17 s->next=G->adjlist[j].firstedge;
18 G->adjlistk[j].firstedge=s; //将新结点*s插入顶点vj的边表头部
19 }
20 }
该算法的时间复杂度是O(n+e)。
注意：
建立有向图的邻接表更简单，每当读人一个顶点对序号<i,j>时，仅需生成一个邻接序号为j的边表结点，将其插入到vj的出边表头部即可。
- 建立网络的邻接表时，需在边表的每个结点中增加一个存储边上权的数据域。
3. 十字链表
图的算法
1. 深度优先遍历
2. 广度优先遍历
3. 最小生成树
4. 最短路径
5. 拓扑排序