苗火 Nicholas

[Data structures]Find artificulation

2019-7-24 萧 写技术

#include <stdio.h>
#include <stdlib.h>

#define MAX 20
#define INFINIT	65535

typedef struct _ArcCell{
	int adj; // Weight or flag about connection
	int *info; // Other information
}ArcCell;

typedef char VertexType;

typedef enum{
	DG,
	DN,
	UDG,
	UDN
}GraphKind;

typedef struct _MGraph{
	VertexType vexs[MAX];
	ArcCell arcs[MAX][MAX];
	int vexnum;
	int arcnum;
	GraphKind kind;
}MGraph;

int visited[MAX];
int low[MAX];
int count;

int LocateVex(MGraph *G, VertexType v)
{
	int i=0;
	while(i<G->vexnum && G->vexs[i] != v){
		i++;
	}
	if(i<G->vexnum){
		return i;
	}else{
		return -1;
	}
}

int CreateUDG(MGraph *G)
{
	int i,j,k;
	char v1,v2;

	scanf(" %d %d", &G->vexnum, &G->arcnum);	
	for(i=0; i<G->vexnum; i++){
		scanf(" %c", &G->vexs[i] );
	}
	for(i=0; i<G->vexnum; i++){
		for(j=0; j<G->vexnum; j++){
			G->arcs[i][j].adj = INFINIT;
		}
	}
	for(k=0; k<G->arcnum; k++){
		scanf(" %c %c", &v1, &v2);
		i=LocateVex(G, v1);
		j=LocateVex(G, v2);	
		G->arcs[i][j].adj = 1;
		G->arcs[j][i].adj = 1;	
	}
	return 1;
}

int FirstAdjvex(MGraph *G, int v)
{
	int i=0;
	while(i<G->vexnum && G->arcs[v][i].adj == INFINIT){
		i++;
	}	
	if(i<G->vexnum){
		return i;
	}else{
		return -1;
	}
}

int NextAdjvex(MGraph *G, int v, int w)
{
	int i=w+1;
	while(i<G->vexnum && G->arcs[v][i].adj == INFINIT){
		i++;
	}
	if(i<G->vexnum){
		return i;
	}else{
		return -1;
	}
}

void DFSArticul(MGraph *G, int v)
{
	int w;
	int min;
	visited[v] = min = ++count;

	for(w = FirstAdjvex(G, v); w>=0; w = NextAdjvex(G, v, w) ){
		if(visited[w] == 0){
			DFSArticul(G, w);
			if(low[w] < min){
				min = low[w];
			}
			if(low[w] >= visited[v]){
				printf(" Articulation: %c (%d)\n", G->vexs[v], v);
			}
		}else if(visited[w] < min){
			min = visited[w];	
		}
	}
	low[v] = min;
}	

void FindArticul(MGraph *G)
{
	int i;
	int v;
	int w;
	count = 1;
	visited[0] = 1;
	low[0] = INFINIT;
	for(i=1; i<G->vexnum; i++){
		visited[i] = 0;
		low[i] = INFINIT;
	}
	v = FirstAdjvex(G, 0);
	DFSArticul(G, v);

	if(count < G->vexnum){
		printf(" Articulation: %c (%d)\n", G->vexs[0], 0);	
		for(w = NextAdjvex(G, 0, v); w>=0; w= NextAdjvex(G, 0, w) ){
			if(visited[i] == 0){
				DFSArticul(G, w);
			}
		}
	}


	printf(" The value of visited and low\n");
	for(i=0; i<G->vexnum; i++){
		printf(" %5d", i);
	}
	printf("\n");
	for(i=0; i<G->vexnum; i++){
		printf("     %c", G->vexs[i]);
	}
	printf("\n");
	for(i=0; i<G->vexnum; i++){
		printf(" %5d", visited[i]);
	}
	printf("\n");
	for(i=0; i<G->vexnum; i++){
		printf(" %5d", low[i]);
	}
	printf("\n");
}

void main()
{
	MGraph G;	

	printf("log.anycle.com\n\n");
	printf("Create graph:\n");
	CreateUDG(&G);
	printf("\n");

	printf("Find articulation:\n");
	FindArticul(&G);
	printf("\n");


}

标签: Data Structures data_structures