图 | shaoyuanhangyes

图

G=(V,E) V顶点 E边

图的概念及术语

1.无向图
2.有向图
3.简单图:无重复边没有结点到自身的边
4.多重图:有重复边有结点到自身的边
5.完全图
无向完全图:任意两个顶点都存在边 n个顶点的无向完全图有$\frac{n(n-1)}{2}$个边
有向完全图:任意两个顶点间都存在方向相反的边 n个顶点的有向完全图有n(n-1)个边
6.子图
图本身就是自己的子图
生成子图:子图中包含了原图的所有顶点
7.连通强连通
无向图对应连通图有向图对应强连通图

无向图	连通图	有向图	强连通图
顶点u-w间有路径存在则u w连通	任意两个结点都连通的图叫连通图	u>w w>u都有路径存在则u w强连通	任意两个结点都强连通的图叫强连通图
连通图:n个顶点最少n-1个边	-	强连通图:n个顶点最少n个边	-
连通分量=极大连通子图:	包含了所有边的连通子图	强连通分量=极大强连通子图	包含了所有边的强连通子图

8.极小连通子图:边数最少的连通子图
9.生成树:连通图中包含了全部结点的一个极小连通子图(不唯一) n个结点n-1条边
生成森林:非连通图所有连通分量的生成树组成生成森林(不唯一)
10.度
n个结点e个边的无向图中度的总数为2e
n个结点e个边的有向图中入度=出度=e
11.网(带权图):对边赋予权值就成了网
12.稀疏图/稠密图:当|E|<|V|log|E|时该图为稀疏图反之为稠密图

图的存储

邻接矩阵

一维数组存结点二维数组存边所以空间复杂度$O(n^2)$

#define Maxsize 100
typedef char VertexType;//结点类型
typedef int EdgeType;//边类型
typedef struct{
    VertexType Vex[Maxsize];//一维数组
    EdgeType Edge[Maxsize][Maxsize];//二维数组
    int vexnum,edgenum;//结点个数，边个数
}MGraph;

性质：
适合稠密图
有向图邻接矩阵中一行非零的个数为该点的入度一列非零的个数为该点的出度
无向图的邻接矩阵为实对称矩阵 $A=A^T$ 一行/列非零个数为该点的度
邻接矩阵$A$ $A^n元素A^n[i][j]=X 其中X=i-j$路径长度为n的路径的个数
针对稀疏图邻接矩阵内存放了很多0/无意义的数据造成了空间上的浪费因此针对稀疏图我们采用邻接表的方式进行存储

邻接表

为每个结点建立一个与之相连的单链表存放与结点相连的边
顶点表为顺序存储存顶点的数据存边表的头指针
边表为链式存储存放与该结点相连的所有边

#define Maxsize 
typedef struct ArcNode{//边表
    int adjvex;//边表数据域 存放相连结点的标号
    struct ArcNode *next;//指向下一个边
}ArcNode;
typedef struct VNode{//顶点表
    VertexType data;//顶点元素
    ArcNode *first;//指向第一个边
}VNode，AdjList[Maxsize];
typedef struct{//邻接表
    AdjList vertices;//存整个图的数据
    int vexnum,arcnum;//顶点个数，边个数
}ALGraph;

性质:
适合稀疏图
因为对结点相连的边选择顺序不同所以邻接表不唯一
有向图邻接表存储空间O(|V|+|E|) 结点对应边表的长度为该结点的出度入度需要遍历邻接表计算
无向图邻接表存储空间O(|V|+2|E|) 结点对应边表的长度为该结点的度

邻接矩阵与邻接表比较

邻接矩阵	vs	邻接表
适合稠密图	适用性	适用稀疏图
效率高	判断两个顶点间是否存在边	效率低
效率低	找出某顶点相邻的边	效率高

十字链表

十字链表是有向图的一种链式存储结构

邻接多重表

邻接多重表是无向图的一种链式存储结构

图的遍历

广度优先搜索BFS

