矩阵图的深度广度遍历-白红宇

矩阵图的深度广度遍历

阅读量：6334 次

发布时间：2019-06-22

本文共 5136 字，大约阅读时间需要 17 分钟。

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

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

图的数据结构

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

示例图

示例代码

1 #include 
      
         2 #include 
       
          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
        
         vers[i] = 65+i; 48     } 49     for(i=0;i
         
          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
          
           numVer;i++){ 68         printf("%c ",g->vers[i]); 69     } 70     printf("\n"); 71  72     for(i=0;i
           
            numVer;i++){ 73 for(j=0;j
            
             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
             
              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
              
               numVer;i++) 93 visited[i] = 0; 94 for(i=0;i
               
                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
                
                 numVer;i++)104 visited[i] = 0;105 initQueue(q,0);106 for(i=0;i
                 
                  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
                  
                   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
                   
                    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
                    
                     front+i
                     
                      data[q->front+i]);142 else143 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

运行结果

转载于:https://my.oschina.net/u/204616/blog/545142

你可能感兴趣的文章