题目一
题目要求
利用邻接矩阵存储无向图，并从0号顶点开始进行深度优先遍历。
输入
输入第一行是两个整数n1 n2，其中n1表示顶点数（则顶点编号为0至n1-1），n2表示图中的边数。
之后有n2行输入，每行输入表示一条边，格式是“顶点1 顶点2”，把边插入图中。
例如：
4 4
0 1
1 3
0 3
0 2
输出
先输出存储图的邻接矩阵，同一行元素之间空1格，最后一个元素之后不要有空格。
之后空一行后输出从0号顶点开始的深度优先遍历序列，顶点编号之间空1格。
例如，对于上面的示例输入，输出为：
0 1 1 1
1 0 0 1
1 0 0 0
1 1 0 0
0 1 3 2
说明
输入第1个4表示有4个顶点，第2个4表示有4条边。之后的4行输入代表4条边的顶点。输出的前4行为邻接矩阵，之后空一行，然后输出的“0 1 3 2”是深度优先遍历序列。
代码实现
邻接矩阵图相关定义：
typedef int Vertex;
typedef int WeightType;
typedef struct EdgeNode {
Vertex v1, v2;
}*Edge;
typedef struct MatrixGraphNode {
int vertexNum; /* 顶点数 */
int edgeNum; /* 边数 */
WeightType** adjMatrix; /* 邻接矩阵 */
int* visited; /* 标记数组，用来标记某一个点是否被访问过，DFS时要用到，也可以把它定义为全局变量，这里为了方便就写在结构体里 */
} *MatrixGraph;
邻接矩阵图的相关操作：
这里选择动态创建二维数组，因为不知道测试样例最大顶点数是多少。读者当然可以直接在定义结构体把就把adjMatrix定义为一个足够大的二维数组，而不必如此麻烦的动态创建。
MatrixGraph createMatrixGraph(int vertexNum) {
MatrixGraph graph = (MatrixGraph)malloc(sizeof(struct MatrixGraphNode));
graph->vertexNum = vertexNum;
graph->edgeNum = 0;
graph->visited = (int*)malloc(sizeof(int) * graph->vertexNum);
/* 动态创建二维数组 */
graph->adjMatrix = (WeightType**)malloc(sizeof(WeightType*) * graph->vertexNum);
for (int i = 0;i < graph->vertexNum;i++)
graph->adjMatrix[i] = (WeightType*)malloc(sizeof(WeightType) * graph->vertexNum);
/* 初始化邻接矩阵adjMatrix和标记数组visited */
for (int i = 0;i < graph->vertexNum;i++) {
graph->visited[i] = 0;
for (int j = 0;j < graph->vertexNum;j++)
graph->adjMatrix[i][j] = 0;
}
return graph;
}
void insertEdge(MatrixGraph graph, Edge edge) {
graph->adjMatrix[edge->v1][edge->v2] = 1;
graph->adjMatrix[edge->v2][edge->v1] = 1;
}
MatrixGraph buildMatrixGraph() {
Edge edge = (Edge)malloc(sizeof(struct EdgeNode));
int vertexNum;
scanf("%d", &vertexNum);
MatrixGraph graph = createMatrixGraph(vertexNum);
scanf("%d", &graph->edgeNum);
for (int i = 0;i < graph->edgeNum;i++) {
scanf("%d%d", &edge->v1, &edge->v2);
insertEdge(graph, edge);
}
return graph;
}
深度优先搜索DFS和打印邻接矩阵图
void DFS(MatrixGraph graph, Vertex v) {
/* 访问当前顶点 */
printf("%d ", v);
graph->visited[v] = 1;
for (int i = 0;i < graph->vertexNum;i++)
/* 如果w没有被访问且和v相连，就递归地访问它 */
if (!graph->visited[i] && isEdge(graph, v, i))
DFS(graph, i);
}
void printGraph(MatrixGraph graph) {
for (int i = 0;i < graph->vertexNum;i++)
for (int j = 0;j < graph->vertexNum;j++)
j == graph->vertexNum - 1 ? printf("%d\n", graph->adjMatrix[i][j]) : printf("%d ", graph->adjMatrix[i][j]);
}
主函数
int main() {
MatrixGraph graph = buildMatrixGraph();
printGraph(graph);
DFS(graph, 0);
system("pause");
return 0;
}
运行结果
题目二
题目要求
利用邻接表存储无向图，并从0号顶点开始进行广度优先遍历。
输入
输入第一行是两个整数n1 n2，其中n1表示顶点数（则顶点编号为0至n1-1），n2表示图中的边数。
之后有n2行输入，每行输入表示一条边，格式是“顶点1 顶点2”，把边插入图中。在链表中插入元素时，在链表头部插入。需要注意，由于是无向图，因此同一条边需要在两条链表中都插入。
例如：
4 4
0 1
1 3
0 3
0 2
输出
先按0至n1-1输出存储图的邻接表，每个链表占1行，同一行元素之间空1格，最后一个元素之后不要有空格。先输出顶点编号，之后按链表顺序输出相邻顶点编号。
之后空一行后输出从0号顶点开始的广度优先遍历序列，顶点编号之间空1格。
例如，对于上面的示例输入，输出为：
0 2 3 1
1 3 0
2 0
3 0 1
0 2 3 1
说明
输入第1个4表示有4个顶点，第2个4表示有4条边。之后的4行输入代表4条边的顶点。输出前4行为邻接表中的4个链表，之后空一行，然后输出的“0 2 3 1”是深度优先遍历序列。文章来源：https://www.toymoban.com/news/detail-487758.html
代码实现
邻接表相关定义
typedef int Vertex;
/* 边 */
typedef struct EdgeNode {
Vertex v1, v2;
}*Edge;
/* 邻接点 */
typedef struct AdjVNode {
Vertex adjVertex;
struct AdjVNode* next;
}*AdjVNodePtr;
/* 邻接表头节点 */
typedef struct VertexNode {
AdjVNodePtr firstEdge;
}*AdjList;
/* 邻接表图 */
typedef struct ListGraphNode {
int vertexNum;
int edgeNum;
AdjList adjList;
int* visited;
}*ListGraph;
图的相关操作
ListGraph createListGraph(int vertexNum) {
ListGraph graph = (ListGraph)malloc(sizeof(struct ListGraphNode));
graph->vertexNum = vertexNum;
graph->edgeNum = 0;
graph->visited = (int*)malloc(sizeof(int));
graph->adjList = (AdjList)malloc(sizeof(struct VertexNode) * graph->vertexNum);
/* 初始化邻接表和标记数组 */
for (int i = 0;i < graph->vertexNum;i++) {
graph->adjList[i].firstEdge = NULL;
graph->visited[i] = 0;
}
return graph;
}
void insertEdge(ListGraph graph, Edge edge) {
/* 插入边<v1,v2> */
AdjVNodePtr newNode = (AdjVNodePtr)malloc(sizeof(struct AdjVNode));
newNode->adjVertex = edge->v2;
newNode->next = graph->adjList[edge->v1].firstEdge;
graph->adjList[edge->v1].firstEdge = newNode;
/* 插入边<v2,v1> */
newNode = (AdjVNodePtr)malloc(sizeof(struct AdjVNode));
newNode->adjVertex = edge->v1;
newNode->next = graph->adjList[edge->v2].firstEdge;
graph->adjList[edge->v2].firstEdge = newNode;
}
ListGraph buildListGraph() {
Edge edge = (Edge)malloc(sizeof(struct EdgeNode));
int vertexNum;
scanf("%d", &vertexNum);
ListGraph graph = createListGraph(vertexNum);
scanf("%d", &graph->edgeNum);
for (int i = 0;i < graph->edgeNum;i++) {
scanf("%d%d", &edge->v1, &edge->v2);
insertEdge(graph, edge);
}
return graph;
}
深度优先搜索BFS和打印邻接表图
/* 队列及相关操作 */
typedef struct QueueNode {
int* data;
int front, rear;
int maxSize;
}*Queue;
Queue createQueue(int maxSize) {
Queue queue = (Queue)malloc(sizeof(struct QueueNode));
queue->maxSize = maxSize;
queue->data = (int*)malloc(sizeof(int) * queue->maxSize);
queue->front = queue->rear = 0;
return queue;
}
int isFull(Queue queue) {
return queue->front == (queue->rear + 1) % queue->maxSize;
}
int isEmpty(Queue queue) {
return queue->front == queue->rear;
}
void addQueue(Queue queue, int data) {
if (isFull(queue))
return;
queue->data[queue->rear] = data;
queue->rear = (queue->rear + 1) % queue->maxSize;
}
int deleteQueue(Queue queue) {
if (isEmpty(queue))
return -1;
int data = queue->data[queue->front];
queue->front = (queue->front + 1) % queue->maxSize;
return data;
}
/* 深度优先搜索 */
void BFS(ListGraph graph, Vertex start) {
Queue queue = createQueue(graph->vertexNum);
printf("%d ", start);
graph->visited[start] = 1;
addQueue(queue, start);
Vertex v;
while (!isEmpty(queue)) {
v = deleteQueue(queue);
for (AdjVNodePtr w = graph->adjList[v].firstEdge;w;w = w->next) {
if (!graph->visited[w->adjVertex]) {
printf("%d ", w->adjVertex);
graph->visited[w->adjVertex] = 1;
addQueue(queue, w->adjVertex);
}
}
}
}
/* 打印图 */
void printGraph(ListGraph graph) {
for (int i = 0;i < graph->vertexNum;i++) {
printf("%d ", i);
for (AdjVNodePtr w = graph->adjList[i].firstEdge;w;w = w->next)
w->next == NULL ? printf("%d\n", w->adjVertex) : printf("%d ", w->adjVertex);
}
}
主函数
int main() {
ListGraph graph = buildListGraph();
printGraph(graph);
BFS(graph, 0);
system("pause");
return 0;
}
运行结果图
文章来源地址https://www.toymoban.com/news/detail-487758.html
到了这里，关于数据结构实验6 ：图的存储与遍历（邻接矩阵的深度优先遍历DFS和邻接表的广度优先遍历BFS）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
