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