图的C语言实现

八月 28, 2021 6811

本文使用C语言完成图的创建（邻接矩阵和邻接表两种方法）与两种遍历方式（深度优先：DFS与广度优先：BFS）。

1.代码部分

1.1图的创建

（1）用邻接矩阵创建

结构体定义：

1
2
3
4
5
6
7
8
9
10
11
12
#define MVNum 20
#define MaxInt 32767
typedef char vertextype;
typedef int arctype;


typedef struct {  // Using matrics.
	vertextype vex[MVNum];
	arctype arc[MVNum][MVNum];
	int vexnum;
	int arcnum;
}AMGraph;

分别使用一维数组vex创建顶点集，二维数组arc创建边集（二维数组的x，y存放边的两个点，数值本身存放权值）

传入AMGraph指针开始创建。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void CreatUDN(AMGraph* g)  // Creat with matrics.
{
	int vnum = 0, anum = 0;
	char a, node1, node2;
	int i, j, k, weight, pos1, pos2;
	printf("Input vexnum: \n");
	scanf_s("%d", &vnum);
	a = getchar();
	printf("Input arcnum: \n");
	scanf_s("%d", &anum);
	a = getchar();
	g->vexnum = vnum;  // Assert value.
	g->arcnum = anum;
	for (i = 0; i < g->vexnum; ++i)
	{
		printf("Input node %d.\n", i + 1);
		scanf_s("%c", &(g->vex[i]), 1);
		a = getchar();
	}
	for (i = 0; i < g->vexnum; i++)
	{
		for (j = 0; j < g->vexnum; j++)
		{
			g->arc[i][j] = 0;  // Initialize.
		}
	}
	for (k = 0; k < g->arcnum; ++k)
	{
		printf("Input the two nodes and weight:\n");
		scanf_s("%c, %c, %d", &node1, 1, &node2, 1, &weight);
		a = getchar();
		pos1 = LocateVex(g, node1);
		pos2 = LocateVex(g, node2);
		g->arc[pos1][pos2] = weight;
		g->arc[pos2][pos1] = weight;
	}
}

其中的LocateVex函数定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int LocateVex(AMGraph* g, vertextype u)
{
	int i;
	for (i = 0; i < g->vexnum; ++i)
	{
		if (u == g->vex[i])
		{
			return i;
		}
		else
		{
			continue;
		}
	}
	return -1;
}

（2）用邻接表创建

结构体定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
typedef struct Arcnode {
	int adjvex;
	struct Arcnode* nextarc;
	int otherinfo;
}Arcnode;


typedef struct VNode{
	vertextype data;
	Arcnode* firstarc;
}VNode, AdjList[MVNum];


typedef struct {  // Using linked list.
	AdjList vertices;
	int vexnum;
	int arcnum;
}ALGraph;

VNode是每一个顶点对应的链表的头节点，Arcnode是其他节点。ALGraph是由头节点形成的线性表。

传入ALGraph指针开始创建：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void CreatUDN2(ALGraph* g)
{
	int vnum = 0, anum = 0;
	char a, node1, node2;
	int i, k, pos1, pos2;
	printf("Input vexnum: \n");
	scanf_s("%d", &vnum);
	a = getchar();
	printf("Input arcnum: \n");
	scanf_s("%d", &anum);
	a = getchar();
	g->vexnum = vnum;
	g->arcnum = anum;
	for (i = 0; i < g->vexnum; ++i)
	{
		printf("Input node %d.\n", i + 1);
		scanf_s("%c", &(g->vertices[i].data), 1);
		a = getchar();
		g->vertices[i].firstarc = NULL;
	}
	for (k = 0; k < g->arcnum; ++k)
	{
		printf("Input the two nodes:\n");
		scanf_s("%c, %c", &node1, 1, &node2, 1);
		a = getchar();
		pos1 = LocateVex2(g, node1);
		pos2 = LocateVex2(g, node2);
		Arcnode* p1 = (Arcnode*)malloc(sizeof(Arcnode));
		p1->adjvex = pos2;
		p1->nextarc = g->vertices[pos1].firstarc;
		g->vertices[pos1].firstarc = p1;
		// Use the following lines to creat none direction graph.
		Arcnode* p2 = (Arcnode*)malloc(sizeof(Arcnode));
		p2->adjvex = pos1;
		p2->nextarc = g->vertices[pos2].firstarc;
		g->vertices[pos2].firstarc = p2;
	}
}

