1、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={
写出G的拓扑排序的结果。
G拓扑排序的结果是:V1、V2、V4、V3、V5、V6、V7
2、连通图的生成树包括图中的全部n个顶点和足以使图连通的n-1条边,最小生成树是边上权值之和最小的生成树。故可按权值从大到小对边进行排序,然后从大到小将边删除。每删除一条当前权值最大的边后,就去测试图是否仍连通,若不再连通,则将该边恢复。若仍连通,继续向下删;直到剩n-1条边为止。
void SpnTree (AdjList g)
//用“破圈法”求解带权连通无向图的一棵最小代价生成树。
{typedef struct {int i,j,w}node; //设顶点信息就是顶点编号,权是整型数
node edge[];
scanf( "%d%d",&e,&n) ; //输入边数和顶点数。
for (i=1;i<=e;i++) //输入e条边:顶点,权值。
scanf("%d%d%d" ,&edge[i].i ,&edge[i].j ,&edge[i].w);
for (i=2;i<=e;i++) //按边上的权值大小,对边进行逆序排序。
{edge[0]=edge[i]; j=i-1;
while (edge[j].w edge[j+1]=edge[0]; }//for k=1; eg=e; while (eg>=n) //破圈,直到边数e=n-1. {if (connect(k)) //删除第k条边若仍连通。 {edge[k].w=0; eg--; }//测试下一条边edge[k],权值置0表示该边被删除k++; //下条边 }//while }//算法结束。 connect()是测试图是否连通的函数,可用图的遍历实现, 3、两棵空二叉树或仅有根结点的二叉树相似;对非空二叉树,可判左右子树是否相似,采用递归算法。 int Similar(BiTree p,q) //判断二叉树p和q是否相似 {if(p==null && q==null) return (1); else if(!p && q || p && !q) return (0); else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild)) }//结束Similar 4、4、void LinkList_reverse(Linklist &L) //链表的就地逆置;为简化算法,假设表长大于2 { p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) { q->next=p;p=q; q=s;s=s->next; //把L的元素逐个插入新表表头 } q->next=p;s->next=q;L->next=s; }//LinkList_reverse