第C語言鄰接表建立圖詳解scanf_s("%d%d",v1,v2);

ENode*p1=(ENode*)malloc(sizeof(ENode));//為新建的邊申請空間

p1-ivex=v2;//該邊指向的節(jié)點

//頭插法建立

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==0e==0)

break;

LGraph*pG;

pG=create();

return0;

無向圖

在代碼的建立鏈表的地方變成

//建立鏈表

for(inti=0;i++i)

intv1,v2;

scanf_s("%d%d",v1,v2);

ENode*p1=(ENode*)malloc(sizeof(ENode));//為新建的邊申請空間

p1-ivex=v2;//該邊指向的節(jié)點

//頭插法建立

p1-next_edge=pG-vexs[v1].fidt_edge;

pG-vexs[v1].fidt_edge=p1;

//另一條邊

ENode*p2=(ENode*)malloc(sizeof(ENode));//為新建的邊申請空間

p2-ivex=v1;//該邊指向的節(jié)點

//頭插法建立

p2-next_edge=pG-vexs[v2].fidt_edge;

pG-vexs[v2].fidt_edge=p2;

鄰接表存圖進行拓撲排序

#includestdio.h

#includestdlib.h

#includestring.h

#includestack

usingnamespacestd;

#definemaxn200

intv,e;

//表結點

typedefstruct_Enode

intivex;//該邊所指向的節(jié)點位置

struct_Enode*next_edge;//指向下一條邊

}ENode,*PENode;

//頭結點

typedefstruct_VNode

intdata;

intindegree;//記錄定點的入度

ENode*fidt_edge;

}VNode;

//鄰接表

typedefstruct_LGraph

intvex_num;//點的數(shù)量

intedg_num;//邊的數(shù)量

VNodevexs[maxn];//一維數(shù)組存表頭節(jié)點

}LGraph;

LGraph*create()

LGraph*pG;

pG=(LGraph*)malloc(sizeof(LGraph));

memset(pG,0,sizeof(LGraph));

pG-vex_num=v;//頂點數(shù)

pG-edg_num=e;//邊數(shù)

for(inti=0;i++i)//初始化定點表的指針域為空

pG-vexs[i].fidt_edge=NULL;

for(inti=0;i++i)

intv1,v2;

scanf_s("%d%d",v1,v2);

ENode*p1=(ENode*)malloc(sizeof(ENode));//為新建的邊申請空間

p1-ivex=v2;//該邊指向的節(jié)點

//頭插法建立

p1-next_edge=pG-vexs[v1].fidt_edge;

pG-vexs[v1].fidt_edge=p1;

returnpG;

voidTopSort(LGraph*pG)

stackint

intcount,k,i;

ENode*p;

for(inti=0;i++i)//記錄各個頂點的入度

//遍歷整個鄰接表，如果表結點的值為i，則i對應的頭結點的入度加1

p=pG-vexs[i].fidt_edge;//獲得其指向的第一條邊

while(p)

pG-vexs[p-ivex].indegree++;//該邊表存的位置對應的頭結點的入度數(shù)量加1

p=p-next_edge;

//將入度為0的壓入棧中

for(inti=0;i++i)

if(pG-vexs[i].indegree==0)s.push(i);

count=0;//對輸出的頂點計數(shù)

while(!s.empty())

intk=s.top();//取出

s.pop();

++count;

//與k節(jié)點相鄰的節(jié)點的入度減1

for(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(countpG-vex_num)

printf("NO\n");

else

printf("YES\n");

intmain()

while(~scanf_s("%d%d",v,e))

if(v=