图
图的基本概念
图的定义
图的基本术语
入度和出度：对于有向图中的一个顶点 V 来说，箭头指向 V 的弧的数量为 V 的入度（InDegree，记为 ID(V)）；箭头远离 V 的弧的数量为 V 的出度。
完全图：若图中各个顶点都与除自身外的其他顶点有关系，这样的无向图称为完全图。同时，满足此条件的有向图则称为有向完全图。具有n个顶点的无向完全图包含边数n(n-1)/2,有向完全图包含边数n(n-1)。
稀疏图和稠密图：这两种图是相对存在的，即如果图中具有很少的边（或弧），此图就称为稀疏图；反之，则称此图为稠密图。稀疏和稠密的判断条件是：e<nlogn，其中 e 表示图中边（或弧）的数量，n 表示图中顶点的数量。如果式子成立，则为稀疏图；反之为稠密图。
子图：指的是由图中一部分顶点和边构成的图，称为原图的子图。
路径和回路：无论是无向图还是有向图，从一个顶点到另一顶点途径的所有顶点组成的序列（包含这两个顶点），称为一条路径。如果路径中第一个顶点和最后一个顶点相同，则此路径称为回路（或环）。并且，若路径中各顶点都不重复，此路径又被称为简单路径；同样，若回路中的顶点互不重复，此回路被称为简单回路（或简单环）。
路径长度：每一条路径上经过的边的数目。
连通图和连通分量：无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。若无向图不是连通图，但图中存储某个子图符合连通图的性质，则称该子图为连通分量。
强连通图和强连通分量：有向图中，若任意两个顶点 Vi 和 Vj，满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通，也就是都含有至少一条通路，则称此有向图为强连通图。若有向图本身不是强连通图，但其包含的最大连通子图具有强连通图的性质，则称该子图为强连通分量。n个顶点的强连通图至少有n条边。
权和网: 在某些实际场景中，图中的每条边（或弧）会赋予一个实数来表示一定的含义，这种与边（或弧）相匹配的实数被称为"权"，而带权的图通常称为网。
Tips
- 无向图中，所以顶点的度之和等于边数的2倍
- 一个n个顶点的无向图最多有n(n-1)/2条边
- n个顶点的无向图最少有n-1条边才可能是一个连通图
- 对于n个顶点的无向图G，保证图G任何情况下都是连通需要的边数最少为(n-1)(n-2)/2+1条边
- n个顶点的有向图中，每个顶点的度最大可达到2(n-1)
- n个顶点的有向图G最多有n(n-1)条边
图的存储结构
邻接矩阵存储方法
Tips
- 无向图的邻接矩阵一定是对称矩阵，反之一个对称矩阵对应的图不一定是无向图。例如完全有向图的邻接矩阵就是对称的。
- 如果一个图的邻接矩阵是不对称的，那么该图一定是有向图。反之一个图是有向图它的邻接矩阵不一定就是不对称的。
- 邻接矩阵适合于稠密图，因为邻接矩阵占用的存储空间与边数无关
- 对于邻接矩阵表示的无向图，图的边数为邻接矩阵数组中为1的元素个数除以2。
- 对于邻接矩阵表示的有向图，图的边数为邻接矩阵数组中为1的元素个数。
- 对于邻接矩阵表示的无向图，顶点i的度等于第i行中元素为1的个数
- 对于邻接矩阵表示的有向图，顶点i的出度等于第i行中元素为1的个数，入度等于第i列中元素为1的个数，顶点i的度数等于它们的和。
图的邻接矩阵结构体定义如下：
#define MAXV <最大顶点个数>
#define INF 32767
typedef struct
{
int no; //顶点的编号
InfoType info; //顶点的其他信息
} VertexType; //顶点的类型
typedef struct
{
int edges[MAXV][MAXV]; //邻接矩阵数组
VertexType vexs[MAXV]; //存储图中顶点信息
int n, e; //记录图的顶点数n和边数e
} MatGraph; //完整的图邻接矩阵类型邻接表存储方法
Tips
- 邻接表适合于稀疏图，因为邻接表占用的存储空间与边数有关。
- 对于邻接表表示的无向图，图的边数等于边结点的个数除以2。
- 对于邻接表表示的有向图，图的边数等于边结点的个数。
- 对于邻接表表示的无向图，顶点i的度等于G->adjlist[i]为头结点的单链表中边表结点的个数。
- 对于邻接表表示的有向图，顶点i的出度等于G->adjlist[i]为头结点的单链表中边表结点的个数，入度需要遍历所以边结点，若G->adjlist[j]为头结点的单链表中存在编号为i的边结点，顶点i的入度加1，顶点i的度为入度和出度之和。
图的邻接表结构体定义如下：
typedef struct ANode
{
int adjvex; //邻接点在数组中的位置下标
struct ANode *nextarc; //指向下一个邻接点的指针
int weight; //权值
} ArcNode; //边结点类型
typedef struct VNode
{
IofoType info; //顶点的其他信息
ArcNode *firstarc; //指向第一个邻接点的指针
} VNode; //存储各链表头结点的数组
typedef struct
{
VNode adjlist[MAXV]; //邻接表的头结点的数组
int n, e; //记录图中顶点数n和边数e
} AdjGraph; //完整的图邻接表类型图的基本运算算法
创建图
void CreatAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
{
int i, j;
ArcNode *p;
G = (AdjGraph *)malloc(sizeof(AdjGraph)); //为图邻接表分配空间
for (i = 0; i < n; i++)
G->adjlist[i].firstarc = NULL; //先将邻接表中每个头结点的指针域置为空
for (i = 0; i < n; i++)
for (j = n - 1; j >= 0; j--) //扫描邻接矩阵A中不为0不为正无穷的元素
if (A[i][j] != 0 && A[i][j] != INF)
{
p = (ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点p
p->adjvex = j; //邻接点编号置为j
p->weight = A[i][j]; //为邻接点设置权重
p->nextarc = G->adjlist[i].firstarc; //用头插法插入p结点
G->adjlist[i].firstarc = p;
}
G->n = n; //图的顶点为n
G->e = e; //图的边数置为e
}输出图
void DispAdj(AdjGraph *G)
{
int i;
ArcNode *p;
for (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;
}
}
}销毁图
void DestoryAdj(AdjGraph *&G)
{
int i;
ArcNode *pre, *p;
for (i = 0; i < G->n; i++) //扫描所有的单链表
{
pre = G->adjlist[i].firstarc; //让pre先指向第i个单链表的头结点的后继结点
if (pre != NULL)
{
p = pre->nextarc;
while (p != NULL) //依次释放第i个单链表的所有边结点
{
free(pre);
pre = p; //每次要将p的前一个结点保存起来
p = p->nextarc;
}
free(pre); //释放pre
}
}
free(G); //最后释放头结点数组
}图的遍历
深度优先遍历（DFS）
深度优先遍历，是从图中的一个顶点出发，每次遍历当前访问顶点的临界点，一直到访问的顶点没有未被访问过的临界点为止。然后采用依次回退的方式，查看来的路上每一个顶点是否有其它未被访问的临界点。访问完成后，判断图中的顶点是否已经全部遍历完成，如果没有，以未访问的顶点为起始点，重复上述过程。
int visited[MAX] = {0}; //定义一个全局数组visited所有元素均为0表示所有结点均未访问过
void DFS(AdjGraph *G, int v) //v是初始点
{
ArcNode *p;
visited[v] = 1; //先将v置为已访问
printf("%d ", v); //输出已访问结点的编号
p = G->adjlist[v].firstarc; //p指向v的第一个邻接点
while (p != NULL)
{
if (visited[p->adjvex] == 0) //如果p->adjvex顶点未被访问，递归访问它
DFS(G, p->adjvex);
p = p->nextarc; //p在指向v的下一个邻接点
}
}广度优先遍历（BFS）
广度优先遍历类似于树的层次遍历。从图中的某一顶点出发，遍历每一个顶点时，依次遍历其所有的邻接点，然后再从这些邻接点出发，同样依次访问它们的邻接点。按照此过程，直到图中所有被访问过的顶点的邻接点都被访问到。最后还需要做的操作就是查看图中是否存在尚未被访问的顶点，若有，则以该顶点为起始点，重复上述遍历的过程。广度优先遍历中用到了队列，每个顶点最多入队一次。
void BFS(adjGraph *G, int v)
{
int w, i;
ArcNode *p;
SqQueue *qu; //定义一个环形队列qu
InitQuence(qu); //初始化队列
int visited[MAXV]; //定义顶点访问标记数组
for (i = 0; i < G->n; i++) //访问标记数组初始化为0 表示未访问
{
visited[v] = 0;
}
printf("%2d", v); //输出被访问的顶点v的编号
visited[v] = 1; //将v标记为已访问
enQueue(qu, v); //将v进队
while (!QueueEmpty(qu)) //判断如果队列不为空
{
deQueue(qu, w); //出队一个顶点w
p = G->adjlist[w].firstarc; //p指向w的第一个邻接点
while (p != NULL) //查找w的所有邻接点
{
if (visited[p->adjvex] == 0) //如果邻接点未被访问
{
printf("%2d", p->adjvex); //输出该邻接点
visited[p->adjvex] = 1; //将该结点标记为已访问
enQueue(qu, p->adjvex); //将该结点进队
}
p = p->nextarc; //再找下一个邻接点
}
}
printf("\n");
}Tips
- 采用邻接表存储的图的深度优先遍历与二叉树的先序遍历类似。
- 采用邻接表存储的图的广度优先遍历与二叉树的层序遍历类似。
- 对于一个连通图，从它的任一顶点出发进行一次深度优先遍历或者广度优先遍历可访问到图的全部顶点。
- 对于一个非连通图，它有几个连通分量就要调用几次深度优先遍历或者广度优先遍历才可访问到图的全部顶点。
生成树和最小生成树
定义
生成树：一个连通图的生成树是一个极小连通子图，其中含有图中全部顶点，和构成一棵树的（n-1）条边。
注意：一棵有n个顶点的生成树有且仅有（n-1）条边。如果小于（n-1）条边，就是非连通图。如果多于（n-1）条边，则它一定有回路。
最小生成树：图的所有生成树的中边上权值之和最小的树称为图的最小生成树。
一个带权无向图的最小生成树不一定是唯一的，但最小生成树的所有边的权值之和一定是唯一的。
普里姆算法
下面算法的时间复杂度为 O(n2) ，其中n为顶点个数。普里姆算法的执行时间与图的边数无关所以它特别适合用稠密图求最小生成树。
void Prim(MatGraph g, int v)
{
int lowcost[MAXV]; //初始化lowcost数组保存最小边
int MIN;
int closest[MAXV], i, j, k; //初始化closest数组保存U中的顶点
for (i = 0; i < g.n; i++) //初始化lowcost[]和closest[]数组
{
lowcost[i] = g.edges[v][i];
closest[i] = v;
}
for (i = 0; i < g.n; i++) //遍历找出（n-1）个顶点
{
MIN = INF;
for (j = 0; j < g.n; j++) //在集合V-U中找离U最近的顶点k
if (lowcost[j] != 0 && lowcost[j] < MIN)
{
MIN = lowcost[j];
k = j;
}
printf("边(%d,%d)权为：%d\n", closest[k], k, MIN);//将这条边输出
lowcost[k] = 0; //将lowcost[k]置为0，表示k已经加入了U
for (j = 0; j < g.n; j++) //只考虑V-U中的顶点，修改侯选边
if (lowcost[j] != 0 && g.edges[k][j] < lowcost[j]) //要将原来的lowcost[j]与g.edges[k][j]比较
{
lowcost[j] = g.edges[k][j]; //如果g.edges[k][j]小，选择（k,j）作为新的最小边
closest[j] = k; //将closest[j]置为k
}
}
}克鲁斯卡尔算法
下面的算法的时间复杂度为 O(e2)中e为边的个数。克鲁斯卡尔算法的执行时间与图的顶点数无关所以它特别适合用稀疏图求最小生成树。
typedef struct
{
int u; //边的起始顶点
int v; //边的终止顶点
int w; //边的权值
} Edge;
void Kruskal(MatGraph g)
{
int i, j, u1, v1, sn1, sn2, k;
int vest[MAXV]; //连通分量编号数组
Edge E[MaxSize]; //存放图中的所有边
k = 0; //E的数组下标
for (i = 0; i < g.n; i++) //由g生成边集数组E
for (j = 0; j <= i; j++)
if (g.edges[i][j] != 0 && g.edges[i][j] != INF)
{
E[k].u = i;
E[k].v = j;
E[k].w = g.edges[i][j];
k++;
}
InsertSort(E, g, e); //采用直接插入排序对E数组按权值递增排序
for (i = 0; i < g.n; i++) //初始化连通分量编号各不相同
vest[i] = i;
k = 1; //这里的k表示当前构造生成树的第几条边，初值为1
j = 0; //E中的边的下标,初值为0
while (k < g.n) //生成n-1条边
{
u1 = E[j].u;
v1 = E[j].v;//取一条边的两个顶点
sn1 = vest[u1];
sn2 = vest[v1];//分别得到这两个顶点所属的连通分量编号
if (sn1 != sn2) //若两顶点所属连通分量编号不同，则该边可作为最小生成树的一条边
{
printf("(%d,%d):%d\n", u1, v1, E[j].w); //输出改边
k++; //将生成的边数加1
for (i = 0; i < g.n; i++) //两个连通分量编号统一
if (vest[i] == sn2) //将连通分量编号sn2的改为sn1
vest[i] = sn1;
}
j++; //扫描E边集的下一条边
}
}还有一种改进的克鲁斯卡尔算法构造最小生成树的时间复杂度为O(elog2e)。里面用到了堆排序的概念
最短路径
从一个顶点到其余各个顶点的最短路径
狄克斯特拉（Dijkstra）算法
- 求单源最短路径的狄克斯特拉算法既适合于带权有向图也适合于带权无向图。
- 狄克斯特拉算法中一旦将一个顶点加入到S集合中，它以后的最短路径将不会进行调整。
- 狄克斯特拉算法不适合含有负的权值的图求单源最短路径。
- 不考虑路径输出，狄克斯特拉算法的时间复杂度为O(n2)。其中n为图中顶点个数。
算法如下：
void Dijkstra(MatGraph g, int v)
{
int dist[MAXV], path[MAXV]; //dist数组存放最短路径长度，path数组存放最短路径
int S[MAXV]; //S[i]=1表示顶点i在S中，S[i]=0表示顶点i在U中
int MINdis, i, j, u;
for (i = 0; i < g.n; i++)
{
dist[i] = g.edges[v][i]; //将距离进行初始化
S[i] = 0; //将S[]置为空
if (g.edges[v][i] < INF) //将路径初始化
path[i] = v; //顶点v到i有边时，置顶点i的前一个顶点为v
else
path[i] = -1; //顶点v到i无边时，置顶点i的前一个顶点为-1
}
S[v] = 1; //先将v放入S中
path[v] = 0;
for (i = 0; i < g.n - 1; i++) //循环直到所以顶点的最短路径都被求出
{
MINdis = INF; //先将MINdis置为最大值
for (j = 0; j < g.n; j++) //选取不在S中的顶点且具有最短路径长度的顶点u
if (S[j] == 0 && dist[j] < MINdis)
{
u = j;
MINdis = dist[j];
}
S[u] = 1; //将顶点u加入到S中
for (j = 0; j < g.n; j++) //修改不在S中顶点的最短路径长度
if (S[j] == 0)
if (g.edges[u][j] < INF && dist[u] + g.edges[u][j] < dist[j]) //若新加入的顶点dist[u] + g.edges[u][j]小于dist[j]
{
dist[j] = dist[u] + g.edges[u][j]; //更新顶点j的最短路径长度
path[j] = u; //置顶点j的前一个顶点为u
}
}
Dispath(g, dist, path, S, v); //输出最短路径
}每对顶点之间的最短路径
Floyd算法
- 对比狄克斯特拉算法，Floyd算法可以对含有负的权值的图求最短路径，但是图中不能含有权值和为负数的环路。
- 不考虑路径输出，Floyd算法的时间复杂度为O(n3)。其中n为图中顶点个数。
算法如下：
void Floyd(MatGraph g)
{
int A[MAXV][MAXV], path[MAXV][MAXV]; //A[i][j]表示i->j最短路径长度 用path[][]储存最短路径
int i, j, k;
for (i = 0; i < g.n; i++)
for (j = 0; j < g.n; j++)
{
A[i][j] = g.edges[i][j];
if (i != j && g.edges[i][j] < INF)
path[i][j] = i; //顶点i到j有边时，path[i][j]置为i
else
path[i][j] = -1; //顶点i到j无边时，path[i][j]置为-1
}
for (k = 0; k < g.n; k++) //依次遍历所有顶点
{
for (i = 0; i < g.n; i++)
for (j = 0; j < g.n; j++)
if (A[i][j] > A[i][k] + A[k][j]) //如果i->k->j的路径长度小于i->j的路径长度
{
A[i][j] = A[i][k] + A[k][j]; //修改i->j最短路径的长度
path[i][j] = path[k][j]; //修改最短路径
}
}
Dispath(g, A, path); //输出最短路径
}拓扑排序
结构体定义和算法如下：
typedef struct
{
Vertex data; //顶点信息
int count; //增加数据域，存放顶点入度
ArcNode *firstarc; //指向第一个邻接点
} VNode; //邻接表头结点类型void TopSort(AdjGraph *G)
{
int i, j;
int St[MAXV], top = -1; //定义一个栈，指针为top
ArcNode *p; //定义一个邻接表边结点p
for (i = 0; i < G->n; i++) //将入度的初值置为0
G->adjlist[i].count = 0;
for (i = 0; i < G->n; i++) //求所有顶点的入度，并存到count中
{
p = G->adjlist[i].firstarc;
while (p != NULL)
{
G->adjlist[p->adjvex].count++;
p = p->nextarc;
}
}
for (i = 0; i < G->n; i++) //将入度为0的顶点进栈
if (G->adjlist[i].count == 0)
{
top++;
St[top] = i;
}
while (top > -1) //如果栈不为空
{
i = St[top];
top--; //出栈一个顶点
printf("%d", i); //输出该顶点
p = G->adjlist[i].firstarc; //找到该顶点第一个邻接点
while (p != NULL) //将顶点i的出边邻接点的入度均减1
{
j = p->adjvex;
G->adjlist[j].count--;
if (G->adjlist[j].count == 0) //如果邻接点入度为0，将其进栈
{
top++;
St[top] = j;
}
p = p->nextarc; //找下一个邻接点
}
}
}Tips
- 一个有向图如果存在回路，那么不能产生一个完整的拓扑序列，所以强连通图不能进行拓扑排序。
- 如果一个有向图不能产生一个完整的拓扑序列，那么图中一定存在回路。
- 如果一个有向图的拓扑序列是唯一的，那么图中必有一个顶点的入度为0，一个顶点的出度为0。
- 如果图中只有一个入度为0的顶点，在拓扑序列中每次都输出一个顶点后都只有一个入度为0的顶点，那么这个有向图的拓扑序列是唯一的。
- 如果一个AOV网有n个顶点，e条边，在拓扑排序的过程中，搜索入度为零的顶点所需的时间是O(n)。在正常情况下，每个顶点进一次栈，出一次栈，所需时间O(n)。每个顶点入度减1的运算共执行了e次。所以总的时间复杂为O(n+e)。
- 判断一个有向图是否存在回路除了可以用拓扑排序方法以外，还可以采用深度优先遍历。
Comments NOTHING