图的具体实现

• 构造图
• 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)

 

构造图

如果要我实现一份图论的代码，在 可读性、支持范式（泛型、对象）、简洁、安全、性能 里面选，我优先考虑安全。

所以，实现图论代码之前，给出一份我用的出错处理模块。

错误处理模块：自动化错误处理、实现异常机制

#include<stdio.h>
#include<errno.h> 
#include<string.h> 
#define clean_errno() (errno == 0 ? "None" : strerror(errno))
// 看懂这句代码，需要了解 errno、strerror() 
// errno 是一个数字，errno = 1 是操作不允许，errno = 2 是没有这样的文件或目录，在 errno.h 文件里一共定义了 124 个常见错误 [1, 124]
// errno 本身只是一个数字，如果想知道这串数字的含义是什么，可以通过 strerror() 函数，比如 errno = 2，strerror(errno) 会返回 【Error: No such file or directory】

#define log_err(M, ...) fprintf(stderr,\ "[ERROR] (%s:%d: errno: %s) " M "\n", __FILE__, __LINE__,\ clean_errno(), ##__VA_ARGS__)
// log_err相当于一个调试器，当程序出现错误时，输出 那个文件名(__FILE__)、错误的行数(__LINE__)、错误的原因(strerror(errno))，以及提示信息(这个是我们调用的时候写的)
        
#define check(A, M, ...) if(!(A)) {\ log_err(M, ##__VA_ARGS__); errno=0; goto error; }
// check(同assert)，断言check括号里的内容为真，否则打印错误信息并跳转到 error 处清理
   
#define check_mem(A) check((A), "内存不足。")
// check_mem() 可以用于检测内存，如果 A == false，就输出【内存不足】，并进行一次跳转

int main( )
{
   FILE *fp = fopen("file.abc","r");		// 打开一个压根不存在的文件
   if( fp == NULL ) 						// 因为文件不存在，所以打不开，指针为空
     check(fp, "fp == NULL呀～（提示信息：这里给一串相关的提示信息）" );
     // 使用我们的错误处理宏 check(), 
     
   int *a = (int *)malloc(19979797797984);	// 申请一个编译器给不了的空间
   if( a == NULL ) 							// 因为内存不够，所以没申请到，指针为空
     check_mem(a);							// 和 check() 一样，只不过不需要给提示信息了
     
   error:									// 错误处理标签, do something，如
   	if( fp == NULL )
   		printf("fail to open %s\n","file.abc");
   		
   	if( a == NULL )
   		printf("out of memory %d\n",19979797797984);

	puts("")    // 如果不用特别做什么，可以写 puts("") 占个位
 
    return -1;  // 如果写 return 占位，那函数就结束了
    
    // 这种统一错误标签（只有一个error标签）其实不灵活。
    // 因为错误处理也可以检测异常，如果某个地方有问题，那程序跳过这个地方即可，接着运行下面的代码，比如上面的代码，就因为打不开文件，所以程序越过申请空间这步，直接返回了。
    // 使用多个错误处理标签就可以实现异常
    
    
     
	fclose(fp);    fp = NULL;
	free(a);       a = NULL;
	return 0;
}

