王道考研 数据结构之图
图知识点思维导图
图代码实现
1. 图的存储
1.1 邻接矩阵法
#define MaxVertexNum 100 //顶点数目的最大值
//#define INFINITY //宏定义常量无穷，int的最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的类型
typedef struct{
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //图的当前顶点数和边数/弧数
int vexnum,arcnum; //图的当前顶点数和弧数
}MGraph;
1.2 邻接表法
#define MaxVertexNum 100 //顶点数目的最大值
//边表结点
typedef struct ArcNode{
int adjvex; //该弧所指向的顶点位置
struct ArcNode *next; //指向下一条弧的指针
// InfoType info; //网的边权值
}ArcNode;
//顶点表结点
typedef struct VNode{
VertexType data; //顶点信息
ArcNode *first; //第一条边/弧
}VNode,AdjList[MaxVertexNum];
//邻接表
typedef struct{
AdjList vertices; //邻接表
int vexnum,arcnum; //图的顶点和弧数
}ALGraph;
1.3 十字链表法
十字链表是有向图的一种链式存储结构
#define MaxVertexNum 100 //顶点数目的最大值
//边表结点
typedef struct ArcNode{
int tailcex,headvex; //该弧的头尾结点
struct ArcNode *hlink,*tlink; //分别指向弧头相同和弧尾相同的结点
//InfoType info; //相关信息指针
}ArcNode;
//顶点表结点
typedef struct VNode{
VertexType data; //顶点信息
ArcNode *fristin, *firstout; //指向第一条入弧和出弧
}VNode;
//邻接表
typedef struct {
VNode xlist[MaxVerNum]; //邻接表
int vexnum,arcnum; //图的顶点数和弧数
}GLGraph;
1.4 邻接多重表法
邻接多重表是无向图的另一种链式存储方式
#define MaxVertexNum 100 //顶点数目的最大值
//边表结点
typedef struct ArcNode{
bool mark; //访问标记
int ivex,jvex; //分别指向该弧的两个结点
struct ArcNode *llink,*jlink; //分别指向两个顶点的下一条边
//InfoType info; //相关信息指针
}ArcNode;
//顶点表结点
typedef struct VNode{
VertexType data; //顶点信息
ArcNode *fristedge; //指向第一条依附该顶点的边
}VNode;
//邻接表
typedef struct {
VNode adjmulist[MaxVerNum]; //邻接表
int vexnum,arcnum; //图的顶点数和弧数
}AMLGraph;
2. 图的遍历
2.1 广度优先遍历BFS
图的广度优先遍历类似于二叉树的层次遍历，借助队列来实现
bool visit[MAX_VERTEX_NUM]; //访问标记数组
//初始化标记数组和队列，并对每个结点顶点进行访问标记数组，若还没有被访问则调用BFS
void BSFTraverse(Graph G){
//对图G进行广度优先遍历
for(i = 0 ; i<G.vexnum ;++i)
visit[i]=false; //访问顶点标记数组初始化
InitQueue(Q); //初始化辅助队列Q
for(int i = 0;i<G.vexnum;++i)
if(!visited[i]) //对每个连通分量调用一次BFS
BFS(G,i); //Vi未访问过，从Vi开始BFS
}
//广度优先遍历
//访问顶点，做标记入队，队不为空，队头元素出队，访问该队头元素的邻接点，若邻接点未被访问，则标记入队；若无邻接点则继续下一个元素出队
void BFS(Graph G,int v){
//从顶点v出发，广度优先遍历图G，算法借助一个辅助队列Q
visit(v); //访问初试顶点v
visited[v] = TRUE; //对v做已访问标记
Enqueue(Q,v); //顶点v入队
while(!isEmpty(Q)){
DeQueue(Q,v); //顶点v出队
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
//检测v所有邻接点
if(!visited[w]){ //w为v的尚未访问的邻接顶点
visit(w); //访问顶点w
visited[w]=TRUE; //对w做已访问标记
EnQueue(Q,w); //顶点w入队列
}
}
}
}
2.1.1 BFS算法求解单源最短路径问题
//初始化路径长度，顶点u做标记改自身到自身路径为0，入队，队不为空，队头元素出队，访问该队头元素的邻接点，若邻接点未被访问，则标记，路径长度加一，入队；过无邻接点则继续下一个元素出队
void BFS_MIN_Distance(Graph G,int u){
//d[i]表示从u到i结点的最短路径
for(int i = 0; i<G.vexnum;++i)
d[i]=INFINITY; //初始化路径长度无穷
visited[u]=true;
d[u]=0;
EnQueue(Q,u);
while(!IsEmpty(Q)){ //BFS算法主过程
DeQueue(Q,u); //队头元素u出队
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,u,w)){
if(!visited[w]){ //w为u的尚未访问的邻接顶点
visited[w]=true; //访问已访问标记
d[w]=d[u]+1; //路径长度加1
EnQueue(Q,w); //顶点w入队
}
}
}
2.2 深度优先搜索DFS
图的深度优先遍历类似于树的先序遍历，借助递归栈来实现
bool visit[MAX_VERTEX_NUM]; //访问标记数组
//初始化标记数组和队列，并对每个结点顶点进行访问标记数组，若还没有被访问则调用DFS
void DSFTraverse(Graph G){
//对图G进行深度优先遍历
for(v = 0 ; v<G.vexnum ;++v)
visit[v]=false; //访问顶点标记数组初始化
for(v = 0;v<G.vexnum;++v)
if(!visited[v])
DFS(G,v); //Vi未访问过，从Vi开始BFS
}
//深度优先遍历
//访问顶点，做标记，访问该顶点的邻接点，若邻接点未被访问，则递归调用DFS
void DFS(Graph G,int v){
//从顶点v出发，采用递归，深度优先遍历图G
visit(v); //访问顶点v
visited[v] = true; //对v做已访问标记
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
if(!visited[w]){ //w为v的尚未访问的邻接顶点
DFS(G,w);
}
}
}
3. 图的应用
3.1 最小生成树
//伪代码
GENERIC_MST(G){
T=NULL;
while T 未形成一颗生成树;
do 找到一条最小代价边(u,v)并且加入T后不会产生回路;
T = T(u,v);
}
3.1.1 Prime算法
思想（选顶点）：先选一个顶点加入T中，选择一个与T中顶点集合距离最近的顶点，并将此顶点和相应的边加入T中，每次操作后顶点数和边数加一。以此类推，知道所有顶点都加入T中。
//伪代码
void Prim(G,T){
T=; //初始化空树
U={w}; //添加任一顶点w
while((v-U)!= ){ //若树中不含全部顶点
设(u,v)是使u U与v (V-U)，且权值最小的边;
T=T{(u,v)}; //边归入树
U=U {v};//顶点归入树
}
}
3.1.1 Kruskal算法
思想（选边）：初始时为只有n个顶点而无边的非连通图，每个顶点自成一个连通分量，按照权值由小到大排序，不断选取当前未被选取过且权值最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入T，否则舍弃此边而选择下一条权值最小的边。以此类推，直至T中所有顶点都在一个连通分量上。
//伪代码
void Kruskal(V ,T){
T=v; //初始化树T，仅含顶点
numS=n; //连通分量数
while(numS>1){ //如果连通分量数大于1
从E中取出权值最小的边(v ,u);
if(v和u属于T中不同的连通分量){
T=T {(v ,u)}; //将此边加入生成数中
numS--; //连通分量数减1
}
}
3.2 拓扑排序
3.2.1 拓扑排序
bool TopologicalSort(Graph G){
//如果G存在拓扑排序，则返回true，否则返回flase，这时G中存在环
InitStack(S); //初始化栈
//存储入度为0的顶点
for(int i = 0; i < G.vexnum; ++i){
if(indegree[i]==0)
Push(S,i); //将所有入度为0的顶点进栈
}
int count = 0; //计数，记录当前已经输出的顶点数
while(!IsEmpty(S)){ //栈不空，则存在入度为0的顶点
Pop(S,i); //栈顶元素出栈
print[count++]=i; //输出顶点i
for(p=G.vertices[i].firstarc;p=p->nextarc){ //将所有i指向的顶点的入度减1，并将入度减为0的顶点压入栈S
v = p->adjvex;
if(!(--indegree[v]))
Push(S,v); //入度为0，则入栈
}
}
if(count < G.vexnum)
return false; //排序失败，说明有向图中有回路
else
return true; //拓扑排序成功
}
3.2.2 逆拓扑排序(DFS算法)
void DFSTraverse(Graph G){ //对图G进行深度优先遍历
for(v = 0; v<G.vexnum;++v)
vivited[v] = flase; //初始化已访问标记数据
for(v = 0; v<G.vexnum;++v)
if(!visited[v])
DFS(G,v);
}
void DFS(Graph G,int v){ //从顶点v触发，深度优先遍历图G
visit(v); //设已访问标记
visited[v] = true;
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighor(G,v,W))
if(!visited[w]){ //w为u的尚未访问的邻接顶点
DFS(g,W);
}
print(v); //输出顶点
}
邻接矩阵存储结构的 NextNeighbor 函数:
int NextNeighbor(MGraph &G, int x, int y){
if(x != -1&&y != -1){
for (int col=y+1;col < G.vexnum ; col++){
if(G.Edge[x][col]>0 && G.Edge[x][co1]<maxWeight)
return col;//maxWeight代表无穷
}
}
return -1;
}
邻接表做存储结构的 NextNeighbor 函数:
int NextNeighbor(ALGraph &G, int x, int y){
if(x != -1){//顶点x存在
ArcNode *p=G.vertices[x].first; //对应边链表第一个边结点
while(p!=NULL&&p->data!=y) //寻找邻接顶点Y
p = p->next;
if(p!=NULL&&p->next !=NULL)
return p->next->data; //返回下一个邻接顶点
}
return -1;
}