critical.h

此代码主要实现的是求图中关节点的C程序,一起讨论

#include "stdio.h"
#include "graph.h"
int visited[MAX_LEN];		//全局变量
int count;					//记访问的顶点个数
int low[MAX_LEN];			//
int min;
int crit[MAX_LEN];			//记录关节顶点
int k=0;					//记录关节点个数

bool is_not_in_crit(int v)
{
	int i=k,j=0;
	for(j=0;j<k;j++)
		if(crit[j]==v)
			return false;
	return true;

}
void dfs_articul(graph G,int v)
{
	count++;
	visited[v]=count;		//将访问顶点的序号放入visited[]
	min=visited[v];			//初始化访问初值
	struct edge *ed;
	ed=G.vp[v].next;
	ed=ed->next;			//寻找v的邻接点
	int w;
	while(ed!=NULL)
	{
		w=ed->seq;
		if(visited[w]==0)	//w hasn't been searched
		{
			dfs_articul(G,w);
			if(low[w]<min)
				min=low[w];
			if(visited[v]<=low[w])
			{
				if(is_not_in_crit(v))
				{
					//printf("\n\t the %d st node is a critical node !",v);
					crit[k++]=v;
				}
			}
		}
		else
			if(visited[w]<min)
				min=visited[w];
		ed=ed->next;
	}
	low[v]=min;
}


void get_critical(graph G)			//求出关节点
{
	FILE *fp,*fpd;//store the critical nodes
	FILE *fpdd;  //knn
	fp=fopen("critical.txt","w");
	if((fpd=fopen("crit_degree.txt","w"))==NULL) printf("can't open the file!\n");
	if((fpdd=fopen("crit_degree_knn.txt","w"))==NULL) printf("can't open the file fpdd!\n");
	int i=0,j=0;
	int n=G.amount_vex;
	int total_d=0;
	for(i=0;i<=MAX_LEN;i++)
		visited[i]=0;
	count=1;
	visited[1]=1;		//以第一个顶点为根,建立生成树
	struct edge *ed;
	ed=G.vp[1].next;
	ed=ed->next;		//图G为连通图所以顶点一定有邻接点
	int v;
	v=ed->seq;
	dfs_articul(G,v);		//dfs算法求关节点
	if(count<n)			//生成树的根有两棵以上的子树
	{
		//printf("\n\t the 1st node is a critical node !"); //1为关结点
		crit[k++]=1;
		while(ed->next!=NULL)
		{
			ed=ed->next;
			v=ed->seq;
			if(visited[v]==0)
				dfs_articul(G,v);
		}//end while
	}//end if
	int cd[DEG];			//cd[i] 是度为i的结点数
	int de=0,cdw=0;
	for(de=0;de<DEG;de++)
		cd[de]=0;
	fprintf(fp,"\nthe total number of the critical nodes are:%d, Let's show:\n",k);
	for(j=0;j<k;j++)
	{
		cdw=G.vp[crit[j]].degree;
		fprintf(fp,"\t %d\t--->%d\n",crit[j],cdw);
		fprintf(fpdd,"%d\t%d\n",cdw,G.vp[crit[j]].knn);
		cd[cdw]++;
		total_d+=cdw;
	}
	i=1;
	do
	{
		fprintf(fpd,"%d\t%d\n",i,cd[i]);
		i++;
	}while(i!=DEG);    //max possible degree 
	fclose(fpd);
	fprintf(fp,"\n");
	double acd=(double)total_d/k;
	printf("\nthe critical degree average is %f\n",acd);
	fclose(fp);
	fclose(fpd);
	fclose(fpdd);
}//get_articul