矩阵图的深度广度遍历

2023-12-20 08:44:52

图的常用表示方法就是矩阵和邻接表。

矩阵通常使用与规整的，且数据量较小的图，这种图直观上方便的表示出了图之间节点的相互关系。

图的数据结构

typedef struct Graph_Matrix{
    char vers[NUM]; //存储数据表示
    int arc[NUM][NUM];//二维矩阵图，用来表示节点相连情况
    int numVer,numEdge;//顶点数，和边数
}Graph_Matrix;

矩阵图的深度优先遍历

为了防止图中有不连通的子图，因此每个节点顺序的遍历一次，每次采用深度优先遍历其联通子图，避免了遗漏节点。

有点类似书中遍历玩父节点，直接遍历他的左边孩子，然后再回来....

int DFS(Graph_Matrix *g,int i){
    int j;
    visited[i] = 1;
    printf("%c ",g->vers[i]);
    for(j=0;j<g->numVer;j++){
        if(g->arc[i][j] == 1 && !visited[j])
            DFS(g,j);
    }
}
void DFSTraverse(Graph_Matrix *g){
    int i;
    for(i=0;i<g->numVer;i++)
        visited[i] = 0;
    for(i=0;i<g->numVer;i++){
        if(!visited[i])
            DFS(g,i);
    }
}

矩阵图的广度优先遍历

广度优先遍历，主要依赖于一个队列，每次遍历一个父节点，寻找他的子节点一次放入队列中，遍历完，读取队列中的队头，在此读取其子节点，有点类似树中遍历父节点后，在遍历他的孩子节点。

void BFSTraverse(Graph_Matrix *g){
    int i,j;
    Queue *q = (Queue *)malloc(sizeof(Queue));
    for(i=0;i<g->numVer;i++)
        visited[i] = 0;
    initQueue(q,0);
    for(i=0;i<g->numVer;i++){
        if(!visited[i]){
            visited[i] = 1;
            printf("%c ",g->vers[i]);
            inQueue(q,i);
            while(getLength(q)){
                int *tar = (int *)malloc(sizeof(int));
                outQueue(q,tar);
                for(j=0;j<g->numVer;j++){
                    if(g->arc[*tar][j] == 1 &&  !visited[j]){
                        visited[j] = 1;
                        printf("%c ",g->vers[j]);
                        inQueue(q,j);
                    }
                }
            }
        }
    }
}

示例图

