有向图

代码:

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<stack>usingnamespacestd;#definemaxn200intv,e;//表结点typedefstruct_Enode{intivex;//该边所指向的节点位置intvalue;//如果边有权值的话,就对其赋值struct_Enode*next_edge;//指向下一条边}ENode,*PENode;//头结点typedefstruct_VNode{intdata;ENode*fidt_edge;}VNode;//邻接表typedefstruct_LGraph{intvex_num;//点的数量intedg_num;//边的数量VNodevexs[maxn];//一维数组存表头节点}LGraph;LGraph*create(){LGraph*pG;pG=(LGraph*)malloc(sizeof(LGraph));memset(pG,0,sizeof(LGraph));pG->vex_num=v;//顶点数pG->edg_num=e;//边数for(inti=0;i<v;++i)//初始化定点表的指针域为空pG->vexs[i].fidt_edge=NULL;//建立链表for(inti=0;i<e;++i){intv1,v2;scanf_s("%d%d",&v1,&v2);ENode*p1=(ENode*)malloc(sizeof(ENode));//为新建的边申请空间p1->ivex=v2;//该边指向的节点//头插法建立p1->next_edge=pG->vexs[v1].fidt_edge;pG->vexs[v1].fidt_edge=p1;}returnpG;}intmain(){while(~scanf_s("%d%d",&v,&e)){if(v==0&&e==0)break;LGraph*pG;pG=create();}return0;}

无向图

在代码的建立链表的地方变成

//建立链表for(inti=0;i<e;++i){intv1,v2;scanf_s("%d%d",&v1,&v2);ENode*p1=(ENode*)malloc(sizeof(ENode));//为新建的边申请空间p1->ivex=v2;//该边指向的节点//头插法建立p1->next_edge=pG->vexs[v1].fidt_edge;pG->vexs[v1].fidt_edge=p1;//另一条边ENode*p2=(ENode*)malloc(sizeof(ENode));//为新建的边申请空间p2->ivex=v1;//该边指向的节点//头插法建立p2->next_edge=pG->vexs[v2].fidt_edge;pG->vexs[v2].fidt_edge=p2;}

邻接表存图进行拓扑排序

#include<stdio.h>#include<stdlib.h>#include<string.h>#include<stack>usingnamespacestd;#definemaxn200intv,e;//表结点typedefstruct_Enode{intivex;//该边所指向的节点位置struct_Enode*next_edge;//指向下一条边}ENode,*PENode;//头结点typedefstruct_VNode{intdata;intindegree;//记录定点的入度ENode*fidt_edge;}VNode;//邻接表typedefstruct_LGraph{intvex_num;//点的数量intedg_num;//边的数量VNodevexs[maxn];//一维数组存表头节点}LGraph;LGraph*create(){LGraph*pG;pG=(LGraph*)malloc(sizeof(LGraph));memset(pG,0,sizeof(LGraph));pG->vex_num=v;//顶点数pG->edg_num=e;//边数for(inti=0;i<v;++i)//初始化定点表的指针域为空pG->vexs[i].fidt_edge=NULL;for(inti=0;i<e;++i){intv1,v2;scanf_s("%d%d",&v1,&v2);ENode*p1=(ENode*)malloc(sizeof(ENode));//为新建的边申请空间p1->ivex=v2;//该边指向的节点//头插法建立p1->next_edge=pG->vexs[v1].fidt_edge;pG->vexs[v1].fidt_edge=p1;}returnpG;}voidTopSort(LGraph*pG){stack<int>s;intcount,k,i;ENode*p;for(inti=0;i<v;++i)//记录各个顶点的入度{//遍历整个邻接表,如果表结点的值为i,则i对应的头结点的入度加1p=pG->vexs[i].fidt_edge;//获得其指向的第一条边while(p){pG->vexs[p->ivex].indegree++;//该边表存的位置对应的头结点的入度数量加1p=p->next_edge;}}//将入度为0的压入栈中for(inti=0;i<v;++i)if(pG->vexs[i].indegree==0)s.push(i);count=0;//对输出的顶点计数while(!s.empty()){intk=s.top();//取出s.pop();++count;//与k节点相邻的节点的入度减1for(p=pG->vexs[k].fidt_edge;p;p=p->next_edge){intto;to=p->ivex;pG->vexs[to].indegree--;//减为0的话就压入栈中if(pG->vexs[to].indegree==0)s.push(to);}}if(count<pG->vex_num)printf("NO\n");elseprintf("YES\n");}intmain(){while(~scanf_s("%d%d",&v,&e)){if(v==0&&e==0)break;LGraph*pG;pG=create();TopSort(pG);}return0;}