资源描述：
《图的基本操作算法汇总_B5》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、//图的基本操作算法//1.voidCreatGraph(AdjListg)//建立有n个顶点和m条边的无向图的邻接表存储结构{intn,m;scanf("%d%d",&n,&m);for(i=1,i<=n;i++)//输入顶点信息,建立顶点向量{scanf(&g[i].vertex);g[i].firstarc=null;}for(k=1;k<=m;k++)//输入边信息{scanf(&v1,&v2);//输入两个顶点i=GraphLocateVertex(g,v1);j=GraphLocateVertex(g,v2);//顶点定位p=(ArcNode*)malloc(
2、sizeof(ArcNode));//申请边结点p->adjvex=j;p->next=g[i].firstarc;g[i].firstarc=p;//将边结点链入p=(ArcNode*)malloc(sizeof(ArcNode));//无向图双向连接p->adjvex=i;p->next=g[j].firstarc;g[j].firstarc=p;}}//算法CreatGraph结束//2.voidCreatAdjList(AdjListg)//建立有向图的邻接表存储结构{intn;scanf("%d",&n);for(i=1;i<=n;j++){scanf(&g[i
3、].vertex);图的基本操作算法汇总_A4第40页，总40页g[i].firstarc=null;}//输入顶点信息scanf(&v1,&v2);while(v1&&v2)//题目要求两顶点之一为0表示结束{i=GraphLocateVertex(g2,v1);p=(ArcNode*)malloc(sizeof(ArcNode));//有向图只需要单边p->adjvex=j;p->next=g[i].firstarc;g[i].firstarc=p;scanf(&v1,&v2);}}//5．voidInvertAdjList(AdjListgin,gout)//将有向
4、图的出度邻接表改为按入度建立的逆邻接表{for(i=1;i<=n;i++)//设有向图有n个顶点,建逆邻接表的顶点向量。{gin[i].vertex=gout[i].vertex;gin.firstarc=null;}//逆邻接表顶点初始化for(i=1;i<=n;i++)//邻接表转为逆邻接表{p=gout[i].firstarc;//取指向邻接表的指针邻接表头结点i的第一条边while(p!=null){j=p->adjvex;//邻接表边结点中的j顶点信息s=(ArcNode*)malloc(sizeof(ArcNode));//申请逆邻接表的边结点空间s
5、->adjvex=i;//对逆邻接表的边结点顶点信息赋值s->next=gin[j].firstarc;//对逆邻接表的边结点下一边信息赋值gin[j].firstarc=s;//边结点链入逆邻接表图的基本操作算法汇总_A4第40页，总40页p=p->next;//邻接表中找下一个邻接点。}//while}//for}//6.voidAdjListToAdjMatrix(AdjListgl,AdjMatrixgm)//将图的邻接表表示转换为邻接矩阵表示{for(i=1;i<=n;i++)//设图有n个顶点,邻接矩阵初始化。for(j=1;j<
6、=n;j++)gm[i][j]=0;for(i=1;i<=n;i++){p=gl[i].firstarc;//取第一个邻接点。while(p!=null){gm[i][p->adjvex]=1;p=p->next;}//下一个邻接点}//for}//算法结束//7.voidAdjMatrixToAdjList(AdjMatrixgm,AdjListgl)//图的邻接矩阵表示法转换为邻接表表示法{for(i=1;i<=n;i++)//邻接表表头向量初始化。{scanf(&gl[i].vertex);gl[i].firstarc=null;}for(i=1;i<=n;i++)
7、for(j=1;j<=n;j++)if(gm[i][j]==1)图的基本操作算法汇总_A4第40页，总40页{p=(ArcNode*)malloc(sizeof(ArcNode));//申请结点空间。p->adjvex=j;//顶点i的邻接点是jp->next=gl[i].firstarc;//下一个邻接边结点gl[i].firstarc=p;//链入顶点i的邻接点链表中}}//end//[算法讨论]算法中邻接表中顶点在向量表中的下标与其在邻接矩阵中的行号相同。//9.voidDeletEdge(AdjListg,inti,j
