使用 C 的 DSA - 图形

概述

图形是一种用于对数学图形进行建模的数据结构。它由一组称为顶点边的连接对组成。我们可以使用顶点数组和边的二维数组来表示图形。

重要术语

顶点 − 图形的每个节点都表示为一个顶点。在下面给出的示例中，带标签的圆圈表示顶点。因此 A 到 G 是顶点。我们可以使用数组来表示它们，如下图所示。这里 A 可以通过索引 0 来标识。B 可以使用索引 1 来标识，依此类推。
边 − 边表示两个顶点之间的路径或两个顶点之间的线。在下面给出的例子中，从 A 到 B、从 B 到 C 等的线表示边。我们可以使用二维数组来表示数组，如下图所示。这里 AB 可以表示为第 0 行第 1 列的 1，BC 可以表示为第 1 行第 2 列的 1，依此类推，其他组合保持为 0。
相邻 − 如果两个节点或顶点通过边相互连接，则它们是相邻的。在下面给出的例子中，B 与 A 相邻，C 与 B 相邻，依此类推。
路径 − 路径表示两个顶点之间的一系列边。在下面给出的示例中，ABCD 表示从 A 到 D 的路径。

基本操作

以下是图形的基本主要操作。

添加顶点 − 向图形添加顶点。
添加边 − 在图的两个顶点之间添加边。
显示顶点 − 显示图形的顶点。

添加顶点操作

//add vertex to the vertex list
void addVertex(char label){
struct vertex* vertex = 
   (struct vertex*) malloc(sizeof(struct vertex));
   vertex->label = label;  
   vertex->visited = false;     
   lstVertices[vertexCount++] = vertex;
}

Add Edge Operation

//add edge to edge array
void addEdge(int start,int end){
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
}

Display Edge Operation

//display the vertex
void displayVertex(int vertexIndex){
   printf("%c ",lstVertices[vertexIndex]->label);
}

遍历算法

以下是图上的重要遍历算法。

深度优先搜索 − 以深度方向遍历图。
广度优先搜索 −以宽度方向遍历图形。

深度优先搜索算法

深度优先搜索算法 (DFS) 以深度方向遍历图形，并使用堆栈记住在任何迭代中出现死胡同时获取下一个顶点以开始搜索。

如上例所示，DFS 算法首先从 A 到 B 到 C 到 D，然后到 E，然后到 F，最后到 G。它采用以下规则。

规则 1 − 访问相邻的未访问顶点。将其标记为已访问。显示它。将其推入堆栈。
规则 2 −如果未找到相邻顶点，则从堆栈中弹出一个顶点。（它将从堆栈中弹出所有没有相邻顶点的顶点。）
规则 3 − 重复规则 1 和规则 2，直到堆栈为空。

void depthFirstSearch(){
   int i;
   //将第一个节点标记为已访问
   lstVertices[0]->visited = true;
   
   //display the vertex
   displayVertex(0);   
   
   //push vertex index in stack
   push(0);

   while(!isStackEmpty()){
      //get the unvisited vertex of vertex which is at top of the stack
      int unvisitedVertex = getAdjUnvisitedVertex(peek());
      
      //没有找到相邻顶点
      if(unvisitedVertex == -1){
         pop();
      } else {
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         push(unvisitedVertex);
      }
   }
   //stack is empty, search is complete, reset the visited flag        
   for(i=0;i < vertexCount;i++){
      lstVertices[i]->visited = false;
   }        
}

广度优先搜索算法

广度优先搜索算法 (BFS) 以广度运动遍历图形，并使用队列记住在任何迭代中出现死胡同时获取下一个顶点以开始搜索。

如上例所示，BFS 算法首先从 A 到 B 到 E 到 F，然后到 C 和 G，最后到 D。它采用以下规则。

规则 1 − 访问相邻的未访问顶点。将其标记为已访问。显示它。将其插入队列中。
规则 2 −如果未找到相邻顶点，则从队列中删除第一个顶点。
规则 3 − 重复规则 1 和规则 2，直到队列为空。

void breadthFirstSearch(){
   int i;
   //将第一个节点标记为已访问
   lstVertices[0]->visited = true;
   
   //display the vertex
   displayVertex(0);   
   
   //将顶点索引插入队列
   insert(0);
   int unvisitedVertex;
   while(!isQueueEmpty()){
      //获取队列最前面的未访问顶点
      int tempVertex = removeData();         
      
      //没有找到相邻顶点
      while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){    
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         insert(unvisitedVertex);               
      }
   } 
   //队列为空，搜索完成，重置访问标志        
   for(i=0;i<vertexCount;i++){
      lstVertices[i]->visited = false;
   }    
}

示例

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 10

struct Vertex {
   char label;
   bool visited;
};

