|
本文共 4627 字，大约阅读时间需要 15 分钟。
//这里整理的为图那里的算法//邻接矩阵和邻接表的图的表示很重要//这里就不说明MAXSIZE就为最大值的默认了typedef struct ArcCell{ VRType adj;//这里是点中的值 InfoType *info;//这里是有关点的信息比如这里可以放权值 }ArcCel,AdjMatrix[MAXSIZE][MAXSIZE]; //后面的是矩阵typedef struct MGraph{ VertexType vexs[MAXSIZE]; //这里是顶点表AdjMatrix arcs; //这里是邻接矩阵边表int vexnum; //顶点的数目int arcnum; //边的数目GraphKind kind; //图的种类}MGraph;//这里是邻接表的表示方法很重要typedef struct ArcNode{ //边节点int adjvex; //指向弧所指向的顶点的位置ArcNode* nextarc; //指向下一条弧的指针InfoType *info; //该相关弧的信息}ArcNode;typedef struct VexNode{ //顶点节点ElemType data; //顶点信息ArcNode* firstarc; //指向第一条依附该顶点的指针}VexNode,AdjList[MAXSIZE];typedef struct ALGraph{AdjList vertices; //顶点组成的数组int vexnum; //顶点数目int arcnum; //边数目GraphKind kind;}ALGraph;//拓扑排序的代码//拓扑排序的原理就是每次把入度为0的节点删除，然后再把与其相连的边也删去。//拓扑排序可以检验是否图中有环bool Topologicalsort(MGraph M){Stack s;//这里需要一个栈来保存入度为0的节点init(s);int count = 0; //这里记录入度为0的节点的个数for(int i = 1;i firstarc;p;p=p->nextarc) //这里的代码的意思就是删去和刚才出栈的节点的邻接边的入度的数目{int i = p->adjvex; //这里找到邻接边所对应的弧所指向的顶点的位置if(--indegree[i] == 0) //删除邻接边的入度的数目 即就是把入度数目减去1{push(s,i) //若入度数目为0，则把其压栈说明他是拓扑排序的下一个节点}}}return count == M.vexnum?true:false;//如果所有的节点都最后度为0，那么说明可以拓扑排序，若不可以则不行；}//最小生成树 这里的图使用邻接矩阵表示的//时间复杂度 O(n^2) //这里的closedge保存的是顶点adj和它邻接顶点中邻接边权值最小的邻接点和权值typedef struct closedge{VerTexType adjvex; //这里为邻接顶点VRType lowcost; //这里为邻接顶点的权值}closedge[MAXSIZE]; //因为有好多的顶点所有用一个数组来表示void MinSpanTreePrim(MGraph G,VertexType u)//prime需要一个图和一个顶点作为参数{int k =LocateVex(G,u) //定位顶点u在图G中的位置for(int i = 0;i
//根据图的信息更新closedge G.adjlist[k][i].adj这个保存的是i和k之间的权值
{
if(k==i)
closedge[i]={u,G.arcs[k][i]};
}
closedge[k].lowcost = 0;
//这里把closedge[k].lowcost更新为0，说明了把节点k已经加入了最小生成树之中了
for(int j = 1;j
//因为已经有一个节点加入到最小生成树中了，所以循环只需要1-G.vexnum之间
{
k=minmum(closedge);
//找到closedge中的lowcost最小值顶点
closedge[k].lowcost = 0;
//把最小的lowcost加入到最小生成树中
for(int l = 0;l
//更新K周围的邻接点的最小权值
{
if(G.arcs[k][l] firstarc;p&&;p=p->nextarc)//找k节点邻接节点入队
{
int k = p->adjvex;
if(!visited[k])
//找到未访问的标记并且访问之后再入队列
{
visit(k);
visited[k] = 1;
EnQueue(Q,k);
}
}
}}//深度度优先遍历int visited[MAXSIZE];void DFSTraver(MGraph G,int v){
for(int i = 0;i
//每个节点都进行深度优先遍历
{
if(!visited[i])
{
DFS(G,i)
}
}}void DFS(MGraph G,int v){
visited[v] = 1;
visit(v);
for(VexNode* p = G.adjlist[v]->firstarc;p;p=p->nextarc)//邻接边进行深度优先遍历
{
int i = p->adjvex;
if(!visited[i])
{
DFS(G,i)
}
}}
;++i)>
;++i)>
;++k)>
;++j)>
;++i)>
;++k)>
;++j)>
;++m)>
;++l)>
;++j)>
;++i)>
转载地址：https://blog.csdn.net/GyafdxIs/article/details/61925021 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
|