6.2图的存储及基本操作
6.2.1邻接矩阵法
图的邻接矩阵存储结构定义如下：
#define MaxVertexNUm 100 //顶点数目的最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{VertexType Ver[MaxVertexNum]; //顶点表EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵,边表int vexnum,arcnum; //图的当前顶点数和弧数
}MGraph;6.2.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; //ALGraph是以邻接表存储的图类型6.2.3十字链表
6.2.4邻接多重表
6.2.5图存储小结
6.3图的遍历
6.3.1广度优先搜索(BFS)
1.广度优先搜索算法的伪代码如下：
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void BFSTraverse(Graph G){ //对图G进行广度优先遍历for(i=0;i<G.vexnum;++i)visited[i]=FALSE; //访问标记数组初始化InitQueue(Q); //初始化辅助队列Qfor(i=0;i<G.vexnum;++i) //从0号顶点开始遍历if(!visited[i]) //对每个连通分量调用一次BFSBFS(G,i); //Vi未访问过,从Vi开始BFS
}
void BFS(Graph G,int v){ //从顶点v出发,广度优先遍历图Gvisit(v); //访问初始顶点vvisited[v]=TRUE; //对v做已访问标记EnQueue(Q,v); //顶点v入队列Qwhile(!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); //访问顶点wvisited[w]=TRUE; //对w做已访问标记EnQueue(Q,w); //顶点w入队列}}
}2.BFS算法求解单源最短路径问题的算法如下：
void BFS_MIN_Distance(Graph G,int u){for(i=0;i<G.vexnum;++i)d[i]=∞; //初始化路径长度visited[u]=TRUE; d[u]=0;EnQueue(Q,u);while(!isEmpty(Q)){ //BFS算法主过程DeQueue(Q,u); //对头元素u出队for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))if(!visited[w]){ //w为u的尚未访问的邻接顶点visited[w]=TRUE; //设已访问标记d[w]=d[u]+1; //路径长度加1EnQueue(Q,w); //顶点w入队}}
}6.3.2深度优先搜索(DFS)
1.用递归进行深度优先搜索算法过程如下:
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void DFSTraverse(Graph G){ //对图G进行深度优先遍历for(v=0;v<G.vexnum;++v)visited[v]=FALSE; //初始化已访问标记数组for(v=0;v<G.vexnum;++v) //本代码中是从v=0开始遍历if(!visited[v])DFS(G,v);
}
void DFS(Graph G,int v){ //从顶点v出发,深度优先遍历图Gvisit(v); //访问顶点vvisited[v]=TRUE; //设已访问标记for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))if(!visited[w]){ //w为v的尚未访问的邻接顶点DFS(G,w);}
}6.4图的应用
6.4.1最小生成树
1.通用的最小生成树算法如下：
GENERIC_MST(G){T=NULL;while T 未形成一棵生成树;do 找到一条最小代价边(u,v)并且加入T后不会产生回路;T=T∪(u,v);
}2.Prim算法
Prim算法的简单实现如下：
void Prim(G,T){T=∅; //初始化空树U={w}; //添加任意一个顶点wwhile((V-U)!=∅){ //若树中不含全部顶点设(u,v)是使u∈U与v∈(V-U),且权值最小的边;T=T∪{(u,v)}; //边归入树U=U∪{v}; //顶点归入树}
}3.Kruskal算法
Kruskal算法的步骤如下：
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}}
}6.4.2最短路径
1.Dijkstra算法求单源最短路径问题
2.Floyd算法求各顶点之间最短路径问题
Floyd算法实现如下：
//......准备工作,根据图的信息初始化矩阵A和path(如上图)
for(int k=0;k<n;k++){ //考虑以Vk作为中转点for(int i=0;i<n;i++){ //遍历整个矩阵,i为行号,j为列号for(int j=0;j<n;j++){if(A[i][j]>A[i][k]+A[k][j]){ //以Vk为中转点的路径更短A[i][j]=A[i][k]+A[k][j]; //更新最短路径长度path[i][j]=k; //中转点}}}
}6.4.3求最短路径小结
6.4.4有向无环图描述表达式
6.4.5拓扑排序
拓扑排序算法的实现如下：
bool TopologicalSort(Graph G){InitStack(S); //初始化栈,存储入度为0的顶点int i;for(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; //输出顶点ifor(p=G.vertices[i].firstarc;p;p=p->nextarc){//将所有i指向的顶点的入度减1,并且将入度减为0的顶点压入栈Sv=p->adjvex; if(!(--indegree[v]))Push(S,v); //入度为0,则入栈}}//whileif(count<G.vexnum)return false; //排序失败,有向无环图中有回路elsereturn true; //拓扑排序成功
}6.4.6关键路径
