实验时间： 第11周
实验目的： 掌握图的邻接矩阵、邻接表两种存储结构，能够实现在任意一种存储结构上的创建和遍历两种基本操作
实验要求：
1、认真阅读和掌握教材上和本实验相关内容和算法（见P161~170）。
2、上机将图的任意一种存储表示的创建和遍历（DFS和BFS至少实现一种）算法实现。
3、实现下面实验内容要求的功能，并能够进行简单的输入输出验证。
实验内容：
1、 图的创建部分
编程实现图的任意一种存储表示的创建算法，要求能够进行简单的输入输出验证。
2、 图的遍历操作部分
编程实现图的遍历操作，至少实现图的深度优先搜索和广度优先搜索两种遍历算法中的一种，要求能够进行简单的输入输出验证。
图的创建与遍历（使用邻接矩阵）
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
// Representation of Graph using Adjacency Matrix
typedef struct {
int V; // Number of vertices
int **matrix; // Adjacency matrix
} GraphAdjMatrix;
GraphAdjMatrix* createGraphAdjMatrix(int vertices) {
GraphAdjMatrix* graph = (GraphAdjMatrix*)malloc(sizeof(GraphAdjMatrix));
graph->V = vertices;
// Allocate memory for adjacency matrix
graph->matrix = (int**)malloc(vertices * sizeof(int*));
for (int i = 0; i < vertices; ++i) {
graph->matrix[i] = (int*)calloc(vertices, sizeof(int));
}
return graph;
}
void addEdgeAdjMatrix(GraphAdjMatrix* graph, int src, int dest) {
// Assuming it's an undirected graph, assigning 1 for both directions
graph->matrix[src][dest] = 1;
graph->matrix[dest][src] = 1;
}
void printGraphAdjMatrix(GraphAdjMatrix* graph) {
printf("Adjacency Matrix:\n");
for (int i = 0; i < graph->V; ++i) {
for (int j = 0; j < graph->V; ++j) {
printf("%d ", graph->matrix[i][j]);
}
printf("\n");
}
}
void freeGraphAdjMatrix(GraphAdjMatrix* graph) {
for (int i = 0; i < graph->V; ++i) {
free(graph->matrix[i]);
}
free(graph->matrix);
free(graph);
}
int main() {
int V = 4; // Number of vertices
GraphAdjMatrix* g = createGraphAdjMatrix(V);
addEdgeAdjMatrix(g, 0, 1);
addEdgeAdjMatrix(g, 0, 2);
addEdgeAdjMatrix(g, 1, 2);
addEdgeAdjMatrix(g, 2, 3);
printGraphAdjMatrix(g);
freeGraphAdjMatrix(g);
return 0;
}
结果演示：
图的创建与遍历（使用邻接表）
#include <stdio.h>
#include <stdlib.h>
// Node to store adjacent vertices in Adjacency List
typedef struct Node {
int dest;
struct Node* next;
} Node;
// Adjacency List representation of Graph
typedef struct {
int V; // Number of vertices
Node** array; // Array of adjacency lists
} GraphAdjList;
Node* createNode(int dest) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
GraphAdjList* createGraphAdjList(int vertices) {
GraphAdjList* graph = (GraphAdjList*)malloc(sizeof(GraphAdjList));
graph->V = vertices;
// Create an array of adjacency lists
graph->array = (Node**)malloc(vertices * sizeof(Node*));
for (int i = 0; i < vertices; ++i) {
graph->array[i] = NULL;
}
return graph;
}
void addEdgeAdjList(GraphAdjList* graph, int src, int dest) {
// Add edge from src to dest
Node* newNode = createNode(dest);
newNode->next = graph->array[src];
graph->array[src] = newNode;
// For undirected graph, uncomment the lines below
/*
newNode = createNode(src);
newNode->next = graph->array[dest];
graph->array[dest] = newNode;
*/
}
void printGraphAdjList(GraphAdjList* graph) {
printf("Adjacency List:\n");
for (int i = 0; i < graph->V; ++i) {
Node* temp = graph->array[i];
printf("Adjacency list of vertex %d: ", i);
while (temp != NULL) {
printf("%d -> ", temp->dest);
temp = temp->next;
}
printf("NULL\n");
}
}
void freeGraphAdjList(GraphAdjList* graph) {
for (int i = 0; i < graph->V; ++i) {
Node* current = graph->array[i];
while (current != NULL) {
Node* next = current->next;
free(current);
current = next;
}
}
free(graph->array);
free(graph);
}
int main() {
int V = 4; // Number of vertices
GraphAdjList* g = createGraphAdjList(V);
addEdgeAdjList(g, 0, 1);
addEdgeAdjList(g, 0, 2);
addEdgeAdjList(g, 1, 2);
addEdgeAdjList(g, 2, 3);
printGraphAdjList(g);
freeGraphAdjList(g);
return 0;
}
结果演示：