//堆栈变量
int stack[MAX]; 
int top=-1; 

//队列变量
int queue[MAX];
int rear=-1;
int front=0;
int queueItemCount = 0;

//图形变量
//顶点数组
struct Vertex* lstVertices[MAX];

//邻接矩阵
int adjMatrix[MAX][MAX];

//顶点数
int vertexCount = 0;

//堆栈函数
void push(int item) { 
   stack[++top]=item; 
}
int pop() { 
   return stack[top--]; 
} 
int peek() {         
   return stack[top];
}
bool isStackEmpty(){
   return top == -1;
}
//队列函数
void insert(int data){
   queue[++rear] = data;
   queueItemCount++;
}
int removeData(){
   queueItemCount--;
   return queue[front++]; 
}
bool isQueueEmpty(){
   return queueItemCount == 0;
}
//图形函数
//将顶点添加到顶点列表
void addVertex(char label){
   struct Vertex* vertex = (struct Vertex*) malloc(sizeof(struct Vertex));
   vertex->label = label;  
   vertex->visited = false;     
   lstVertices[vertexCount++] = vertex;
}
//将边添加到边数组
void addEdge(int start,int end){
   adjMatrix[start][end] = 1;
   adjMatrix[end][start] = 1;
}
//display the vertex
void displayVertex(int vertexIndex){
   printf("%c ",lstVertices[vertexIndex]->label);
}
//get the adjacent unvisited vertex
int getAdjUnvisitedVertex(int vertexIndex){
   int i;
   for(i=0; i<vertexCount; i++)
      if(adjMatrix[vertexIndex][i]==1 && lstVertices[i]->visited==false)
         return i;
   return -1;
}
void depthFirstSearch(){
   int i;
   //将第一个节点标记为已访问
   lstVertices[0]->visited = true;
   
   //display the vertex
   displayVertex(0);   
   
   //push vertex index in stack
   push(0);

   while(!isStackEmpty()){
      //get the unvisited vertex of vertex which is at top of the stack
      int unvisitedVertex = getAdjUnvisitedVertex(peek());
      
      //没有找到相邻顶点
      if(unvisitedVertex == -1){
         pop();
      } else {
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         push(unvisitedVertex);
      }
   }
   //stack is empty, search is complete, reset the visited flag        
   for(i=0;i < vertexCount;i++){
      lstVertices[i]->visited = false;
   }        
}
void breadthFirstSearch(){
   int i;
   //将第一个节点标记为已访问
   lstVertices[0]->visited = true;
   
   //display the vertex
   displayVertex(0);   
   
   //将顶点索引插入队列
   insert(0);
   int unvisitedVertex;
   while(!isQueueEmpty()){
      //获取队列最前面的未访问顶点
      int tempVertex = removeData();         
      
      //没有找到相邻顶点
      while((unvisitedVertex=getAdjUnvisitedVertex(tempVertex)) != -1){    
         lstVertices[unvisitedVertex]->visited = true;
         displayVertex(unvisitedVertex);
         insert(unvisitedVertex);               
      }
   }
   //队列为空，搜索完成，重置访问标志        
   for(i=0;i<vertexCount;i++){
      lstVertices[i]->visited = false;
   }    
}
main() {
   int i, j;
   
   for(i=0; i<MAX; i++) // set adjacency
      for(j=0; j<MAX; j++) // matrix to 0
         adjMatrix[i][j] = 0;

   addVertex('A');   //0
   addVertex('B');   //1
   addVertex('C');   //2
   addVertex('D');   //3
   addVertex('E');   //4
   addVertex('F');   //5
   addVertex('G');   //6

   /*      1  2  3   
   * 0  |--B--C--D
   * A--|
   * |
   * |     4 
   * |-----E
   * |     5  6
   * |  |--F--G
   * |--| 
   */        
   addEdge(0, 1);   //AB
   addEdge(1, 2);   //BC
   addEdge(2, 3);   //CD
   addEdge(0, 4);   //AC
   addEdge(0, 5);   //AF
   addEdge(5, 6);   //FG
   printf("Depth First Search: ");
   
   //A B C D E F G
   depthFirstSearch();              
   printf("
Breadth First Search: ");
   
   //A B E F C G D
   breadthFirstSearch();
}

如果我们编译并运行上述程序，则会产生以下结果 −

Depth First Search: A B C D E F G 
Breadth First Search: A B E F C G D

使用 C 的 DSA 教程

使用 C 的 DSA 有用资源

使用 C 的 DSA - 图形

概述

基本操作

添加顶点操作

Add Edge Operation

Display Edge Operation

遍历算法

深度优先搜索算法

广度优先搜索算法

示例

颜色选择器

读后有收获微信请站长喝咖啡

错误报告

您的建议:

感谢您的帮助！