其中LocateVex2函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int LocateVex2(ALGraph*g, vertextype u) 
{
	int i;
	for (i = 0; i < g->vexnum; i++)
	{
		if (u == g->vertices[i].data)
		{
			return i;
		}
		else 
			continue;
		}
		{
	}
	return -1;
}

1.2图的遍历

（1）深度优先算法（递归思想）
1
2
3
4
5
6
7
8
9
10
11
12
13
void DFS(AMGraph* g, int* visited, int v)  // Using matrics.
{
	int w;
	printf("%c ", g->vex[v]);
	visited[v] = 1;
	for (w = 0; w < g->vexnum; w++)
	{
		if ((g->arc[v][w] != 0) && (visited[w])!=1)
		{
			DFS(g, visited, w);
		}
	}
}

（2）广度优先算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void BFS(ALGraph* g, int* visited, int v)
{
	printf("%c ", g->vertices[v].data);
	visited[v] = 1;
	Queue* que = Initial();
	EnQueue(que, v);
	while (QueueEmpty(que) == 0)
	{
		int u = DeQueue(que);
		for (int w = FirstAdjVex(g, u); w >= 0; w = NextAdjVex(g, u, w))
		{
			if (visited[w] != 1)
			{
				printf("%c ", g->vertices[w].data);
				visited[w] = 1;
				EnQueue(que, w);
			}
			else
			{
				continue;
			}
		}
	}
}

其中用到的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
int FirstAdjVex(ALGraph* g, int u)
{
	int c = g->vertices[u].firstarc->adjvex;
	return c;
}


int NextAdjVex(ALGraph* g, int u, int w)
{
	Arcnode *p = g->vertices[u].firstarc;
	if (p)
	{
		while (p)
		{
			if (p->adjvex == w)
			{
				if (p->nextarc)
				{
					return p->nextarc->adjvex;
				}
				else 
				{
					break;
				}
			}
			else
			{
				p = p->nextarc;
				continue;
			}
		}
		return -1;
	}
	else
	{
		return -1;
	}
}


Queue* Initial()
{
	Queue* que = (Queue*)malloc(sizeof(Queue));
	if (que)
	{
		que->front = que->rear = 0;
		que->base = (int*)malloc(sizeof(int));
		if (!que->base) { printf("ERROR!"); }
		return que;
	}
	else
	{
		printf("Error");
	}
}


int DeQueue(Queue* que)
{
	int e;
	if (que->front == que->rear) 
	{ 
		printf("Queue is empty.\n"); 
		return -1;
	}
	else 
	{
		e = que->base[que->front];
		que->front = (que->front + 1) % MAXSIZE;
		return e;
	}
}


void EnQueue(Queue* que, int v)
{
	if ((que->rear + 1) % MAXSIZE == que->front) { printf("Queue is full. Fail to insert.\n"); }
	else {
		que->base[que->rear] = v;
		que->rear = (que->rear + 1) % MAXSIZE;  // Make queue a circle.
	}
}


int QueueEmpty(Queue* que)
{
	if (que->front == que->rear) { return 1; }
	else { return 0; }
}

主函数部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void main()
{
	AMGraph* amg = (AMGraph*)malloc(sizeof(AMGraph));
	ALGraph* alg = (ALGraph*)malloc(sizeof(ALGraph));
	if (amg)
	{
		CreatUDN(amg);
		int* visited1 = (int*)malloc(sizeof(int));
		char v, a;
		printf("Start position: \n");
		scanf_s("%c", &v, 1);
		a = getchar();
		int u = LocateVex(amg, v);
		DFS(amg, visited1, u);
		printf("\n");
	}
	if (alg)
	{
		CreatUDN2(alg);
		int* visited2 = (int*)malloc(sizeof(int));
		char v, a;
		printf("start position: \n");
		scanf_s("%c", &v, 1);
		a = getchar();
		int u = LocateVex2(alg, v);
		BFS(alg, visited2, u);
	}
}

2.改进与反思

不知何时free掉分配的内存。。

查看评论