e1关节点.c

1、 图的存储结构的定义和图的创建 图的种类有：有向图、无向图、有向网、无向网。 图的存储结构可采用：邻接矩阵、邻接表。 要求：分别给出邻接矩阵和邻接表在某一种图上的创建算法 2、 图的遍历：

#include"guanjiedian.c"

void DFS(ALGraph G,int v);

/*void CreatGraph(ALGraph *G)
{//1表示无向图，2表示有向图，3表示无向网，4表示有向网//
	int i;
	printf("1表示无向图，2表示有向图，3表示无向网，4表示有向网\n");
	printf("please choose\n");
	scanf("%d",&(*G).kind);
	switch((*G).kind){
	case DG: CreateDG(G);
	case DN: CreateDN(G);
	case UDG:CreateUDG(G);
	case UDN:CreateUDN(G);
	default:return;
	}
}//CreatGraph*/

int Locate(ALGraph G,char v)
{
	int i;
	for(i=0;i<G.vexnum&&G.vertices[i].data!=v;i++);
	return i;
}

void CreateUDN(ALGraph *G)
{
	int i=0,j,k;
	char v1,v2;
	ArcNode *p1,*p2,*q;
	printf("please input vexnum and arcnum\n");
	scanf("%d%d",&(*G).vexnum,&(*G).arcnum);
	getchar();
	printf("%d\n",(*G).vexnum);
	for(i=0;i<(*G).vexnum;++i)
	{
		printf("please input data\n");
		scanf("%c",&(*G).vertices[i].data);
		getchar();
		(*G).vertices[i].firstarc=NULL;
	}
	for(i=0;i<(*G).vexnum;++i)
	{
		printf("%c %d",(*G).vertices[i].data,i);
	}
	for(i=0;i<(*G).arcnum;++i)
	{
		printf("please input edge\n");
		//scanf("%c%c ",&v1,&v2);
		v1=getchar();
		v2=getchar();
		getchar();
		printf("%c%c\n",v1,v2);
		j=Locate(*G,v1);
		k=Locate(*G,v2);
		printf("%d %d\n",j,k,i);
		p1=(ArcNode*)malloc(sizeof(ArcNode));
		//*p1={k,NULL};
		p1->adjvex=k;
		p1->nextarc=NULL;
		q=(*G).vertices[j].firstarc;
		(*G).vertices[j].firstarc=p1;
		p1->nextarc=q;
		p2=(ArcNode*)malloc(sizeof(ArcNode));
		//*p2={j,NULL};
		p2->adjvex=j;
		p2->nextarc=NULL;
		q=(*G).vertices[k].firstarc;
		(*G).vertices[k].firstarc=p2;
		p2->nextarc=q;
	}
}//CreatDG

print(ALGraph G)
{
	int i;
	ArcNode *p;
	for(i=0;i<G.vexnum;i++)
	{
		for(p=G.vertices[i].firstarc;p;p=p->nextarc)
			printf("%c",G.vertices[p->adjvex].data);
		printf("\n");
	}
}

void DFSTraverse(ALGraph G)
{
	int v;
	for(v=0;v<G.vexnum;v++)
		visited[v]=0;
	for(v=0;v<G.vexnum;v++)
		if(!visited[v])
			DFS(G,v);
}
void DFS(ALGraph G,int v)
{
	int k;
	ArcNode *p;
	visited[v]=1;
	printf("%c",G.vertices[v].data);
	for(p=G.vertices[v].firstarc;p;p=p->nextarc)
	{
		k=p->adjvex;
		if(!visited[k])
			DFS(G,k);
	}
}

main(){
	ALGraph G;
	CreateUDN(&G);
	printf("调用dfs后输出结果\n");
	DFSTraverse(G);
	printf("\n");
    printf("输出每个节点的相邻节点\n");
	print(G);
	printf("\n");
    printf("输出所有的关节点\n");
	FindArticul(G);
}