理解
时间: 2024-02-21 19:59:16 浏览: 12
好的,那我就开始回答您的问题。
首先,我们需要定义一个结构体来表示无向图中的顶点和边。代码如下:
```c
// 定义邻接表中的节点结构体
typedef struct node {
int vertex; // 顶点编号
struct node* next; // 指向下一个节点的指针
} Node;
// 定义邻接表中的头结点结构体
typedef struct head {
Node* first; // 指向第一个节点的指针
} Head;
// 定义无向图结构体
typedef struct graph {
int v; // 顶点数目
Head* array; // 邻接表数组
} Graph;
```
然后,我们需要编写一个函数来创建无向图的邻接表。这个函数需要从用户输入中读取顶点数目和边的信息,并将这些信息存储在邻接表中。代码如下:
```c
// 创建无向图的邻接表
Graph* createGraph() {
int v, e, i;
printf("请输入顶点数目和边数目:");
scanf("%d%d", &v, &e);
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->v = v;
graph->array = (Head*)malloc(v * sizeof(Head));
for (i = 0; i < v; i++) {
graph->array[i].first = NULL;
}
for (i = 0; i < e; i++) {
int src, dest;
printf("请输入第%d条边的起点和终点:", i + 1);
scanf("%d%d", &src, &dest);
// 添加一条从起点到终点的边
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = dest;
newNode->next = graph->array[src].first;
graph->array[src].first = newNode;
// 添加一条从终点到起点的边
newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = src;
newNode->next = graph->array[dest].first;
graph->array[dest].first = newNode;
}
return graph;
}
```
接下来,我们需要编写一个函数来进行深度优先搜索,并输出遍历得到的顶点序列。这个函数首先需要初始化一个布尔型数组来记录每个顶点是否被访问过,然后从第一个顶点开始进行深度优先搜索。代码如下:
```c
// 深度优先搜索遍历无向图
void DFS(Graph* graph, int v, bool visited[]) {
visited[v] = true;
printf("%d ", v);
Node* node = graph->array[v].first;
while (node != NULL) {
if (!visited[node->vertex]) {
DFS(graph, node->vertex, visited);
}
node = node->next;
}
}
// 输出深度优先搜索遍历得到的顶点序列
void printDFS(Graph* graph) {
bool visited[graph->v];
int i;
for (i = 0; i < graph->v; i++) {
visited[i] = false;
}
for (i = 0; i < graph->v; i++) {
if (!visited[i]) {
DFS(graph, i, visited);
}
}
}
```
最后,我们可以在主函数中调用这些函数来创建无向图并输出深度优先搜索遍历得到的顶点序列。代码如下:
```c
int main() {
Graph* graph = createGraph();
printf("深度优先搜索遍历得到的顶点序列为:");
printDFS(graph);
printf("\n");
return 0;
}
```
这样,一个采用交互方式建立无向图邻接表并输出深度优先搜索遍历得到的顶点序列的程序就完成了。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)