示例代码

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #define NUM 5
  4 #define MAXSIZE NUM
  5 typedef struct Graph_Matrix{
  6     char vers[NUM];
  7     int arc[NUM][NUM];
  8     int numVer,numEdge;
  9 }Graph_Matrix;
 10 
 11 typedef struct Queue{
 12     int data[NUM];
 13     int front;
 14     int rear;
 15 }Queue;
 16 
 17 void initQueue(Queue *q,int n);
 18 void showQueue(Queue *q);
 19 int getLength(Queue *q);
 20 int inQueue(Queue *q,int num);
 21 int outQueue(Queue *q,int *tar);
 22 
 23 void createGraph(Graph_Matrix *g);
 24 void showGraph(Graph_Matrix *g);
 25 int visited[NUM];
 26 int DFS(Graph_Matrix *g,int i);
 27 void DFSTraverse(Graph_Matrix *g);
 28 void BFSTraverse(Graph_Matrix *g);
 29 
 30 int main()
 31 {
 32     Graph_Matrix * g1 = (Graph_Matrix *)malloc(sizeof(Graph_Matrix));
 33     createGraph(g1);
 34     showGraph(g1);
 35     printf("\n");
 36     DFSTraverse(g1);
 37     printf("\n");
 38     BFSTraverse(g1);
 39     return 0;
 40 }
 41 
 42 void createGraph(Graph_Matrix *g){
 43     int i;
 44     int j;
 45     g->numEdge = 0;
 46     for(i=0;i<NUM;i++){
 47         g->vers[i] = 65+i;
 48     }
 49     for(i=0;i<NUM;i++){
 50         for(j=0;j<NUM;j++){
 51             if(i != j){
 52                 g->arc[i][j] = 1;
 53                 g->numEdge++;
 54             }
 55             else
 56                 g->arc[i][j] = 0;
 57         }
 58     }
 59     g->arc[2][3] = g->arc[3][2] = 0;
 60     g->arc[1][2] = g->arc[2][1] = 0;
 61     g->numEdge -= 4;
 62     g->numEdge = g->numEdge/2;
 63     g->numVer = 5;
 64 }
 65 void showGraph(Graph_Matrix *g){
 66     int i,j;
 67     for(i=0;i<g->numVer;i++){
 68         printf("%c ",g->vers[i]);
 69     }
 70     printf("\n");
 71 
 72     for(i=0;i<g->numVer;i++){
 73         for(j=0;j<g->numVer;j++){
 74             printf("%d ",g->arc[i][j]);
 75         }
 76         printf("\n");
 77     }
 78     printf("vertexes:%d edges:%d",g->numVer,g->numEdge);
 79 }
 80 
 81 int DFS(Graph_Matrix *g,int i){
 82     int j;
 83     visited[i] = 1;
 84     printf("%c ",g->vers[i]);
 85     for(j=0;j<g->numVer;j++){
 86         if(g->arc[i][j] == 1 && !visited[j])
 87             DFS(g,j);
 88     }
 89 }
 90 void DFSTraverse(Graph_Matrix *g){
 91     int i;
 92     for(i=0;i<g->numVer;i++)
 93         visited[i] = 0;
 94     for(i=0;i<g->numVer;i++){
 95         if(!visited[i]) //如果是连通图，只会执行一次
 96             DFS(g,i);
 97     }
 98 }
 99 
100 void BFSTraverse(Graph_Matrix *g){
101     int i,j;
102     Queue *q = (Queue *)malloc(sizeof(Queue));
103     for(i=0;i<g->numVer;i++)
104         visited[i] = 0;
105     initQueue(q,0);
106     for(i=0;i<g->numVer;i++){
107         if(!visited[i]){
108             visited[i] = 1;
109             printf("%c ",g->vers[i]);
110             inQueue(q,i);
111             while(getLength(q)){
112                 int *tar = (int *)malloc(sizeof(int));
113                 outQueue(q,tar);
114                 for(j=0;j<g->numVer;j++){
115                     if(g->arc[*tar][j] == 1 &&  !visited[j]){
116                         visited[j] = 1;
117                         printf("%c ",g->vers[j]);
118                         inQueue(q,j);
119                     }
120                 }
121             }
122         }
123     }
124 }
125 
126 void initQueue(Queue *q,int n){
127     int i;
128     q->front=0;
129     q->rear =0;
130     for(i=0;i<n;i++){
131         q->data[q->rear]=2*i+1;
132         q->rear++;
133     }
134 }
135 void showQueue(Queue *q){
136     int i;
137     int len=getLength(q);
138     printf("front-");
139     for(i=0;i<len;i++){
140         if(q->front+i<MAXSIZE)
141             printf("%d-",q->data[q->front+i]);
142         else
143             printf("%d-",q->data[q->front+i-MAXSIZE]);
144     }
145     printf("rear\n");
146 }
147 int getLength(Queue *q){
148     return (q->rear-q->front+MAXSIZE)%MAXSIZE;
149 }
150 int inQueue(Queue *q,int num){
151     if((q->rear+1)%MAXSIZE == q->front)
152         return 0;
153     q->data[q->rear] = num;
154     q->rear = (q->rear+1)%MAXSIZE;
155     return 1;
156 }
157 int outQueue(Queue *q,int *tar){
158     if(q->front == q->rear)
159         return 0;
160     *tar = q->data[q->front];
161     q->front = (q->front+1)%MAXSIZE;
162     return 1;
163 }

View Code

运行结果