2. 图的具体实现

Posted on by hackdl

图的具体实现

  • 构造图
  • 邻接矩阵
  • *create_graph( *G, graph_kind )
  • destroy_graph( *G )
  • print_graph(*G)
  • visual_graph(*G, graph_kind)
  • 点接口
  • total_vertices(*G)
  • insert_vertices(*G, v)
  • remove(*G, v)
  • dregree_in(*G, v)
  • dregree_out(*G, v)
  • first_neighbor(*G, v)
  • next_neighbor(*G, v, u)
  • judge_adjacent(*G, v, u)
  • status(*G, v)：UNDISCOVERED、DISCOVERED
  • vertices_val(*G, pos)
  • vertices_pos(*G, v)
  • 弧接口
  • total_edge(*G)
  • exist(*G, v, u)
  • insert_edge(*G, v, u)
  • remove_edge(*G, v, u)
  • weight(*G, v, u)

 

构造图

 

邻接矩阵

创建图：[邻接矩阵]

typedef enum{                  // 枚举图类型
    DG = 1,                    // 有向无权图
    DN = 2,                    // 无向无权图
    UDG = 3,                   // 有向有权图
    UDN = 4                    // 无向有权图
}graph_kind;

/* 邻接矩阵 */
typedef char T             
typedef struct graph_adj_matrix{
    T* list;        	   // 顶点表，存储顶点本身的数据，如顶点1的信息是[北京]
    int** matrix;          // 二维数组
    int n;            	   // 顶点数
    int m;                 // 弧数
    graph_kind kind;       // 图的类型
}adjMatrix;

#define MAX_vertex 256     				    // 最大顶点数
#define MAX_edge  MAX_vertex * MAX_vertex   // 最大弧数，邻接矩阵的空间是 n*n

 

*create_graph( *G, graph_kind )

graph_kind 是图的类型，函数原型把 graph_kind 写出来，只是暗示，我们会创建不同类型的图，其实并不需要这个参数，具体请看代码。

