o1101574955的专栏

图论算法小结

//邻接矩阵存储结构定义如下：//邻接矩阵包含两种数组：顶点表和边表#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);//初始化辅助队列Qfor(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，算法借助一个辅助队列Qvisit(v);//访问初始顶点vvisited[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);//访问顶点wvisited[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;//路径长度加1EnQueue(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出发，采用递归思想，深度优先遍历图Gvisit(v);//访问顶点vvisited[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;elsereturn 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;elsereturn 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;elsereturn 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]){//DFSwhile(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;}elsebreak;}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）。//法一：BFSbool 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;}//法二：DFSbool 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，，这里采用递归DFSreturn 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的所有简单路径//法一：非递归DFSbool 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;//Pushv=FirstNeighbor(G,v);}elsebreak;}w=s[top–];//Popvisited[w]=FALSE//退栈时清除访问标记v=s[top];//GetTopw=NextNeighbor(G,v,w);while(w>=0 && visited[w])w=NextNeighbor(G,v,w);v=w;}}//法二：递归DFSbool 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 5typedef 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];//有边的点对应的是边的权值，没有边的点对应的是INFINITYcloseset[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;}}}//Kruskaltypedef 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];elsebreak;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;elsereturn 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;}

当你感到悲哀痛苦时，最好是去学些什么东西。