通过一个队列和一个数组来实现

bool visited[Maxsize];//辅助数组visited来标记对应编号的顶点是否被访问过
void BFSTraverse(Graph G){
    for(int i=0;i<G.vexnum;i++) visited[i]=0;//初始化辅助数组全部置0;
    InitQueue(Q);
    for(int i=0;i<G.vexnum;i++){//不连通的图的顶点也可以被循环到
        if(!visited[0]) BFS(G,i);//若该顶点未被访问过 对该顶点执行BFS
    }
}

//FirstNeighbor(G,x) 求图G中顶点x的第一个邻接点 若存在则返回顶点编号 不存在就返回-1
//NextNeighbor(G,x,y) y是x的一个邻接点 返回除了y之外的下一个邻接点 不存在就返回-1

void BFS(Graph G,int v){//v为顶点在visited数组中的编号
    visit(v);
    visited[v]=1;//v被标记访问过
    EnQueue(Q,v);//v入队
    while(!IsEmpty(Q)){//队列不为空时执行循环
        DeQueue(Q,v);
        for(int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,x,w)){
            if(!visited[w]){//若该邻接点未被访问过
                visit[w];
                visited[w]=1;
                EnQueue(Q,w);
            }
        }
    }
}

BFS算法性能分析: 空间复杂度$O(|V|)$ 时间复杂度 G为邻接矩阵 $O(|V|^2)$ G为邻接表 $O(|V|+|E|)$
可以利用BFS解决无权图的单源最短路径问题
可以利用BFS得到广度优先生成树邻接矩阵的广度优先生成树唯一邻接表的广度优先生成树不唯一(邻接表的边表序列不唯一)

深度优先搜索DFS

通过递归或者栈实现

bool visited[Maxsize];//标记数组
void DFSTraverse(Graph G){
    for(int i=0;i<G.vexnum;i++) visited[i];
    for(int i=0;i<G.vexnum;i++){
        if(!visited[i]) DFS(G,i);//结点未被访问过 进行DFS；
    }
}
void DFS(Graph G,int v){
    visit[v];
    visited[v]=1;
    for(int w=FisrtNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
        if(!visited[w]) DFS(G,w);
    }
}

DFS算法性能分析: 空间复杂度$O(|V|)$ 时间复杂度 G为邻接矩阵 $O(|V|^2)$ G为邻接表 $O(|V|+|E|)$
深度优先遍历得出的序列得到深度优先生成树/森林
邻接矩阵的深度优先生成树唯一邻接表的深度优先生成树不唯一(邻接表的边表序列不唯一)

遍历和连通性

在无向图中 BFS()与DFS()的调用次数为连通分量的个数

图的应用

最小生成树

最小生成树就是极小连通子图包含了所有顶点和最少的边权值唯一且最小 |E|=|V|-1
性质:带权无向连通图才有最小生成树最小生成树不一定唯一当所有的边权值都不一样时才有唯一的最小生成树
图有n个顶点n-1个边时最小生成树就是它自己

从策略上来说，Prim算法是直接查找，多次寻找邻边的权重最小值，而Kruskal是需要先对权重排序后查找的
所以说，Kruskal在算法效率上是比Prim快的，因为Kruskal只需一次对权重的排序就能找到最小生成树，而Prim算法需要多次对邻边排序才能找到

Prim算法

适用于稠密图
首先以一个结点作为最小生成树的初始结点，然后以迭代的方式找出最小生成树中各结点权重最小的边，并加到最小生成树中。（加入之后如果产生回路了就要跳过这条边，选择下一个结点）当所有的结点都加入到最小生成树中后，就找出了这个连通图的最小生成树

Kruskal算法

Kruskal算法在找最小生成树结点之前，需要对权重从小到大进行排序。将排序好的权重边依次加入到最小生成树中（如果加入时产生回路就跳过这条边，加入下一条边），当所有的结点都加入到最小生成树中后，就找到了这个连通图的最小生成树

shaoyuanhangyes

图

图