以数组(邻接矩阵)或邻接表为存储结构,建立一个图。
时间: 2023-11-27 18:50:12 浏览: 46
好的,我来给你举个例子。假设我们要建立一个有向图,其中包括4个顶点和5条边,邻接矩阵如下:
```
1 2 3 4
1 0 1 0 1
2 1 0 1 0
3 0 0 0 1
4 0 1 1 0
```
其中,矩阵中的行表示出发顶点,列表示到达顶点,其中1表示有一条从出发顶点到到达顶点的有向边,0表示没有。
邻接表如下:
```
1 -> 2 -> 4
2 -> 1 -> 3
3 -> 4
4 -> 2 -> 3
```
其中,每个顶点对应一个链表,链表中存储该顶点指向的顶点编号。例如,1号顶点指向2、4号顶点,因此该链表为2 -> 4。
以上就是一个简单的图的邻接矩阵和邻接表的存储方式。
相关问题
用C语言写一个以数组(邻接矩阵)或邻接表为存储结构建立一个图,并且能输出图的深度优先序列或广度优先序列
以下是使用邻接表存储结构建立图,并输出深度优先序列和广度优先序列的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
#define FALSE 0
#define TRUE 1
// 邻接表结构体
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
int data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct{
AdjList vertices;
int vexnum, arcnum; // 顶点数和边数
}ALGraph;
// 初始化邻接表
void InitALGraph(ALGraph *G)
{
int i;
G->vexnum = G->arcnum = 0;
for(i = 0; i < MAX_VERTEX_NUM; i++){
G->vertices[i].firstarc = NULL;
}
}
// 添加顶点
void AddVertex(ALGraph *G, int v)
{
if(G->vexnum == MAX_VERTEX_NUM){
printf("Error: Vertex number exceeds maximum.\n");
return;
}
G->vertices[G->vexnum].data = v;
G->vexnum++;
}
// 添加边
void AddArc(ALGraph *G, int v1, int v2)
{
if(G->arcnum >= MAX_VERTEX_NUM * (MAX_VERTEX_NUM - 1) / 2){
printf("Error: Arc number exceeds maximum.\n");
return;
}
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = v2;
p->nextarc = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = p;
G->arcnum++;
}
// DFS遍历
void DFS(ALGraph *G, int v, int *visited)
{
printf("%d ", G->vertices[v].data);
visited[v] = TRUE;
ArcNode *p = G->vertices[v].firstarc;
while(p != NULL){
int w = p->adjvex;
if(!visited[w]){
DFS(G, w, visited);
}
p = p->nextarc;
}
}
// BFS遍历
void BFS(ALGraph *G, int v, int *visited)
{
int queue[MAX_VERTEX_NUM];
int front = -1, rear = -1;
printf("%d ", G->vertices[v].data);
visited[v] = TRUE;
queue[++rear] = v;
while(front != rear){
int w = queue[++front];
ArcNode *p = G->vertices[w].firstarc;
while(p != NULL){
int u = p->adjvex;
if(!visited[u]){
printf("%d ", G->vertices[u].data);
visited[u] = TRUE;
queue[++rear] = u;
}
p = p->nextarc;
}
}
}
int main()
{
ALGraph G;
InitALGraph(&G);
// 添加顶点
AddVertex(&G, 1);
AddVertex(&G, 2);
AddVertex(&G, 3);
AddVertex(&G, 4);
AddVertex(&G, 5);
// 添加边
AddArc(&G, 0, 1);
AddArc(&G, 0, 2);
AddArc(&G, 1, 3);
AddArc(&G, 1, 4);
AddArc(&G, 2, 4);
// 输出深度优先序列
int visited[MAX_VERTEX_NUM] = {FALSE};
printf("DFS: ");
DFS(&G, 0, visited);
printf("\n");
// 输出广度优先序列
int visited2[MAX_VERTEX_NUM] = {FALSE};
printf("BFS: ");
BFS(&G, 0, visited2);
printf("\n");
return 0;
}
```
以上代码中,使用邻接表存储结构,首先通过 `AddVertex` 函数添加顶点,再通过 `AddArc` 函数添加边。然后通过 `DFS` 函数和 `BFS` 函数分别输出深度优先序列和广度优先序列。为了避免重复遍历,使用 `visited` 数组记录每个顶点是否被访问过。
用C语言写一个图算法,以数组(邻接矩阵)或邻接表为存储结构,建立一个图,包括定义图的数组或邻接表存储表示,输出图G的深度优先序列,广度优先序列和邻接矩阵。
好的,以下是一个简单的图算法的C语言实现,使用邻接矩阵作为存储结构:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100
int visited[MAX_VERTICES]; // 记录是否已经访问过
int adjacency_matrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int queue[MAX_VERTICES]; // 广度优先搜索需要使用的队列
int num_vertices = 0; // 图中顶点的数量
// 添加边
void add_edge(int start, int end) {
adjacency_matrix[start][end] = 1;
adjacency_matrix[end][start] = 1;
}
// 深度优先搜索
void dfs(int vertex) {
visited[vertex] = 1;
printf("%d ", vertex);
for (int i = 0; i < num_vertices; i++) {
if (adjacency_matrix[vertex][i] && !visited[i]) {
dfs(i);
}
}
}
// 广度优先搜索
void bfs(int vertex) {
int front = 0, rear = 0;
queue[rear++] = vertex;
visited[vertex] = 1;
while (front != rear) {
int v = queue[front++];
printf("%d ", v);
for (int i = 0; i < num_vertices; i++) {
if (adjacency_matrix[v][i] && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
}
int main() {
scanf("%d", &num_vertices);
int num_edges;
scanf("%d", &num_edges);
for (int i = 0; i < num_edges; i++) {
int start, end;
scanf("%d %d", &start, &end);
add_edge(start, end);
}
printf("邻接矩阵:\n");
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
printf("%d ", adjacency_matrix[i][j]);
}
printf("\n");
}
printf("深度优先序列:");
for (int i = 0; i < num_vertices; i++) {
visited[i] = 0;
}
for (int i = 0; i < num_vertices; i++) {
if (!visited[i]) {
dfs(i);
}
}
printf("\n");
printf("广度优先序列:");
for (int i = 0; i < num_vertices; i++) {
visited[i] = 0;
}
for (int i = 0; i < num_vertices; i++) {
if (!visited[i]) {
bfs(i);
}
}
printf("\n");
return 0;
}
```
使用邻接表作为存储结构的实现和上述代码类似,只需要修改存储结构和深度优先搜索、广度优先搜索的实现即可。