数据结构和算法-图的存储和遍历

图是一种较为复杂的数据结构，是顶点和边的集合。有两种存储方式：邻接矩阵和邻接表。图的遍历方法有深度优先遍历和广度优先遍历

一、邻接矩阵

样式图：
截屏2020-05-14下午6.25.33.png

1、图的结构

#define MAXVEX 100 /* 最大顶点数，应由用户定义 */

typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char VertexType; /* 顶点类型应由用户定义  */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

typedef struct{
 VertexType vexs[MAXVEX]; //顶点表
 EdgeType arc[MAXVEX][MAXVEX];  //邻接矩阵
 int numNodes, numEdges;
} MGraph;

2、创建和存储

void createMGraph(MGraph *G){
  int i,j,k,w;
  printf("输入顶点数和边数：\n");
  scanf("%d,%d",&G->numNodes,&G->numEdges);
  printf("顶点数:%d,边数:%d\n",G->numNodes,G->numEdges);
  //输入顶点信息
  printf("输入顶点信息：\n");
  for (i = 0; i <= G->numNodes; i++) {
      scanf("%c",&G->vexs[I]);
  }
  printf("\n");
  //初始化邻接矩阵
  for (i = 0 ; i < G->numNodes; i++) {
      for (j = 0; j < G->numNodes; j++) {
          G->arc[i][j] = 0;
      }
  }
  
  //输入边表信息
  for (k = 0; k < G->numEdges; k++) {
      printf("输入顶点i到顶点j的边的权值\n");
      scanf("%d,%d,%d",&i,&j,&w);
      
      G->arc[i][j] = w;
      G->arc[j][i] = G->arc[i][j];
  }
  //打印邻接矩阵
  for (i = 0; i < G->numNodes; i++) {
      printf("\n");
      for (j = 0; j < G->numNodes; j++) {
          printf("%d ",G->arc[i][j]);
      }
  }
  printf("\n");
}

二、邻接表

样式图：
截屏2020-05-14下午6.26.27.png

1、结构

#define M 100

typedef char Element;
typedef int BOOL;

//邻接表结点
typedef struct Node{
 int adj_vex_index;//顶点的下标
 Element data;
 struct Node *next; //下一个
}EdgeNode;

//顶点表结点
typedef struct vNode{
 Element data;
 EdgeNode *firstEdge;
}VexNode,AdjList[M];

//图的结构
typedef struct Craph{
 AdjList adjList; //顶点表
 int numNodes; //顶点个数
 int numEdges; //边的个数
 BOOL is_directed; //是否有向图
}Graph, *LinkGraph;

2、创建邻接表

void createLinkGraph(LinkGraph *G){
 int i, j ,k;
 EdgeNode *p;
 printf("输入顶点数目,边数和有向？：\n");
 scanf("%d,%d,%d",&(*G)->numNodes,&(*G)->numEdges,&(*G)->is_directed);
 
 printf("输入顶点信息：\n");
 for (i = 0; i<(*G)->numNodes; i++) {
     getchar();
     scanf("%c",&(*G)->adjList[i].data);
     (*G)->adjList[i].firstEdge = NULL;
 }
 
 printf("输入边信息：\n");
 for (k = 0; k<(*G)->numEdges; k++) {
     scanf("%d %d",&i,&j);
     //创建一个新的结点
     p = (EdgeNode *)malloc(sizeof(EdgeNode));
     //下标为j
     p->adj_vex_index = j;
     //头插法
     p->next = (*G)->adjList[i].firstEdge;
     (*G)->adjList[i].firstEdge = p;
     
     if (!(*G)->is_directed) {//无向图
         p = (EdgeNode *)malloc(sizeof(EdgeNode));
         p->adj_vex_index = I;
         p->next = (*G)->adjList[j].firstEdge;
         (*G)->adjList[j].firstEdge = p;
     }
 }
}

打印邻接表

void putGraph(LinkGraph G){
  printf("邻接表中存储信息:\n");
  for (int i = 0; i<G->numNodes; i++) {
      EdgeNode *p = G->adjList[i].firstEdge;
      while ℗ {
          printf("%c->%c ",G->adjList[i].data,G->adjList[p->adj_vex_index].data);
          p = p->next;
      }
      printf("\n");
  }
}

三、深度优先遍历

1、邻接矩阵的深度优先遍历

//DFS遍历
BOOL visited[MAXVEX]; //访问标志的数组

void DFS(MGraph G, int i){
 visited[i] = TRUE;
 printf("%c ",G.vexs[i]);
 for (int j = 0; j<G.numNodes; j++) {
     if (G.arc[i][j] == 1 && !visited[j]) {
         DFS(G, j);
     }
 }
}

void DFSTravese(MGraph G){
 //初始化visited数组
 for (int i = 0; i<G.numNodes; i++) {
     visited[i] = FALSE;
 }
 //从某个顶点开始遍历
 for (int i = 0; i<G.numNodes; i++) {
     if (!visited[i]) {
         DFS(G, i);
     }
 }
}

2、邻接表的深度优先遍历

BOOL visited[MAXVEX]; //访问标志的数组
void DFS(LinkGraph G, int i){
  EdgeNode *p;
  visited[i] = TRUE;
  //打印某顶点
  printf("%c ",G->adjList[i].data);
  p = G->adjList[i].firstEdge;
  while (p) {
      if (!visited[p->adj_vex_index]) {
          DFS(G, p->adj_vex_index);
      }
      p = p->next;
  }
}

void DFSTraverse(LinkGraph G){
  //初始化visited数组
  for (int i = 0; i<G->numNodes; i++) {
      visited[i] = FALSE;
  }
  
  for (int i = 0; i<G->numNodes; i++) {
      if (!visited[i]) {
          DFS(G, i);
      }
  }
  printf("\n");
}

四、广度优先遍历

1、广度优先遍历需要用到队列

#define MAXSIZE 10 /* 存储空间初始分配量 */

/* 循环队列的顺序存储结构 */
typedef struct
{
  int data[MAXSIZE];
  int front;        /* 头指针 */
  int rear;        /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
}Queue;

//初始化队列
Status initQueue(Queue *Q){
  Q->front = 0;
  Q->rear = 0;
  return OK;
}

//判断队列是否为空
Status queueIsEmpty(Queue Q){
  if (Q.front == Q.rear) {
      return TRUE;
  }else{
      return FALSE;
  }
}

//入队
Status enterQueue(Queue *Q, int e){
  if ((Q->rear+1)%MAXSIZE == Q->front) {
      return ERROR;
  }
  Q->data[Q->rear] = e;
  Q->rear = (Q->rear+1)%MAXSIZE;
  return OK;
}

//出队
Status deleteQueue(Queue *Q, int *e){
  if (queueIsEmpty(*Q)) {
      return ERROR;
  }
  *e = Q->data[Q->front];
  Q->front = (Q->front + 1)%MAXSIZE;
  return OK;
}

2、邻接矩阵的广度优先遍历

void BFSTraverse(MGraph G){
  //创建队列
  Queue Q;
  initQueue(&Q);
  //初始化标志数组
  for (int i = 0; i<G.numNodes; i++) {
      visited[i] = FALSE;
  }
  for (int i = 0; i<G.numNodes; i++) {
      if (!visited[i]) {
          visited[i] = TRUE;
          printf("%c ",G.vexs[i]);
          enterQueue(&Q, i);
          while (!queueIsEmpty(Q)) {
              int e;
              deleteQueue(&Q, &e);
              for (int j = 0; j<G.numNodes; j++) {
                  if (G.arc[e][j] == 1 && !visited[j]) {
                      visited[j] = TRUE;
                      printf("%c ",G.vexs[j]);
                      enterQueue(&Q, j);
                  }
              }
          }
      }
      
  }
  printf("\n");
}

3、邻接表的广度优先遍历

void BFSTraverse(LinkGraph G){
  //创建队列
  Queue Q;
  initQueue(&Q);
  //初始化标志数组
  for (int i = 0; i<G->numNodes; i++) {
      visited[i] = FALSE;
  }
  EdgeNode *p;
  for (int i = 0; i<G->numNodes; i++) {
      if (!visited[i]) {
          visited[i] = TRUE;
          printf("%c ",G->adjList[i].data);
          enterQueue(&Q, i);
          while (!queueIsEmpty(Q)) {
              int e;
              deleteQueue(&Q, &e);
              p = G->adjList[e].firstEdge;
              while (p) {
                  if (!visited[p->adj_vex_index]) {
                      visited[p->adj_vex_index] = TRUE;
                      printf("%c ",G->adjList[p->adj_vex_index].data);
                      enterQueue(&Q, p->adj_vex_index);
                  }
                  p = p->next;
              }
          }
      }
      
  }
  printf("\n");
}

邻接矩阵
邻接表

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 200,176评论 5赞 469
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 84,190评论 2赞 377
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 147,232评论 0赞 332
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 53,953评论 1赞 272
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 62,879评论 5赞 360
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,177评论 1赞 277
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,626评论 3赞 390
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,295评论 0赞 254
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,436评论 1赞 294
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,365评论 2赞 317
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,414评论 1赞 329
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,096评论 3赞 315
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,685评论 3赞 303
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,771评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 30,987评论 1赞 255
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 42,438评论 2赞 346
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,032评论 2赞 341