杰人编程网

graph.h

#ifndef __GRAPH_H__
#define __GRAPH_H__

typedef char Vertex[20]; /* 顶点的数据类型，字符串 */

typedef struct AdjLinkedNode {
	int adjvex;
	struct AdjLinkedNode *next;
}AdjLinkedNode;

typedef struct Graph {
	Vertex *vertex;
	int c;	/* capacity */
	int n_v; /* number of vertex */
	AdjLinkedNode *adjHeaders;
}Graph;

/* 创建最多n个顶点的图 */
int createGraph(Graph *g, int n);

/* 图g插入顶点v */
int insertVertex(Graph *g, Vertex v);

/* 图g插入边(u,v) */
int insertEdge(Graph *g, Vertex u, Vertex v);

/* 遍历图g */
void traverseGraph(Graph *g, int (*func)(Vertex v));

#endif

graph.c

#include  /* strcpy(), strcmp() */
#include 
#include  /* malloc() */
#include "graph.h"


/* 创建最多n个顶点的图 */
int createGraph(Graph *g, int n)
{
	int i;
	g->vertex = (Vertex *)malloc(sizeof(Vertex) * n);
	g->c = n;
	g->n_v = 0;
	g->adjHeaders = (AdjLinkedNode *)malloc(sizeof(AdjLinkedNode) * n);
	for(i=0; iadjHeaders[i].next = NULL;
	}

	return 0;
}


/* 图g插入顶点v */
int insertVertex(Graph *g, Vertex v)
{
	/* g->vertex[g->n_v] = v */
	strcpy(g->vertex[g->n_v], v);

	g->n_v ++;

	return g->n_v;
}

/* 获取顶点v的索引(下标) */
int locateVertex(Graph *g, Vertex v)
{
	int i;
	for(i=0; in_v; i++) {
		if (strcmp(g->vertex[i], v) == 0) {
			return i;
		}
	}
	return -1;
}

void insertAdjLinked(Graph *g, int iu, int iv)
{
	AdjLinkedNode *p;
	p = (AdjLinkedNode *)malloc(sizeof(AdjLinkedNode));
	p->adjvex = iv;
	p->next = g->adjHeaders[iu].next;
	g->adjHeaders[iu].next = p;
}

/* 图g插入边(u,v) */
int insertEdge(Graph *g, Vertex u, Vertex v)
{
	int iu, iv;

	iu = locateVertex(g, u);
	iv = locateVertex(g, v);

	insertAdjLinked(g, iu, iv);
	insertAdjLinked(g, iv, iu);

	return 0;
}

/* 遍历图的内部函数 */
void traverseGraphInner(Graph *g, int u, int flags[], int (*func)(Vertex v))
{
	AdjLinkedNode *p;

	if (flags[u] == 1) {
		return;
	}

	/* visit u */
	flags[u] = 1;
/*	printf("%d: %s\n", u, g->vertex[u]); */
	func(g->vertex[u]);

	for(p=g->adjHeaders[u].next; p!=NULL; p=p->next) {
		traverseGraphInner(g, p->adjvex, flags, func);
	}

}


/* 遍历图g */
void traverseGraph(Graph *g, int (*func)(Vertex v))
{
	int i, *flags; /* 到此一游数组 */

	flags = (int *)malloc(sizeof(int) * g->n_v);
	for(i=0; in_v; i++) {
		flags[i] = 0;
	}

	/* 解决非连通图问题 */
	for(i=0; in_v; i++) {
		traverseGraphInner(g, i, flags, func);
	}
	
}

main.c

#include 
#include "graph.h"


int visitVertex(Vertex v)
{
	printf("%s\n", v);
	return 0;
}


int visitVertex2(Vertex v)
{
	printf("\t%s\n", v);
	return 0;
}


int main()
{
	Graph map;

	createGraph(&map, 100);

	insertVertex(&map, "SanJiao");
	insertVertex(&map, "SiJiao");
	insertVertex(&map, "ShiTang");

	insertEdge(&map, "SanJiao", "SiJiao");
	insertEdge(&map, "ShiTang", "SiJiao");

	traverseGraph(&map, visitVertex);
	traverseGraph(&map, visitVertex2);

	return 0;
}