通过C语言代码实现分别实现有向网和无向网的邻接矩阵存储的创建函数,以及图的深度优先搜索函数。通过以下给出的有向网和无向往进行验证。(顶点的数据为顶点的名称字符数组char name[2]:“G1“,G2“,“G3”…)
时间: 2024-02-12 21:09:53 浏览: 83
邻接矩阵存储的无向网的基本操作(C语言实现)
好的,我来回答你的问题。
首先,我们先定义一个图的结构体,包含了顶点数量、边的数量和邻接矩阵等信息:
```c
typedef struct {
int vexnum; // 顶点数量
int edgenum; // 边的数量
int **matrix; // 邻接矩阵
char **vexname; // 顶点名称
} Graph;
```
接着,我们可以定义一个创建有向网的邻接矩阵的函数:
```c
Graph* createDirectedGraph(char vexname[][3], int n, int edges[][3], int m) {
Graph* g = (Graph*)malloc(sizeof(Graph));
g->vexnum = n;
g->edgenum = m;
g->vexname = (char**)malloc(n * sizeof(char*));
for (int i = 0; i < n; i++) {
g->vexname[i] = (char*)malloc(3 * sizeof(char));
strcpy(g->vexname[i], vexname[i]);
}
g->matrix = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
g->matrix[i] = (int*)malloc(n * sizeof(int));
memset(g->matrix[i], 0, n * sizeof(int));
}
for (int i = 0; i < m; i++) {
int start = edges[i][0];
int end = edges[i][1];
int weight = edges[i][2];
g->matrix[start][end] = weight;
}
return g;
}
```
这个函数的参数包括了顶点名称数组、顶点数量、边数组和边的数量。我们首先根据顶点数量和边的数量分配内存空间,并设置相应的属性值。然后,我们遍历边数组,根据起点、终点和权值设置邻接矩阵。
接下来,我们可以定义一个创建无向网的邻接矩阵的函数:
```c
Graph* createUndirectedGraph(char vexname[][3], int n, int edges[][3], int m) {
Graph* g = (Graph*)malloc(sizeof(Graph));
g->vexnum = n;
g->edgenum = m;
g->vexname = (char**)malloc(n * sizeof(char*));
for (int i = 0; i < n; i++) {
g->vexname[i] = (char*)malloc(3 * sizeof(char));
strcpy(g->vexname[i], vexname[i]);
}
g->matrix = (int**)malloc(n * sizeof(int*));
for (int i = 0; i < n; i++) {
g->matrix[i] = (int*)malloc(n * sizeof(int));
memset(g->matrix[i], 0, n * sizeof(int));
}
for (int i = 0; i < m; i++) {
int start = edges[i][0];
int end = edges[i][1];
int weight = edges[i][2];
g->matrix[start][end] = weight;
g->matrix[end][start] = weight;
}
return g;
}
```
这个函数的实现与创建有向网的邻接矩阵的函数类似,唯一的不同是在设置邻接矩阵的时候,我们需要同时设置起点到终点和终点到起点的权值。
最后,我们可以定义一个深度优先搜索的函数:
```c
void DFS(Graph* g, int v, int* visited) {
printf("%s ", g->vexname[v]);
visited[v] = 1;
for (int i = 0; i < g->vexnum; i++) {
if (g->matrix[v][i] != 0 && visited[i] == 0) {
DFS(g, i, visited);
}
}
}
```
这个函数的参数包括了图、起点和一个表示顶点是否被访问过的数组。我们先输出起点的名称,然后将其标记为已访问。接着,我们遍历与起点相邻的所有顶点,如果该顶点未被访问,则递归调用 DFS 函数。
下面是一个用来测试这些函数的例子:
```c
int main() {
char vexname[3][3] = {"G1", "G2", "G3"};
int directed_edges[5][3] = {
{0, 1, 3},
{1, 2, 4},
{2, 0, 5},
{0, 2, 1},
{2, 1, 2}
};
int undirected_edges[5][3] = {
{0, 1, 3},
{1, 2, 4},
{2, 0, 5},
{0, 2, 1},
{1, 2, 2}
};
Graph* directed_graph = createDirectedGraph(vexname, 3, directed_edges, 5);
Graph* undirected_graph = createUndirectedGraph(vexname, 3, undirected_edges, 5);
int visited[3] = {0};
printf("Directed graph DFS: ");
DFS(directed_graph, 0, visited);
printf("\n");
memset(visited, 0, 3 * sizeof(int));
printf("Undirected graph DFS: ");
DFS(undirected_graph, 0, visited);
printf("\n");
return 0;
}
```
这个例子首先定义了一个三个顶点的图,包含了两个数组分别代表有向网和无向网的边。然后,我们分别创建了有向网和无向网的邻接矩阵,并利用 DFS 函数进行遍历。最后,我们释放了申请的内存空间。
希望这个例子能够帮助你理解如何实现有向网和无向网的邻接矩阵存储和深度优先搜索函数。
阅读全文