创建图：[邻接矩阵]

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);
	check_mem(G->list != NULL);	                         

	
	G->matrix = (int**)malloc(sizeof(int) * MAX_vertex);    // 先开辟行
	
	for(int i=0; i<MAX_vertex; i++)                         // 再开辟列
		G->matrix[i] = (int*)malloc(sizeof(int) * MAX_edge);  
	
	
	for(int i=0; i<MAX_vertex; i++)
		for(int j=0; j<MAX_edge; j++)
			G->matrix[i][j] = 0;

	
	FILE *fp=fopen( "input_data.txt","r" ); 
	check( fp, "提示信息：文件打不开，可能是文件名错了");

	
	 
	fscanf(fp, "%d%*c%d", &(G->n), &(G->m));    // 第一行是 顶点数、弧数
	scanf("%*[^\n]"), scanf("%*c");             // 清空缓冲区
	
	puts("依次输入顶点本身的数据:> ");              // 如第 1 个顶点，可能是个城市名
	for(int i=0; i<G->n; i++)
		scanf("%c", &(G->list[i]));
	
	T v1, v2;
	int v, u, w;
	int i, j;
	scanf("%d", &G->kind);
	switch(G->kind){
		case DG:	// 有向无权图
			for(i=G->n-1; i>0; i--){		            
		    	fscanf(fp, "%c %c", &v1, &v2);
		    	scanf("%*[^\n]"), scanf("%*c");             // 清空缓冲区
		    	
		    	v = vertices_pos(G, v1);
		    	u = vertices_pos(G, v2);
		    	if (v==-1 || u==-1) {    // 顶点不存在
            		printf("no this vertex\n");
            		return;
        		}
		    	G->matrix[v][u] == 1;
	    	}
	    	break;
	    	
	    case DN:	// 无向无权图
	    	for(i=G->n-1; i>0; i--){		            
		    	fscanf(fp, "%c %c", &v1, &v2);
		    	v = vertices_pos(G, v1);
		    	u = vertices_pos(G, v2);
		    	if (v==-1 || u==-1) {    // 顶点不存在
            		printf("no this vertex\n");
            		return;
        		}
		    	G->matrix[v][u] == 1;
		    	G->matrix[u][v] == 1;
	    	}
	    	break;
	    	
	    case UDG:	// 有向带权图（有向网）
	    	for(i=G->n-1; i>0; i--){		            
		    	fscanf(fp, "%c %c %d", &v1, &v2, &w);
		    	v = vertices_pos(G, v1);
		    	u = vertices_pos(G, v2);
		    	if (v==-1 || u==-1) {    // 顶点不存在
            		printf("no this vertex\n");
            		return;
        		}
		    	G->matrix[v][u] == w;
	    	}
	    	break;
	    	
	    case UDN:	// 无向带权图（无向网）
	    	for(i=G->n-1; i>0; i--){		            
		    	fscanf(fp, "%c %c %d", &v1, &v2, &w);
		    	v = vertices_pos(G, v1);
		    	u = vertices_pos(G, v2);
		    	if (v==-1 || u==-1) {    // 顶点不存在
            		printf("no this vertex\n");
            		return;
        		}
		    	G->matrix[v][u] == w;
		    	G->matrix[u][v] == w;
	    	}
	    	break;
	    	
	    default:
	    	puts("graph_kind 无效！");
            break;
	}
	
error:
	puts("");	// 只是占个位，不用特别做什么

	fclose(fp); fp = NULL;
}

 

destroy_graph( *G )

void destroy(adjMatrix * G)
{
 	// 顶点表释放
 	free( G->list );
 	G->list = NULL;
 	
 	// 先释放列
 	for( int i = 0; i < G->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 < G->n; i++, putchar(10) )  
    // putchar(10)是换行，每行换一次行
        for (int j = 0; j < G->m; j++)
            printf("%d ",G->matrix[i][j]);
    putchar(10);
}

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

结合顶点表输出信息：

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

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

 

visual_graph(*G, graph_kind)

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

 
 void graph_dot( adjMatrix * G, char* filename )
 {
 	FILE *file = fopen(filename, "w+");
	switch(G->kind){
		case DG:	// 有向无权图
			fprintf(file, "digraph{\n");
 	
	 		for( int i=0; i<G->n; i++ )
	 	       for( int j=0; j<G->n; j++ )
	 	             if( G->matrix[i][j] == 1 )
	 	                 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<G->n; i++ )
	 	       for( int j=0; j<G->n; j++ )
	 	             if( G->matrix[i][j] == 1 )
	 	                 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<G->n; i++ )
	 	       for( int j=0; j<G->n; j++ )
	 	             if( G->matrix[i][j] == 1 )
	 	                 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<G->n; i++ )
	 	       for( int j=0; j<G->n; j++ )
	 	             if( G->matrix[i][j] == 1 )
	 	                 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;
	}

 	fclose(file);    file = NULL;
 	return;
 }

编译: gcc -o 所有源文件.c

产生dot文件：./可执行文件名 > dot_filename.dot

(前提：有 dot 文件)保存为png：dot filename.dot -T -o png_filename.png

效果图：

复杂度是 Θ ( n 2 ) \Theta(n^{2}) Θ(n2)，还有一种 Θ ( n ) \Theta(n) Θ(n) 的画法。

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 < G->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)

vertices_pos(adjMatrix *G, v){
	for(int i=0; i<G->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)