图的常用表示方法就是矩阵和邻接表。
矩阵通常使用与规整的，且数据量较小的图，这种图直观上方便的表示出了图之间节点的相互关系。
图的数据结构
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 }
运行结果
本文转自博客园xingoo的博客，原文链接：矩阵图的深度广度遍历，如需转载请自行联系原博主。
