鄰接表怎么畫(C語言如何鄰接表建立圖)

有向圖

代碼:

#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;}