圖的關節節點

圖的關節節點是一種關於割點的指示代碼。

基本介紹

• 中文名：圖的關節節點
• 別名：割點
• 表現形式：代碼
• 分割：連通分量

圖的關節節點也成為割點，刪去關節節點圖將會被分割成幾個連通分量

代碼如下

void DFSArticul(ALGraph G,int v0)

{int min,w;

ArcNode *p;

visited[v0]=min=++count;

for(p=G.vertices[v0].firstarc;p;p=p->nextarc)

{

w=p->adjvex;

if(visited[w]==0)

{

DFSArticul(G,w);

if(low[w]<min) min= low[w];

if(low[w]>=visited[v0]) printf("%d \n", G.vertices[v0].data);

}

}

low[v0]=min;

}

void FindArticul(ALGraph G)

{

int i,v;

ArcNode *p;

p=(ArcNode *)malloc(sizeof(ArcNode));

for(i=0;i<G.vexnum;++i) visited[i]=0;

p=G.vertices[0].firstarc;

// v=(p->adjvex);

DFSArticul(G,1);

if(count<G.vexnum)

{

printf("%d %d",0,G.vertices[0].data );

while(p->nextarc)

{

p=p->nextarc;

v=p->adjvex;

if(visited[v]==0)

DFSArticul(G,v);

}

}

}