图的具体实现
- 构造图
- 邻接矩阵
- *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 < 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_vertex; j++)
G->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 < G->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 <= 4 )
// G->kind 只能是 1、2、3、4，不然重新输入
);
T v1, v2;
int w; // 权
switch (G->kind)
{
case DG:
for (int i = 0; i < G->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 vertex\n");
return;
}
G->matrix[n][m] = 1;
}
break;
case DN:
for (int i = 0; i < G->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 vertex\n");
return;
}
G->matrix[n][m] = 1;
G->matrix[m][n] = 1; // 无向图的二阶矩阵沿主对角线对称
}
break;
case UDG:
for (int i = 0; i < G->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 vertex\n");
return;
}
G->matrix[n][m] = w;
}
break;
case UDN:
for (int i = 0; i < G->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 vertex\n");
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<stdio.h>
#include<stdlib.h>
#include<assert.h>
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 < G->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 < 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_vertex; j++)
G->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 < G->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 <= 4)
// n 个逗号表达式的值是最后一个，刚好可以结合循环做结束条件，如果输入值不是 1、2、3、4，就一直输入
);
T v1, v2;
int w;
switch (G->kind)
{
case DG:
for (int i = 0; i < G->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 < G->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 < G->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 < G->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 < 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);
}
/* 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 < G->n; i++)
for (int j = 0; j < G->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 < G->n; i++)
for (int j = 0; j < G->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 < G->n; i++)
for (int j = 0; j < G->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 < G->n; i++)
for (int j = 0; j < G->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 < 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->n; 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 写出来，只是暗示，我们会创建不同类型的图，其实并不需要这个参数，具体请看代码。
/* 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 < G->n; i++)
for (int j = 0; j < G->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 < G->n; i++)
for (int j = 0; j < G->n; j++)
if ( G->matrix[i][j] && i < j )
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]){
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] && i < j){
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;
}
}比如，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 < 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)
int vertices_pos(adjMatrix * G, T 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)