void create_graph(adjMatrix * G)
{
	 G->list = (T *) malloc(sizeof(T) * MAX_vertex);
	 assert(G->list != NULL);

	/* 使用二级指针开辟二维数组，也可以数组指针开辟；或者直接开辟一维数组，再把一维索引转为二维即可 
	 */
	G->matrix = (int **)malloc(sizeof(int) * MAX_vertex);	// 先开辟行

	for (int i = 0; i matrix[i] = (int *)malloc(sizeof(int) * MAX_edge);

	/* 初始化矩阵 */
	for (int i = 0; i matrix[i][j] = 0;

	/* 顶点、弧的数据，从文件里读出来 */
	char file_name[128] = "";
	puts("请输入测试文件:> ");
	scanf("%127[^n]", file_name);
	FILE *fp = fopen(file_name, "r");
	assert( fp );


	fscanf(fp, "%d%*c%d", &(G->n), &(G->m));	// 第一行是 顶点数、弧数
	scanf("%*[^n]"), scanf("%*c");	            // 清空缓冲区

	puts("请输入顶点信息:)");
	for (int i = 0; i n; i++)
	{
		scanf("%[a-z-A-Z0-9]%*c", &G->list[i]);	
		// 读取数据(只能是字母和数字)，并消除数据之外的字符
	}

while( 
	puts("请选择图（1有向图, 2无向图, 3有向网, 4无向网:)"),
	scanf("%d", &G->kind), 
	! ( G->kind >= 1 && G->kind kind 只能是 1、2、3、4，不然重新输入
);

	T v1, v2;
	int w;		// 权
	switch (G->kind)
	{
	case DG:
	   for (int i = 0; i m; i++ )
		{
			while (fgetc(fp) != 'n');	// 文件指针移动到下一行
			fscanf(fp, "%c%*c%c", &v1, &v2);
			int n = vertices_pos(G, v1);
			int m = vertices_pos(G, v2);
			if (m == -1 || n == -1)
			{
				printf("no this vertexn");
				return;
			}
			G->matrix[n][m] = 1;
		}
		break;
	
	case DN:
		for (int i = 0; i m;  i++)
		{
			while (fgetc(fp) != 'n');	// 文件指针移动到下一行
			fscanf(fp, "%c%*c%c", &v1, &v2);
			int n = vertices_pos(G, v1);
			int m = vertices_pos(G, v2);
			if (m == -1 || n == -1)
			{
				printf("no this vertexn");
				return;
			}
			G->matrix[n][m] = 1;
			G->matrix[m][n] = 1;	// 无向图的二阶矩阵沿主对角线对称
		}
		break;
		
      case UDG:
      for (int i = 0; i m; i++)
		{
			while (fgetc(fp) != 'n');	// 文件指针移动到下一行
			fscanf(fp, "%c%*c%c%*c%d", &v1, &v2, &w);
			int n = vertices_pos(G, v1);
			int m = vertices_pos(G, v2);
			if (m == -1 || n == -1)
			{
				printf("no this vertexn");
				return;
			}
			G->matrix[n][m] = w;
		}
		break;
      
      case UDN:
      for (int i = 0; i m; i++)
		{
			while (fgetc(fp) != 'n');	// 文件指针移动到下一行
			fscanf(fp, "%c%*c%c%*c%d", &v1, &v2, &w);
			int n = vertices_pos(G, v1);
			int m = vertices_pos(G, v2);
			if (m == -1 || n == -1)
			{
				printf("no this vertexn");
				return;
			}
			G->matrix[n][m] = w;
			G->matrix[m][n] = w;
		}
		break;
		
	 default:
		break;
	}
}

比如，无权图测试文件叫 input.txt，里面是这样的：

3 3		
A B
B C
A C
  • 输入：input.txt 即可。

接着是，输入顶点信息。比如input.txt文件的顶点有 3 个，分别是 A、B、C。

  • 输入：A B C 即可

而后是，选择图的类型。上面有提示，如 1 是有向图。

  • 输入：1 即可。

而后，我们调用输出函数，就可以打印这个图啦。

大概就是这个流程，需要调用 3 个函数：

  • 创建图：create_graph( *G, graph_kind );
  • 打印图：print_graph(*G);
  • 获取顶点位置：vertices_pos(*G, v)

这 3 个函数都在本文里，可以按 command/win + F 搜索。

这是在手机上测试的，AC。而后，再调用 visual_graph(*G, graph_kind) 可视化即可。

完整代码：

#include
#include
#include

typedef enum{						// 枚举图类型
	DG = 1,							// 有向无权图
	DN = 2,							// 无向无权图
	UDG = 3,						// 有向有权图
	UDN = 4							// 无向无权图
} graph_kind;

/* 邻接矩阵 */
typedef int T;
typedef struct graph_adj_matrix
{
	T *list;					// 顶点表，存储顶点本身的数据，如顶点1的信息是[北京]
	int **matrix;				// 二维数组
	int n;						// 顶点数
	int m;						// 弧数
	graph_kind kind;			// 图的类型
} adjMatrix;

#define MAX_vertex 256			// 最大顶点数
#define MAX_edge  MAX_vertex * MAX_vertex	// 最大弧数，邻接矩阵的空间是 n*n

/* 获取顶点的位置 */
int vertices_pos(adjMatrix * G, T v)
{
	for (int i = 0; i n; i++)
		if (G->list[i] == v)
			return i;

	return -1;					// 找不到，v不存在
}

void create_graph(adjMatrix * G)
{
	/* 存储顶点信息 */
	G->list = (T *) malloc(sizeof(T) * MAX_vertex);
	assert(G->list != NULL);

	G->matrix = (int **)malloc(sizeof(int) * MAX_vertex);	
	// 先开辟行

	for (int i = 0; i matrix[i] = (int *)malloc(sizeof(int) * MAX_edge);

	/* 初始化矩阵 */
	for (int i = 0; i matrix[i][j] = 0;

	/* 顶点、弧的数据，从文件里读出来 */
	puts("请输入测试文件:> ");
	char file_name[128] = "";
	scanf("%127[^n]", file_name);
	FILE *fp = fopen(file_name, "r");
	assert(fp);

	fscanf(fp, "%d%*c%d", &(G->n), &(G->m));
	scanf("%*[^n]"), scanf("%*c");	// 清空缓冲区

	puts("n请输入顶点信息:)");
	for (int i = 0; i n; i++)
	{
		scanf("%[a-z-A-Z0-9]%*c", &G->list[i]);	// 读取数据(只能是字母和数字)，并消除数据之外的字符
	}

	while (
			puts("n请选择图（1有向图, 2无向图, 3有向网, 4无向网:)"), 
			scanf("%d", &G->kind), 
			!(G->kind >= 1 && G->kind kind)
	{
	case DG:
		for (int i = 0; i m; i++)
		{
			while (fgetc(fp) != 'n');	// 文件指针移动到下一行
			fscanf(fp, "%c %c", &v1, &v2);
			int n = vertices_pos(G, v1);
			int m = vertices_pos(G, v2);
			assert(m != -1);  // 顶点 v1 不存在
			assert(n != -1 );

			G->matrix[n][m] = 1;
		}
		break;

	case DN:
		for (int i = 0; i m; i++)
		{
			while (fgetc(fp) != 'n');	// 文件指针移动到下一行
			fscanf(fp, "%c %c", &v1, &v2);
			int n = vertices_pos(G, v1);
			int m = vertices_pos(G, v2);
			assert(m != -1);
			assert(n != -1);

			G->matrix[n][m] = 1;
			G->matrix[m][n] = 1;	// 无向图的二阶矩阵沿主对角线对称
		}
		break;

	case UDG:
		for (int i = 0; i m; i++)
		{
			while (fgetc(fp) != 'n');	// 文件指针移动到下一行
			fscanf(fp, "%c %c %d", &v1, &v2, &w);
			int n = vertices_pos(G, v1);
			int m = vertices_pos(G, v2);
			assert(m != -1);
			assert(n != -1);

			G->matrix[n][m] = w;
		}
		break;

	case UDN:
		for (int i = 0; i m; i++)
		{
			while (fgetc(fp) != 'n');	// 文件指针移动到下一行
			fscanf(fp, "%c %c %d", &v1, &v2, &w);
			int n = vertices_pos(G, v1);
			int m = vertices_pos(G, v2);
			assert(m != -1);
			assert(n != -1);

			G->matrix[n][m] = w;
			G->matrix[m][n] = w;
		}
		break;

	default:
		break;
	}
}

void print_graph(adjMatrix * G)
{
	puts(" ");
	int i, j;
	printf("   ");
	for (i = 0; i n; i++)
		printf("%c  ", G->list[i]);

	putchar(10);

	for (i = 0; i n; i++, putchar(10))
	{
		printf("%c  ", G->list[i]);
		for (j = 0; j n; j++)
			printf("%d  ", G->matrix[i][j]);
	}
	putchar(10);
}

  /* dot 画图 */
void visual_graph(adjMatrix * G, char *filename)
{
	FILE *file = fopen(filename, "w+");
	assert(file);
	switch (G->kind)
	{
	case DG:					// 有向无权图
		fprintf(file, "digraph{n");

		for (int i = 0; i n; i++)
			for (int j = 0; j n; j++)
				if (G->matrix[i][j] != 0)
					fprintf(file, "t%c->%c;n", G->list[i], G->list[j]);

		fprintf(file, "}n");

		break;

	case DN:					// 无向无权图
		fprintf(file, "graph{n");

		for (int i = 0; i n; i++)
			for (int j = 0; j n; j++)
				if (G->matrix[i][j] != 0)
					fprintf(file, "t%c--%c;n", G->list[i], G->list[j]);

		fprintf(file, "}n");
		break;

	case UDG:					// 有向带权图（有向网）
		fprintf(file, "digraph{n");

		for (int i = 0; i n; i++)
			for (int j = 0; j n; j++)
				if (G->matrix[i][j] != 0)
					fprintf(file, "t%c->%c[label=%d];n", G->list[i], G->list[j],
							G->matrix[i][j]);

		fprintf(file, "}n");
		break;

	case UDN:					// 无向带权图（无向网）
		fprintf(file, "graph{n");

		for (int i = 0; i n; i++)
			for (int j = 0; j n; j++)
				if (G->matrix[i][j] != 0)
					fprintf(file, "t%c--%c[label=%d];n", G->list[i], G->list[j],
							G->matrix[i][j]);

		fprintf(file, "}n");
		break;

	default:
		puts("graph_kind 无效！");
		break;
	}
}

int main()
{
	adjMatrix G;	
	// 建模图：邻接矩阵
	
	create_graph(&G);	
	// 构造图：图建模[邻接矩阵]、初始化矩阵、构造某种类型图、读入测试数据
	
	print_graph(&G);	
	// 输出图：打印完整的图形
	
	visual_graph(&G, "adjMatrix.dot");	
	// 可视化图：需要学一下 dot 语言，终端运行或下载一个软件
}

 

destroy_graph( *G )

void destroy(adjMatrix * G)
{
 	// 顶点表释放
 	free( G->list );
 	G->list = NULL;
 	
 	// 先释放列
 	for( int i = 0; i n; i ++ )
 	    free( G->matrix[i] );
 	// 再释放行
 	free( G->matrix );
 	G->matrix = NULL;
 	G->n = G->m = 0;
 }

 

print_graph(*G)

void print_graph(adjMatrix * G){
    for (int i = 0; i n; i++, putchar(10) )  
    // putchar(10)是换行，每行换一次行
        for (int j = 0; j n; j++)
            printf("%d ",G->matrix[i][j]);
    putchar(10);
}

运行后的大概模样，仅供参考

结合顶点表输出信息：

void print_graph(adjMatrix * G)
 {
 	int i, j;
 	printf("   ");
 	for( i = 0; i n; i++ )
 	    printf("%c  ", G->list[i]);
 	    
 	putchar(10);
 	
     for( i=0; in; i++, putchar(10)){
     	printf("%c  ", G->list[i]);
         for(j=0; jn; j++)
             printf("%d  ", G->matrix[i][j]);
     }
     putchar(10);
 }

运行后的大概模样，仅供参考：

 

visual_graph(*G, graph_kind)

graph_kind 是图的类型，函数原型把 graph_kind 写出来，只是暗示，我们会创建不同类型的图，其实并不需要这个参数，具体请看代码。

/*  dot 画图  */
 void visual_graph(adjMatrix * G, char *filename)
{
	FILE *file = fopen(filename, "w+");
	assert(file);
	switch (G->kind)
	{
	case DG:					// 有向无权图
		fprintf(file, "digraph{n");

		for (int i = 0; i n; i++)
			for (int j = 0; j n; j++)
				if (G->matrix[i][j] != 0)
					fprintf(file, "t%c->%c;n", G->list[i], G->list[j]);

		fprintf(file, "}n");

		break;

	case DN:					// 无向无权图
		fprintf(file, "graph{n");

		for (int i = 0; i n; i++)
			for (int j = 0; j n; j++)
				if ( G->matrix[i][j] && i list[i], G->list[j]);

		fprintf(file, "}n");
		break;

	case UDG:					// 有向带权图（有向网）
		fprintf(file, "digraph{n");

		for (int i = 0; i n; i++)
			for (int j = 0; j n; j++)
				if (G->matrix[i][j]){
					fprintf(file, "t%c->%c[label=%d];n", G->list[i], G->list[j],
							G->matrix[i][j]);
				}
		fprintf(file, "}n");
		break;

	case UDN:					// 无向带权图（无向网）
		fprintf(file, "graph{n");

		for (int i = 0; i n; i++)
			for (int j = 0; j n; j++)
				if (G->matrix[i][j] && i list[i], G->list[j],
							G->matrix[i][j]);
				}
		fprintf(file, "}n");
		break;

	default:
		puts("graph_kind 无效！");
		break;
	}
}

比如，filename 输入测试是 demo.dot

如果按 1 （有向图）， demo.dot 就是这样子：

digraph{
	A->B;
	A->C;
	B->C;
}

而后，在终端运行 dot 文件或者下载一个 Graphviz 软件，就会产生一个效果图：

visual_graph(*G, graph_kind)复杂度分析：

  • 时间复杂度是

其实也有一种 

void graph_foreach(Graph g, int source,
        void (*f)(Graph g, int source, int sink, void *data),
        void *data);
        
static void print_edge2dot(Graph g,int source, int sink, void *data){
    fprintf(stdout,"%d->%d;n",source,sink);		// 有向图画法
}

for( int i = 0;i n; i++ ){
	graph_foreach(g,idx,print_edge2dot,NULL);
	// graph_foreach 传递 print_edge2dot() 函数作用到每一个元素上的方法，同 Lisp 的 mapcar。
}

具体的介绍，请猛击 ：http://blog.chinaunix.net/uid-24774106-id-3505579.html

其它画图工具，如：

  • Java 的 Swing框架；
  • html 的 Canvas。
     

点接口

 

total_vertices(*G)

 

insert_vertices(*G, v)

 

remove(*G, v)

 

dregree_in(*G, v)

 

dregree_out(*G, v)

 

first_neighbor(*G, v)

 

next_neighbor(*G, v, u)

 

judge_adjacent(*G, v, u)

 

status(*G, v)：UNDISCOVERED、DISCOVERED

 

vertices_val(*G, pos)

 

vertices_pos(*G, v)

int vertices_pos(adjMatrix * G, T v)
{
	for (int i = 0; i n; i++)
		if (G->list[i] == v)
			return i;

	return -1;					// 找不到，v不存在
}

 

弧接口

 

total_edge(*G)

 

exist(*G, v, u)

 

insert_edge(*G, v, u)

 

remove_edge(*G, v, u)

 

weight(*G, v, u)

 

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: