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

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

一、邻接矩阵

样式图：

截屏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");
}

邻接矩阵
 邻接表