首页 > 其他分享 >数据结构【完整代码】之（C语言实现【图的存储创建遍历】邻接矩阵与邻接表）

数据结构【完整代码】之（C语言实现【图的存储创建遍历】邻接矩阵与邻接表）

时间：2022-11-01 22:01:50浏览次数：50  
标签：遍历 int 邻接矩阵 C语言 ++ numVertexes visited GM GL


零、编码前的准备

1.构画草图：

数据结构【完整代码】之（C语言实现【图的存储创建遍历】邻接矩阵与邻接表）_i++


2.测试数据：

邻接表的DFS与BFS测试数据：
4 5
ABCD
0 1
0 2
0 3
1 2
3 2

邻接矩阵的DFS与BFS测试数据：
4 5
ABCD
0 1 5
0 2 10
0 3 10
1 2 15
3 2 30

一、邻接矩阵

包含四个文件的代码和一张测试效果图：

  • AdjacencyMatrix.h文件： 构建邻接矩阵的存储结构与邻接矩阵的创建函数
  • DBFSAdjacencyMatrix.h文件： 构建邻接矩阵的深度优先遍历与广度优先遍历函数
  • StackAndQueue.h文件： 应广度优先遍历所需，提供队列的基本操作
  • test.cpp文件： 用于测试
  • 效果图：（如下）

效果图：

数据结构【完整代码】之（C语言实现【图的存储创建遍历】邻接矩阵与邻接表）_数据结构_02


AdjacencyMatrix.h文件：

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100
#define INFINITY 65535

typedef char VertexType;
typedef int EdgeType; 

typedef struct{
  VertexType vexs[MAXVEX]; //顶点表 
  EdgeType arc[MAXVEX][MAXVEX]; //邻接矩阵 
  int numVertexes, numEdges; //图中当前顶点数和边数 
}GraphMatrix;

void CreateGraphMatrix(GraphMatrix *G){ //无向图的创建 
  int i, j, k, w;
  printf("输入顶点数和边数：\n");
  scanf("%d%d", &G->numVertexes, &G->numEdges);
  getchar();
  for(i = 0; i < G->numVertexes; i++){
    scanf("%c", &G->vexs[i]);
  }
  for(i = 0; i < G->numVertexes; i++){
    for(j = 0; j < G->numVertexes; j++){
      G->arc[i][j] = INFINITY; //邻接矩阵初始化 
    }
  }
  for(k = 0; k < G->numEdges; k++){
    printf("输入边（vi，vj）上的下标i，下标j和权w：\n");
    scanf("%d%d%d", &i, &j, &w);
    G->arc[i][j] = w; //输入边（vi，vj）上的权w
    G->arc[j][i] = G->arc[i][j]; //因为是无向图，矩阵对称 
  } 
}

DBFSAdjacencyMatrix.h文件：

#include"AdjacencyMatrix.h"
#include"StackAndQueue.h"
#define MAX 100 

int visited[MAX];

void BFSTraverse(GraphMatrix GM){
  int i, j;
  SqQueue Q;
  for(i = 0; i < GM.numVertexes; i++){
    visited[i] = FALSE;
  }
  InitQueue(&Q); //初始化一辅助用的队列
  for(i = 0; i < GM.numVertexes; i++){
    if(!visited[i]){
      visited[i] = TRUE; //设置当前顶点访问过
      printf("%c ", GM.vexs[i]);
      EnQueue(&Q, i);
      while(QueueLength(Q) > 0){
        DeQueue(&Q, &i);
        for(j = 0; j < GM.numVertexes; j++){
          if(GM.arc[i][j] > 0 && GM.arc[i][j] != INFINITY && !visited[j]){ //判断其它顶点若与当前顶点存在边且未访问过 
            visited[j] = TRUE;
            printf("%c ", GM.vexs[j]);
            EnQueue(&Q, j); 
          }
        }
      } 
    }
  } 
} 

