写出从图的邻接表表示转换成邻接矩阵表示的算法, C语言写成过程形式。
时间: 2024-04-18 18:28:39 浏览: 57
以下是将图的邻接表表示转换为邻接矩阵表示的算法,使用C语言编写成过程形式:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
struct Node {
int vertex;
struct Node* next;
};
struct Graph {
int numVertices;
struct Node* adjacencyList[MAX_VERTICES];
};
void initializeGraph(struct Graph* graph, int numVertices) {
graph->numVertices = numVertices;
for (int i = 0; i < numVertices; i++) {
graph->adjacencyList[i] = NULL;
}
}
void addEdge(struct Graph* graph, int src, int dest) {
// 创建新节点
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = dest;
newNode->next = NULL;
// 将新节点插入到源顶点的邻接表中
if (graph->adjacencyList[src] == NULL) {
graph->adjacencyList[src] = newNode;
} else {
struct Node* temp = graph->adjacencyList[src];
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
// 创建新节点
newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->vertex = src;
newNode->next = NULL;
// 将新节点插入到目标顶点的邻接表中
if (graph->adjacencyList[dest] == NULL) {
graph->adjacencyList[dest] = newNode;
} else {
struct Node* temp = graph->adjacencyList[dest];
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}
void convertToAdjacencyMatrix(struct Graph* graph, int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES]) {
int numVertices = graph->numVertices;
for (int i = 0; i < numVertices; i++) {
struct Node* temp = graph->adjacencyList[i];
while (temp != NULL) {
int vertex = temp->vertex;
adjacencyMatrix[i][vertex] = 1;
temp = temp->next;
}
}
}
void printAdjacencyMatrix(int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES], int numVertices) {
printf("Adjacency Matrix:\n");
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
printf("%d ", adjacencyMatrix[i][j]);
}
printf("\n");
}
}
int main() {
int numVertices, numEdges;
printf("Enter the number of vertices and edges: ");
scanf("%d %d", &numVertices, &numEdges);
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
initializeGraph(graph, numVertices);
printf("Enter the edges (src dest):\n");
for (int i = 0; i < numEdges; i++) {
int src, dest;
scanf("%d %d", &src, &dest);
addEdge(graph, src, dest);
}
int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES] = {0};
convertToAdjacencyMatrix(graph, adjacencyMatrix);
printAdjacencyMatrix(adjacencyMatrix, numVertices);
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)