用C语言根据给出的顶点数和边数. 建立无向有权图的邻接表; 并对图输出深度优先搜索遍历序列。例子:输入 4 5 2 3 1 1 3 2 0 3 4 0 2 2 0 1 1 0 输出 0 1 3 2
时间: 2024-10-25 21:13:03 浏览: 15
在C语言中,建立无向有权图的邻接表通常涉及以下几个步骤:
1. 定义结构体:首先,我们需要定义一个表示节点的数据结构,它可能包含顶点值、邻接列表以及权重等信息。
```c
typedef struct Node {
int vertex;
struct Node* adj_list; // 邻接列表头部指针
int weight; // 权重值(如果有的话)
} Node;
```
2. 创建邻接表:对于给定的顶点数和边数,你可以创建一个大小足够的数组来存储所有节点,并初始化邻接列表。
```c
Node* create_graph(int vertices, int edges) {
Node** adjacency_list = (Node**)malloc(vertices * sizeof(Node*));
for (int i = 0; i < vertices; ++i)
adjacency_list[i] = NULL;
// 根据边的信息填充邻接表
int edge_index = 0;
for (int i = 0; i < edges; ++i) {
int src, dest, weight;
scanf("%d %d %d", &src, &dest, &weight);
add_edge(adjacency_list, src, dest, weight, edge_index++);
}
return adjacency_list;
}
void add_edge(Node** list, int src, int dest, int weight, int index) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = dest;
newNode->adj_list = list[src];
newNode->weight = weight;
list[src] = newNode;
}
```
3. 深度优先搜索遍历:使用递归实现DFS遍历并输出访问过的节点序列。
```c
void dfs(Node* node, bool visited[], int result[]) {
if (!visited[node->vertex]) {
visited[node->vertex] = true;
result[dfs_count++] = node->vertex; // 记录路径
Node* temp = node->adj_list;
while (temp != NULL) {
dfs(temp, visited, result);
temp = temp->adj_list;
}
}
}
void print_dfs_sequence(Node* graph, int vertices) {
int result[vertices], dfs_count = 0;
bool visited[vertices] = {false};
// 从任意未访问节点开始
for (int i = 0; i < vertices; ++i)
if (!visited[i])
dfs(graph + i, visited, result);
printf("Depth First Search sequence: ");
for (int i = 0; i < dfs_count; ++i)
printf("%d ", result[i]);
printf("\n");
}
```
最后,你可以结合上述函数来处理用户输入,先建立图,然后进行深度优先搜索并打印结果。
注意:这个示例假设了每个顶点都有权重,如果你的问题中不需要权重,可以简化Node结构和add_edge函数。同时,这里只实现了基本功能,实际项目中可能需要考虑错误检查和内存管理等问题。
阅读全文