void DFS(GraphMatrix GM, int i){
  int j;
  visited[i] = TRUE;
  printf("%c ", GM.vexs[i]);
  for(j = 0; j < GM.numVertexes; j++){
    if(GM.arc[i][j] > 0 && GM.arc[i][j] != INFINITY && !visited[j]){
      DFS(GM, j);
    }
  } 
} 

void DFSTraverse(GraphMatrix GM){
  int i;
  for(i = 0; i < GM.numVertexes; i++){
    visited[i] = FALSE;
  }
  for(i = 0; i < GM.numVertexes; i++){
    if(!visited[i]){
      DFS(GM, i);
    }
  }
}

StackAndQueue.h文件：

#include<stdio.h>
#include <string.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20

typedef int Status; 

//---------------栈
typedef char SElemType;
typedef struct{
  SElemType data[MAXSIZE];
  int top; //用于栈顶指针 
}SqStack;

Status InitStack(SqStack *S){
  for(int i = 0; i < MAXSIZE; i++){
    S->data[i] = ' '; //用0初始化 
  }
  S->top = -1;
}

Status StackSize(SqStack S){
  return (S.top+1);
}

Status Push(SqStack *S, SElemType e){ //------进栈 
  if(S->top == MAXSIZE - 1){ //栈满 
    return ERROR;
  }
  S->top++; //栈顶指针增加一 
  S->data[S->top] = e; //将新插入元素赋值给栈顶空间
  return OK; 
}

Status Pop(SqStack *S, SElemType *e){
  if(S->top == -1){ //栈空 
    return ERROR;
  }
  *e = S->data[S->top];
  S->top--;
  return OK;
}

//-------------队列
typedef int QElemType;
typedef struct{
  QElemType data[MAXSIZE];
  int front;
  int rear;
}SqQueue;
 
Status InitQueue(SqQueue *Q){
  Q->front = 0;
  Q->rear = 0;
  return OK;
}

int QueueLength(SqQueue Q){
  return (Q.rear - Q.front +MAXSIZE) % MAXSIZE;
}

Status EnQueue(SqQueue *Q, QElemType e){ //入队列 
  if((Q->rear + 1) % MAXSIZE == Q->front){ //队列满
    return ERROR; 
  }
  Q->data[Q->rear] = e;
  Q->rear = (Q->rear + 1) % MAXSIZE;
  return OK;
}

Status DeQueue(SqQueue *Q, QElemType *e){ //出队列 
  if(Q->front == Q->rear){
    return ERROR;
  }
  *e = Q->data[Q->front];
  Q->front = (Q->front + 1) % MAXSIZE;
  return OK;
}

test.cpp文件：

#include"DBFSAdjacencyMatrix.h"

int main(){
  GraphMatrix GM;
  printf("-------------------邻接矩阵的【创建】-------------------\n");
  CreateGraphMatrix(&GM);
  printf("\n-------------------邻接矩阵的【DFS】-------------------\n");
  DFSTraverse(GM);
  printf("\n-------------------邻接矩阵的【BFS】-------------------\n");
  BFSTraverse(GM); 
  
}

二、邻接表

包含四个文件的代码和一张测试效果图：

  • AdjacencyList.h文件： 构建邻接表的存储结构与邻接表的创建函数
  • DBFSAdjacencyList.h文件： 构建邻接表的深度优先遍历与广度优先遍历函数
  • StackAndQueue.h文件： 应广度优先遍历所需，提供队列的基本操作
  • test.cpp文件： 用于测试
  • 效果图：（如下）

效果图：


AdjacencyList.h文件：

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100
#define INFINITY 65535

typedef char VertexType;
typedef int EdgeType;

typedef struct EdgeNode{ //边表结点
  int adjvex; //邻接点域，存储该顶点对应的下标
  EdgeType weight; //权值
  struct EdgeNode *next;
}EdgeNode;

