1. 建立无向图的邻接矩阵存储并输出。2. 建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历。
时间: 2023-04-27 16:02:52 浏览: 70
1. 建立无向图的邻接矩阵存储并输出:
邻接矩阵是一种常用的图的存储方式,可以用一个二维数组来表示图中各个节点之间的关系。对于无向图,邻接矩阵是一个对称矩阵,即矩阵中的第i行第j列和第j行第i列都表示节点i和节点j之间是否有边相连。
下面是一个无向图的邻接矩阵示例:
```
1 2 3 4 5
1 0 1 1 0 0
2 1 0 1 1 0
3 1 1 0 0 1
4 0 1 0 0 1
5 0 0 1 1 0
```
其中,矩阵中的每个元素表示两个节点之间的边是否存在,1表示存在,0表示不存在。
2. 建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历:
邻接表是另一种常用的图的存储方式,它将每个节点的所有邻居节点都存储在一个链表中。对于无向图,每个节点的邻居节点都是双向的,因此邻接表中需要存储两个方向的链表。
下面是一个无向图的邻接表示例:
```
1 -> 2 -> 3
2 -> 1 -> 3 -> 4
3 -> 1 -> 2 -> 5
4 -> 2 -> 5
5 -> 3 -> 4
```
其中,每个节点后面的箭头表示该节点的邻居节点。
在邻接表的基础上,可以实现图的深度优先遍历和广度优先遍历。深度优先遍历是一种递归的方式,从起点节点开始,先访问它的一个邻居节点,然后再递归访问该邻居节点的邻居节点,直到所有节点都被访问过。广度优先遍历则是一种迭代的方式,从起点节点开始,先访问它的所有邻居节点,然后再依次访问它们的邻居节点,直到所有节点都被访问过。
相关问题
用c++写一个代码实现1.建立无向图的邻接矩阵存储并输出。 2.建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历。
1. 建立无向图的邻接矩阵存储并输出
```c++
#include <iostream>
using namespace std;
const int MAXN = 100;
int graph[MAXN][MAXN]; // 邻接矩阵
int main() {
int n, m; // n 个节点,m 条边
cin >> n >> m;
// 初始化邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
graph[i][j] = 0;
}
}
// 读入每一条边
for (int i = 0; i < m; i++) {
int u, v; // u 和 v 之间有一条边
cin >> u >> v;
graph[u][v] = graph[v][u] = 1; // 无向图
}
// 输出邻接矩阵
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << graph[i][j] << " ";
}
cout << endl;
}
return 0;
}
```
2. 建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100;
vector<int> adj[MAXN]; // 邻接表
bool visited[MAXN]; // 标记每个节点是否已被访问
// 深度优先遍历
void dfs(int u) {
cout << u << " ";
visited[u] = true;
for (int v : adj[u]) {
if (!visited[v]) {
dfs(v);
}
}
}
// 广度优先遍历
void bfs(int u) {
queue<int> q;
q.push(u);
visited[u] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";
for (int v : adj[u]) {
if (!visited[v]) {
q.push(v);
visited[v] = true;
}
}
}
}
int main() {
int n, m; // n 个节点,m 条边
cin >> n >> m;
// 初始化邻接表
for (int i = 0; i < n; i++) {
adj[i].clear();
visited[i] = false;
}
// 读入每一条边
for (int i = 0; i < m; i++) {
int u, v; // u 和 v 之间有一条边
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u); // 无向图
}
// 从节点 0 开始进行深度优先遍历
cout << "Depth First Search: ";
dfs(0);
cout << endl;
// 重新初始化 visited 数组
for (int i = 0; i < n; i++) {
visited[i] = false;
}
// 从节点 0 开始进行广度优先遍历
cout << "Breadth First Search: ";
bfs(0);
cout << endl;
return 0;
}
```
c语言实现 建立无向图的邻接矩阵存储并输出。2. 建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历。
1. 无向图的邻接矩阵存储
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int vexs[MAX_VERTEX_NUM]; // 顶点数组
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vexnum, arcnum; // 顶点数和边数
} Graph;
void CreateGraph(Graph *G) {
int i, j, k;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入顶点信息:");
for (i = 0; i < G->vexnum; ++i) {
scanf("%d", &G->vexs[i]);
}
for (i = 0; i < G->vexnum; ++i) {
for (j = 0; j < G->vexnum; ++j) {
G->arcs[i][j] = 0; // 初始化为0
}
}
printf("请输入每条边的两个顶点序号:\n");
for (k = 0; k < G->arcnum; ++k) {
scanf("%d%d", &i, &j);
G->arcs[i][j] = G->arcs[j][i] = 1; // i,j之间有边,邻接矩阵为1
}
}
void PrintGraph(Graph G) {
int i, j;
printf("邻接矩阵:\n");
for (i = 0; i < G.vexnum; ++i) {
for (j = 0; j < G.vexnum; ++j) {
printf("%d ", G.arcs[i][j]);
}
printf("\n");
}
}
int main() {
Graph G;
CreateGraph(&G);
PrintGraph(G);
return 0;
}
```
2. 邻接表存储图并遍历
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct ArcNode { // 边结点
int adjvex; // 相邻顶点序号
struct ArcNode *next; // 下一条边
} ArcNode;
typedef struct {
int data; // 顶点信息
ArcNode *first; // 第一条边
} VNode;
typedef struct {
VNode vertices[MAX_VERTEX_NUM]; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} Graph;
void CreateGraph(Graph *G) {
int i, j, k;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入顶点信息:");
for (i = 0; i < G->vexnum; ++i) {
scanf("%d", &G->vertices[i].data);
G->vertices[i].first = NULL;
}
printf("请输入每条边的两个顶点序号:\n");
for (k = 0; k < G->arcnum; ++k) {
scanf("%d%d", &i, &j);
// 添加一条边(i,j)
ArcNode *node = (ArcNode *) malloc(sizeof(ArcNode));
node->adjvex = j;
node->next = G->vertices[i].first;
G->vertices[i].first = node;
// 添加一条边(j,i)
node = (ArcNode *) malloc(sizeof(ArcNode));
node->adjvex = i;
node->next = G->vertices[j].first;
G->vertices[j].first = node;
}
}
void DFS(Graph G, int v, int *visited) {
visited[v] = 1;
printf("%d ", G.vertices[v].data);
ArcNode *p = G.vertices[v].first;
while (p != NULL) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
void DFSTraverse(Graph G) {
int i, visited[MAX_VERTEX_NUM] = {0}; // 初始化为0
printf("深度优先遍历:");
for (i = 0; i < G.vexnum; ++i) {
if (!visited[i]) {
DFS(G, i, visited);
}
}
printf("\n");
}
void BFS(Graph G, int v, int *visited) {
int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
visited[v] = 1;
printf("%d ", G.vertices[v].data);
queue[rear++] = v;
while (front != rear) {
int u = queue[front++];
ArcNode *p = G.vertices[u].first;
while (p != NULL) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = 1;
printf("%d ", G.vertices[p->adjvex].data);
queue[rear++] = p->adjvex;
}
p = p->next;
}
}
}
void BFSTraverse(Graph G) {
int i, visited[MAX_VERTEX_NUM] = {0}; // 初始化为0
printf("广度优先遍历:");
for (i = 0; i < G.vexnum; ++i) {
if (!visited[i]) {
BFS(G, i, visited);
}
}
printf("\n");
}
int main() {
Graph G;
CreateGraph(&G);
DFSTraverse(G);
BFSTraverse(G);
return 0;
}
```