图论算法小结
浏览数：33 /
时间：2015年06月08日
图论算法小结
//邻接矩阵存储结构定义如下：
//邻接矩阵包含两种数组：顶点表和边表
#define MaxVertexNum 100 //顶点数目的最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct{
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表
int vexnum,arcnum; //图的当前顶点数和弧数
}AGraph;
//邻接表法：
//邻接表中存在两种结点：顶点表结点和边表结点。其中，顶点表包含：顶点域和边表头指针；边表结点包含：邻接点域和指针域
#define MaxVertexNum 100 //图中顶点数目的最大值
typedef struct ArcNode{ //边表结点
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *next; //指向下一条弧的指针
//InfoType ifo; //网的边权值
}ArcNode;
typedef struct VNode{ //顶点表结点
VertexType data; //顶点信息
ArcNode *first; //指向第一条依附该顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{
AdjList vertices; //邻接表
int vexnum,arcnum; //图的顶点数和弧数
}ALGraph; //ALGraph是以邻接表存储的图类型
/*
说明：
ALGraph G;
G.vertices[i]:邻接表中顶点表数组中的元素（是一个结构体）。
p=G.vertices[i].first:邻接表中顶点表数组中下标为i的元素指向的第一个边表结点的地址（也即指向的第一个边表结点）。
p->adjvex:边表结点的结点号。
p->next:下一个边表结点的地址（也即指向的下一个边表结点）。
"v=FirstNeighbor(G,i);"等价于："v=G.vertices[i].first->adjvex;"
FirstNeighbor(G,x):求图中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
NextNeightor(G,x,y):假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
对于图的不同的存储结构留有相同的函数，例如：
//以邻接矩阵作存储结构
int NextNeighbor(AGraph 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][col]<maxWeight) //maxWeight代表无穷
return col;
}
return -1;
}
//以邻接表作存储结构
int NextNeighbor(ALGraph G,int x,int y){
if(x!=-1){
ArcNode *p=G.vertices[x].first;
while(p!=NULL && p->data!=y)
p=p->next;
if(p!=NULL && p->next!=NULL)
return p->next->data;
}
return -1;
}
*/
//从图的邻接表表示转换成邻接矩阵表示的算法：
void Convert(ALGraph &G,int arcs[N][N]){
int i=0,t=0;
for(i=0;i<N;i++){
for(t=FirstNeighbor(A,i);t>=0;t=NextNeighbor(A,i,t))
arcs[i][t]=1;
}
}
//或者：
void Convert(ALGraph &G,int arcs[N][N]){
int i=0;
ArcNode p;
for(i=0;i<N;i++){
p=G.vertices[i].first; //或者：p=((&G)->vertices[i]).first;
while(p!=NULL){
arcs[i][p->data]=1;
p=p->nextarc;
}
}
}
//广度优先搜索（Breadth-First-Search,BFS）
bool visited[MAX_VERTEX_NUM); //访问标记数组
void BFSTraverse(Graph G){ //对图G进行广度优先遍历，设访问函数为visit()
for(i=0;i<G.vexnum;i++)
visited[i]=FALSE; //访问标志数组初始化
InitQueue(Q); //初始化辅助队列Q
for(i=0;i<G.vexnum;i++) //从0号顶点开始遍历
if(!visited[i]) //对每个连通分量开始遍历
BFS(G,i); //v[i]未访问过，从v[i]开始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入队列
}
}
}
//BFS算法求解单源最短路径问题的算法：
void BFS_MIN_Distance(Graph G,int u){ //d[i]表示从u到i结点的最短路径
for(i=0;i<G.vexnum;i++)
d[i]=INF //初始化路径长度为无穷
visited[u]=TRUE;
d[u]=0;
EnQueue(Q,u);
while(!isEmpty(Q)){ //BFS算法主过程
DeQueue(Q,u);
for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
if(!visited[w]){
visited[w]=TRUE;
d[w]=d[u]+1; //路径长度加1
EnQueue(Q,w);
}
}
}
//深度优先搜索（Depth-First-Search,DFS）
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void DFSTraverse(Graph G){ //对图G进行尝试优先遍历，访问函数为visit()
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出发，采用递归思想，深度优先遍历图G
visit(v); //访问顶点v
visited[v]=TRUE; //设已访问标记
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
if(!visited[w]){ //w为u的尚未访问的邻接顶点
DFS(G,w);
}
}
//判断一个无向图G是否为一棵树
//思路：一个无向图G是一棵树的条件是：G必须是无回路的连通图或者是有n-1条边的连通图（这里采用后一种方法）
//法一：广度优先搜索
bool visited[MAX_VERTEX_NUM]；
int Vnum=0,Enum=0;
bool IsTree1(Graph G){
int v=0,w;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE;
v=0;
visited[v]=TRUE;
EnQueue(Q,v);
Vnum=1;
while(!IsEmpty(Q)){
DeQueue(Q,v);
for(w=FirstNeighbor(Q,v);w>=0;w=NextNeighbor(G,v,w)){
Enum++;
if(!visited[w]){
visited[w]=TRUE;
EnQueue(Q,w);
Vnum++;
}
}
}
if(Vnum==G.vexnum && Enum==2*(G.vernum-1))
return TRUE;
else
return FALSE;
}
//法二：深度优先搜索：
bool visited[MAX_VERTEX_NUM]；
int Vnum=0,Enum=0;
bool IsTree2(Graph G){
for(i=1;i<=G.vexnum;i++)
visited[i]=FALSE;
DFS(G,1);
if(Vnum==G.vexnum && Enum==2*(G.vexnum-1))
return TRUE;
else
return FALSE;
}
void DFS(Graph G,int v){
visited[v]=TRUE;
Vnum++;
int w=FirstNeighbor(G,v);
while(w!=-1){ //可以写成for的形式
Enum++;
if(!visited[w])
DFS(G,w);
w=NextNeighbor(G,v,w);
}
}
//附：判断一个有向图是否为一棵树的算法： //这个好像有点问题？？？
int Vnum=0;
bool visited[MAX_VERTEX_NUM];
bool IsTree(Graph G){
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE;
if(!DFS(G,v))
return FALSE;
if(Vnum==G.vexnum)
return TRUE;
else
return FALSE;
}
bool DFS(Graph G,int v){
visited[v]=true;
Vnum++;
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
if(visited[w])
return FALSE;
if(!DFS(G,w)) //如果访问到了已访问过的结点，就一直返回FALSE，直到退出，说明不是一个棵。
return FSLSE;
}
return TRUE;
}
//DFS的非递归算法：
//法一：此算法栈叶元素是v到i的路径，但是仅仅是一条路径，无法找到所有路径。（下面有一个算法可以打印所有简单路径。）
bool visited[MAX_VEXNUM_NUM];
void DFS_Non_RC(ALGraph G,int v){
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE;
InitStack(S);
for(v=0;v<G.vexnum;v++)
if(!visited[v]){
//DFS
while(v>=0 || !IsEmpty(S)){
while(v>=0){
if(!visited[v]){
visit(v);
visited[v]=TRUE;
Push(S,v);
v=FirstNeighbor(G,v); //或v=G.vertices[v].first->adjvex;
}
else
break;
}
Pop(S,w);
GetTop(S,v);
w=NextNeighbor(G,v,w);
while(w>=0 && visited[w]) //退出循环时，w可能为-1或者是w>=0但是没有被访问过
w=NextNeighbor(G,v,w);
v=w;
}
}
}
//法二：此算法是从右端到左端的顺序进行的。栈中的元素不是v到i的路径。
bool visited[MAX_VEXNUM_NUM];
void DFS_Non_RC(ALGraph G,int v){
int w;
InitStack(S);
for(i=0;i<G.vexnum;i++)
visited[i]=FALSE;
Push(S,v);
visited[v]=TRUE;
while(!IsEmpty(S){
k=Pop(S);
visit(k);
for(w=FirstNeighbor(G,k);w>=0;w=NextNeighbor(G,k,w))
if(!visited[w]){
Push(S,w);
visited[w]=TRUE;
}
}
}
//判断以邻接表方式存储的有向图中是否存在同顶点i到顶点j的路径（i!=j）。
//法一：BFS
bool visited[MAX_VEXNUM_NUM];
bool BFSTest(ALGraph G,int i,int j){
int v=0;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE;
InitQueue(Q);
EnQueue(Q,i);
visited[i]=TRUE;
while(!IsEmpty(Q)){
DeQueue(Q,v);
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
if(w==j)
return TRUE;
if(!visited[w]){
EnQueue(Q,w);
visited[w]=TRUE;
}
}
}
return FALSE;
}
//法二：DFS
bool visited[MAX_VEXNUM_NUM];
bool DFSTest(ALGraph G,int i,int j){
int v=0;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE;
//可采用非递归DFS，这里采用递归DFS
return DFS(G,i,j);
}
bool DFS(ALGraph G,int i,int j){
visited[i]=TRUE;
for(w=FirstNeighbor(G,i);w>=0;w=NextNeighbor(G,i,w)){
if(w==j)
return TRUE;
if(!visited[w])
if(DFS(G,w,j)) //如果找到，一直返回TRUE，直到退出
return TRUE;
}
return FALSE;
}
//输出图中从顶点i到顶点j的所有简单路径
//法一：非递归DFS
bool visited[MAX_VEXNUM_NUM];
void DFS_Non_RC_Path(AGraph G,int i,int j){
int S[MAX_VEXNUM_NUM]; //栈
int top=-1,v=0;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE;
while(v>=0 || top!=-1){
while(v>=0){
if(!visited[v]){
if(v==j){ //打印路径
for(i=0;i<=top;i++)
printf("%d ",S[i]);
printf("%d\n",j);
break;
}
visited[v]=TRUE;
S[++top]=v; //Push
v=FirstNeighbor(G,v);
}
else
break;
}
w=s[top--]; //Pop
visited[w]=FALSE //退栈时清除访问标记
v=s[top]; //GetTop
w=NextNeighbor(G,v,w);
while(w>=0 && visited[w])
w=NextNeighbor(G,v,w);
v=w;
}
}
//法二：递归DFS
bool visited[MAX_VEXNUM_NUM];
int d=-1;
int path[MAX_VEXNUM_NUM];
void FindPath(AGraph G,int i,int j){
int v=0;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE;
DFS_Path(G,i,j);
}
void DFS_Path(ALGraph G,int u,int v){
int w;
ArcNode *p;
d++;
path[d]=u;
visited[u]=TRUE;
if(u==v)
print(path,d+1);
p=G.vertices[v].first; //* 可以改为：for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
while(p!=NULL){ //* if(!visited[w])
w=p->adjvex; //* DFS_Path(G,w,v);
if(!visited[w]) //*
DFS_Path(G,w,v); //*
p=p->next; //*
} //*
visited[u]=FALSE;
d--;
}
-------------------------------------------------------------------------------------------------------------------
************************************************** 图的应用 *****************************************************
-------------------------------------------------------------------------------------------------------------------
//最小生成树（Minimum-Spanning-Tree,MST)
//Prim（对比最短路径中的Dijkstra算法）
#define INFINITY 10000
#define MAX_VERTICES 5
typedef int Graph[MAX_VERTICES][MAX_VERTICES];
void prim(Graph G,int vcount,int father[]){
int i,j,k;
int lowcost[MAX_VERTICES],closeset[MAX_VERTICES],used[MAX_VERTICES];
for(i=0;i<vcount;i++){
lowcost[i]=G[0][i]; //有边的点对应的是边的权值，没有边的点对应的是INFINITY
closeset[i]=0; //最小权值边在已加入点集中的点
used[i]=0;
father[i]=-1;
}
//此时，0点已经在已加入点集中，但是并不把used[0]设置为1，因为，此时才刚开始，还不知道哪个点与0连成的边的权值最小
for(i=1;i<vcount;i++){
j=0;
while(used[j]) j++;
for(k=0;k<vcount;k++)
if(!used[k] && lowcost[k]<lowcost[j]) j=k;
father[i]=closeset[j]; //这个father[]可以不要，因为，已加入到已加入点集中的点的closeset[]值不会变，最终程序退出时，closeset[]中就会有相应的信息
used[j]=1; //每加入一个点，就更新未加入点到已加入点集中的点的最短路径信息
for(k=0;k<vcount;k++)
if(!used[k] && G[j][k]<lowcost[k]){ //更新最短路径信息
lowcost[k]=G[j][k];
closeset[k]=j;
}
}
}
//Kruskal
typedef struct {
int a;
int b;
int pri;
} Node;
void kruskal(Graph G,int Vcount,int Ecount,int father[]){
Node p[Ecount],temp;
int t=0,i,j;
for(i=0;i<Vcount;i++)
for(j=0;j<Vcount;j++)
if(i!=j){
temp.a=i;
temp.b=j;
temp.pri=G[i][j];
for(k=t-1;k>=0;k--)
if(p[k].pri > temp.pri)
p[K+1]=p[k];
else
break;
p[k+1]=temp;
t++;
}
//生成树
memset(used,0,sizeof(used));
memset(father,-1,sizeof(father));
for(i=0;i<t;i++)
if(!used[p[i].a] || !used[p[i].b]){ //只要此边有一个点不在used中，就加入此边
used[p[i].a]=used[p[i].b]=1;
father[p[i].b]=p[i].a;
}
//假设图一定能生成一棵树，这里就不用判断了。
}
//最短路径
//Dijkstra求单源最短路径
void Dijkstra(Graph G,int Vcount,int s,int path[],int dist[]){ //Vcount:顶点个数；s:开始结点；path[]用于返回由开始结点到相应结点的路径指示
int i,j,w,minc,dist[Vcount],mark[Vcount];
memset(mark,0,Vcount);
for(i=0;i<Vcount;i++){
dist[i]=G[s][i];
path[i]=s;
}
mark[s]=1;path[s]=0;dist[s]=0;
for(i=1;i<Vcount;i++){
minc=INFINITY;
w=0;
for(j=0;j<Vcount;j++)
if(!mark[j] && minc>=dist[j]){
minc=dist[j];
w=j;
}
mark[w]=1;
for(j=0;j<Vcount;j++)
if(!mark[j] && G[w][j]!=INFINITY && dist[j]>dist[w]+G[w][j]){
dist[j]=dist[w]+G[w][j];
path[j]=w;
}
}
}
//注意：输入的图的边的权值必须非负（这是Dijkstra的局限性所在）.
//顶点号从0开始，用如下方法打印路径：
void printpath(int path[],int s,int t){ //t:目标结点
int i=t;
while(i!=s){
printf("%d<--",i+1);
i=path[i];
}
printf("%d\n",s+1);
}
//Floyd_Warshall算法（简称为：Floyd算法）用于求各顶点之间最短路径问题
void Floyd_Warshall(Graph G,int Vcount,Graph D,Graph P){ //D:D[i][j]表示从i到j的最短距离；P:P[i][j]表示从i到j的最短路径上的结点
int i,j,k;
for(i=0;i<Vcount;i++)
for(j=0;j<Vcount;j++){
D[i][j]=G[i][j];
P[i][j]=i;
}
for(i=0;i<Vcount;i++){
D[i][i]=0;
P[i][i]=0;
}
for(k=0;k<Vcount;k++)
for(i=0;i<Vcount;i++)
for(j=0;j<Vcount;j++)
if(D[i][j]>D[i][k]+D[k][j]){
D[i][j]=D[i][k]+D[k][j];
P[i][j]=P[k][j];
}
}
//顶点号从0开始，用如下方法打印路径：
void printpath(int P[],int s,int t){ //s:出发结点；t:目标结点
int i=t;
while(i!=s){
printf("%d<--",i+1);
i=P[s][i];
}
printf("%d\n",s+1);
}
//Bellman_Ford:求单源最短路径
void Bellman_Ford(Graph G,int Vcount,int s,int path[],int &success){
int i,j,k,dist[Vcount];
for(i=0;i<n;i++){
dist[i]=INFINITY;
path[i]=0;
}
dist[s]=0;
for(k=1;k<Vcount;k++)
for(i=0;i<Vcount;i++)
for(j=0;j<Vcount;j++)
if(dist[j]>dist[i]+G[i][j]){
dist[j]=dist[i]+G[i][j];
path[j]=i;
}
success=0;
for(i=0;i<Vcount;i++)
for(j=0;j<Vcount;j++)
if(dist[j]>dist[i]+G[i][j])
return 0;
success=1;
}
//注意：输入的图的边的权可以为负（这也正是这个算法的用处所在），如果存在一个从源点可达的权为负的回路则success为0。
//顶点号从0开始，用如下方法打印路径：
void printpath(int path[],int s,int t){ //s:出发结点；t:目标结点
int i=t;
while(i!=s){
printf("%d<--",i+1);
i=path[i];
}
printf("%d\n",s+1);
}
//拓扑排序
//法一：
bool TopologicalSort(Graph G){
int i=0,count=0;
InitStack(S);
for(i=0;i<G.vexnum;i++)
if(indegree[i]==0)
Push(S,i);
while(!IsEmpty(S)){
Pop(S,i);
print[count++]=i;
for(p=G.vertices[i].first;p;p=p->next){
v=p->adjvex;
if(!(--indegree[v]))
Push(S,v)
}
}
if(count<G.vexnum)
return FALSE;
else
return TRUE;
}
//法二：利用DFS求各结点的访问结束时间，将结束时间从大到小排序即可得到一条拓扑序列。
bool visited[MAX_VERTEX_NUM];
int finishTime[MAX_VERTEX_NUM];
int time=0;
void DFS_Traverse(Graph G){
memset(visited,0,sizeof(visited));
memset(finishTime,0,sizeof(finishTime));
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v);
//对finishTime[]按时间值从大到小输出即得到一条拓扑序列
print(finishTime);
}
void DFS(Graph G,int v){
visited[v]=TRUE;
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
if(!visited[w])
DFS(G,w);
time+=1;
finishTime[v]=time;
}
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