typedef struct VertexNode{ //顶点表结点 
  VertexType data; //顶点域，存储顶点信息
  EdgeNode *firstedge; //边表头指针 
}VertexNode, AdjList[MAXVEX];

typedef struct{
  AdjList adjList;
  int numVertexes, numEdges; //图中当前顶点数和边数 
}GraphAdjList;

void CreateALGraph(GraphAdjList *G){ //无向图的创建 
  int i, j, k;
  EdgeNode *e;
  printf("输入顶点数和边数：\n");
  scanf("%d%d", &G->numVertexes, &G->numEdges);
  getchar();
  for(i = 0; i < G->numVertexes; i++){
    scanf("%c", &G->adjList[i].data);
    G->adjList[i].firstedge = NULL;
  }
  
  for(k = 0; k < G->numEdges; k++){
    printf("输入边（vi，vj）上的下标i，下标j：\n");
    scanf("%d%d", &i, &j); //输入边（vi，vj）
    e = (EdgeNode *)malloc(sizeof(EdgeNode));
    e->adjvex = j;
    e->next = G->adjList[i].firstedge; //将e指针指向当前顶点指向的结点（头插法） 
    G->adjList[i].firstedge = e; 
    
    e = (EdgeNode *)malloc(sizeof(EdgeNode));
    e->adjvex = i;
    e->next = G->adjList[j].firstedge; //将e指针指向当前顶点指向的结点
    G->adjList[j].firstedge = e; 
  } 
}

DBFSAdjacencyList.h文件：

#include"AdjacencyList.h" 
#include"StackAndQueue.h"

#define MAX 100 
int visited[MAX];

void BFSTraverse(GraphAdjList GL){
  int i, j;
  EdgeNode *p;
  SqQueue Q;
  for(i = 0; i < GL.numVertexes; i++){ 
    visited[i] = FALSE;
  }
  InitQueue(&Q); //初始化一辅助用的队列
  for(i = 0; i < GL.numVertexes; i++){
    if(!visited[i]){
      visited[i] = TRUE; //设置当前顶点访问过
      printf("%c ", GL.adjList[i].data);
      EnQueue(&Q, i);
      while(QueueLength(Q) > 0){
        DeQueue(&Q, &i);
        p = GL.adjList[i].firstedge;
        while(p){
          if(!visited[p->adjvex]){
            visited[p->adjvex] = TRUE;
            printf("%c ", GL.adjList[p->adjvex].data);
            EnQueue(&Q, p->adjvex); 
          }
          p = p->next;
        }
      } 
    }
  } 
} 

void DFS(GraphAdjList GL, int i){
  EdgeNode *p;
  visited[i] = TRUE;
  printf("%c ", GL.adjList[i].data);
  p = GL.adjList[i].firstedge;
  while(p){
    if(!visited[p->adjvex]){
      DFS(GL, p->adjvex);
    }
    p = p->next;
  } 
} 

void DFSTraverse(GraphAdjList GL){
  int i;
  for(i = 0; i < GL.numVertexes; i++){
    visited[i] = FALSE;
  }
  for(i = 0; i < GL.numVertexes; i++){
    if(!visited[i]){
      DFS(GL, i);
    }
  }
}

StackAndQueue.h文件：（邻接矩阵的实现已给出此文件代码）

test.cpp文件：

#include"DBFSAdjacencyList.h"

int main(){
  GraphAdjList GL;
  printf("-------------------邻接表的【创建】-------------------\n");
  CreateALGraph(&GL);
  printf("\n-------------------邻接表的【DFS】-------------------\n");
  DFSTraverse(GL);
  printf("\n-------------------邻接表的【BFS】-------------------\n");
  BFSTraverse(GL); 
  
}


标签：遍历,int,邻接矩阵,C语言,++,numVertexes,visited,GM,GL
From： https://blog.51cto.com/u_15856491/5815038

相关文章

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99