|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
邻接矩阵(无向图)
- /**
- * C: 邻接矩阵图表示的"无向图(Matrix Undirected Graph)"
- *
- * @author skywang
- * @date 2014/04/18
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <malloc.h>
- #include <string.h>
- #define MAX 100
- #define isLetter(a) ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
- #define LENGTH(a) (sizeof(a)/sizeof(a[0]))
- // 邻接矩阵
- typedef struct _graph
- {
- char vexs[MAX]; // 顶点集合
- int vexnum; // 顶点数
- int edgnum; // 边数
- int matrix[MAX][MAX]; // 邻接矩阵
- }Graph, *PGraph;
- /*
- * 返回ch在matrix矩阵中的位置
- */
- static int get_position(Graph g, char ch)
- {
- int i;
- for(i=0; i<g.vexnum; i++)
- if(g.vexs[i]==ch)
- return i;
- return -1;
- }
- /*
- * 读取一个输入字符
- */
- static char read_char()
- {
- char ch;
- do {
- ch = getchar();
- } while(!isLetter(ch));
- return ch;
- }
- /*
- * 创建图(自己输入)
- */
- Graph* create_graph()
- {
- char c1, c2;
- int v, e;
- int i, p1, p2;
- Graph* pG;
-
- // 输入"顶点数"和"边数"
- printf("input vertex number: ");
- scanf("%d", &v);
- printf("input edge number: ");
- scanf("%d", &e);
- if ( v < 1 || e < 1 || (e > (v * (v-1))))
- {
- printf("input error: invalid parameters!\n");
- return NULL;
- }
-
- if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
- return NULL;
- memset(pG, 0, sizeof(Graph));
- // 初始化"顶点数"和"边数"
- pG->vexnum = v;
- pG->edgnum = e;
- // 初始化"顶点"
- for (i = 0; i < pG->vexnum; i++)
- {
- printf("vertex(%d): ", i);
- pG->vexs[i] = read_char();
- }
- // 初始化"边"
- for (i = 0; i < pG->edgnum; i++)
- {
- // 读取边的起始顶点和结束顶点
- printf("edge(%d):", i);
- c1 = read_char();
- c2 = read_char();
- p1 = get_position(*pG, c1);
- p2 = get_position(*pG, c2);
- if (p1==-1 || p2==-1)
- {
- printf("input error: invalid edge!\n");
- free(pG);
- return NULL;
- }
- pG->matrix[p1][p2] = 1;
- pG->matrix[p2][p1] = 1;
- }
- return pG;
- }
- /*
- * 创建图(用已提供的矩阵)
- */
- Graph* create_example_graph()
- {
- char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
- char edges[][2] = {
- {'A', 'C'},
- {'A', 'D'},
- {'A', 'F'},
- {'B', 'C'},
- {'C', 'D'},
- {'E', 'G'},
- {'F', 'G'}};
- int vlen = LENGTH(vexs);
- int elen = LENGTH(edges);
- int i, p1, p2;
- Graph* pG;
-
- // 输入"顶点数"和"边数"
- if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
- return NULL;
- memset(pG, 0, sizeof(Graph));
- // 初始化"顶点数"和"边数"
- pG->vexnum = vlen;
- pG->edgnum = elen;
- // 初始化"顶点"
- for (i = 0; i < pG->vexnum; i++)
- {
- pG->vexs[i] = vexs[i];
- }
- // 初始化"边"
- for (i = 0; i < pG->edgnum; i++)
- {
- // 读取边的起始顶点和结束顶点
- p1 = get_position(*pG, edges[i][0]);
- p2 = get_position(*pG, edges[i][1]);
- pG->matrix[p1][p2] = 1;
- pG->matrix[p2][p1] = 1;
- }
- return pG;
- }
- /*
- * 返回顶点v的第一个邻接顶点的索引,失败则返回-1
- */
- static int first_vertex(Graph G, int v)
- {
- int i;
- if (v<0 || v>(G.vexnum-1))
- return -1;
- for (i = 0; i < G.vexnum; i++)
- if (G.matrix[v][i] == 1)
- return i;
- return -1;
- }
- /*
- * 返回顶点v相对于w的下一个邻接顶点的索引,失败则返回-1
- */
- static int next_vertix(Graph G, int v, int w)
- {
- int i;
- if (v<0 || v>(G.vexnum-1) || w<0 || w>(G.vexnum-1))
- return -1;
- for (i = w + 1; i < G.vexnum; i++)
- if (G.matrix[v][i] == 1)
- return i;
- return -1;
- }
- /*
- * 深度优先搜索遍历图的递归实现
- */
- static void DFS(Graph G, int i, int *visited)
- {
- int w;
- visited[i] = 1;
- printf("%c ", G.vexs[i]);
- // 遍历该顶点的所有邻接顶点。若是没有访问过,那么继续往下走
- for (w = first_vertex(G, i); w >= 0; w = next_vertix(G, i, w))
- {
- if (!visited[w])
- DFS(G, w, visited);
- }
-
- }
- /*
- * 深度优先搜索遍历图
- */
- void DFSTraverse(Graph G)
- {
- int i;
- int visited[MAX]; // 顶点访问标记
- // 初始化所有顶点都没有被访问
- for (i = 0; i < G.vexnum; i++)
- visited[i] = 0;
- printf("DFS: ");
- for (i = 0; i < G.vexnum; i++)
- {
- //printf("\n== LOOP(%d)\n", i);
- if (!visited[i])
- DFS(G, i, visited);
- }
- printf("\n");
- }
- /*
- * 广度优先搜索(类似于树的层次遍历)
- */
- void BFS(Graph G)
- {
- int head = 0;
- int rear = 0;
- int queue[MAX]; // 辅组队列
- int visited[MAX]; // 顶点访问标记
- int i, j, k;
- for (i = 0; i < G.vexnum; i++)
- visited[i] = 0;
- printf("BFS: ");
- for (i = 0; i < G.vexnum; i++)
- {
- if (!visited[i])
- {
- visited[i] = 1;
- printf("%c ", G.vexs[i]);
- queue[rear++] = i; // 入队列
- }
- while (head != rear)
- {
- j = queue[head++]; // 出队列
- for (k = first_vertex(G, j); k >= 0; k = next_vertix(G, j, k)) //k是为访问的邻接顶点
- {
- if (!visited[k])
- {
- visited[k] = 1;
- printf("%c ", G.vexs[k]);
- queue[rear++] = k;
- }
- }
- }
- }
- printf("\n");
- }
- /*
- * 打印矩阵队列图
- */
- void print_graph(Graph G)
- {
- int i,j;
- printf("Martix Graph:\n");
- for (i = 0; i < G.vexnum; i++)
- {
- for (j = 0; j < G.vexnum; j++)
- printf("%d ", G.matrix[i][j]);
- printf("\n");
- }
- }
- void main()
- {
- Graph* pG;
- // 自定义"图"(输入矩阵队列)
- //pG = create_graph();
- // 采用已有的"图"
- pG = create_example_graph();
- print_graph(*pG); // 打印图
- DFSTraverse(*pG); // 深度优先遍历
- BFS(*pG); // 广度优先遍历
- }
复制代码
邻接矩阵(有向图)
- /**
- * C: 邻接矩阵表示的"有向图(Matrix Directed Graph)"
- *
- * @author skywang
- * @date 2014/04/18
- */
- #include <stdio.h>
- #include <stdlib.h>
- #include <malloc.h>
- #include <string.h>
- #define MAX 100
- #define isLetter(a) ((((a)>='a')&&((a)<='z')) || (((a)>='A')&&((a)<='Z')))
- #define LENGTH(a) (sizeof(a)/sizeof(a[0]))
- // 邻接矩阵
- typedef struct _graph
- {
- char vexs[MAX]; // 顶点集合
- int vexnum; // 顶点数
- int edgnum; // 边数
- int matrix[MAX][MAX]; // 邻接矩阵
- }Graph, *PGraph;
- /*
- * 返回ch在matrix矩阵中的位置
- */
- static int get_position(Graph g, char ch)
- {
- int i;
- for(i=0; i<g.vexnum; i++)
- if(g.vexs[i]==ch)
- return i;
- return -1;
- }
- /*
- * 读取一个输入字符
- */
- static char read_char()
- {
- char ch;
- do {
- ch = getchar();
- } while(!isLetter(ch));
- return ch;
- }
- /*
- * 创建图(自己输入)
- */
- Graph* create_graph()
- {
- char c1, c2;
- int v, e;
- int i, p1, p2;
- Graph* pG;
-
- // 输入"顶点数"和"边数"
- printf("input vertex number: ");
- scanf("%d", &v);
- printf("input edge number: ");
- scanf("%d", &e);
- if ( v < 1 || e < 1 || (e > (v * (v-1))))
- {
- printf("input error: invalid parameters!\n");
- return NULL;
- }
-
- if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
- return NULL;
- memset(pG, 0, sizeof(Graph));
- // 初始化"顶点数"和"边数"
- pG->vexnum = v;
- pG->edgnum = e;
- // 初始化"顶点"
- for (i = 0; i < pG->vexnum; i++)
- {
- printf("vertex(%d): ", i);
- pG->vexs[i] = read_char();
- }
- // 初始化"边"
- for (i = 0; i < pG->edgnum; i++)
- {
- // 读取边的起始顶点和结束顶点
- printf("edge(%d):", i);
- c1 = read_char();
- c2 = read_char();
- p1 = get_position(*pG, c1);
- p2 = get_position(*pG, c2);
- if (p1==-1 || p2==-1)
- {
- printf("input error: invalid edge!\n");
- free(pG);
- return NULL;
- }
- pG->matrix[p1][p2] = 1;
- }
- return pG;
- }
- /*
- * 创建图(用已提供的矩阵)
- */
- Graph* create_example_graph()
- {
- char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
- char edges[][2] = {
- {'A', 'B'},
- {'B', 'C'},
- {'B', 'E'},
- {'B', 'F'},
- {'C', 'E'},
- {'D', 'C'},
- {'E', 'B'},
- {'E', 'D'},
- {'F', 'G'}};
- int vlen = LENGTH(vexs);
- int elen = LENGTH(edges);
- int i, p1, p2;
- Graph* pG;
-
- // 输入"顶点数"和"边数"
- if ((pG=(Graph*)malloc(sizeof(Graph))) == NULL )
- return NULL;
- memset(pG, 0, sizeof(Graph));
- // 初始化"顶点数"和"边数"
- pG->vexnum = vlen;
- pG->edgnum = elen;
- // 初始化"顶点"
- for (i = 0; i < pG->vexnum; i++)
- {
- pG->vexs[i] = vexs[i];
- }
- // 初始化"边"
- for (i = 0; i < pG->edgnum; i++)
- {
- // 读取边的起始顶点和结束顶点
- p1 = get_position(*pG, edges[i][0]);
- p2 = get_position(*pG, edges[i][1]);
- pG->matrix[p1][p2] = 1;
- }
- return pG;
- }
- /*
- * 返回顶点v的第一个邻接顶点的索引,失败则返回-1
- */
- static int first_vertex(Graph G, int v)
- {
- int i;
- if (v<0 || v>(G.vexnum-1))
- return -1;
- for (i = 0; i < G.vexnum; i++)
- if (G.matrix[v][i] == 1)
- return i;
- return -1;
- }
- /*
- * 返回顶点v相对于w的下一个邻接顶点的索引,失败则返回-1
- */
- static int next_vertix(Graph G, int v, int w)
- {
- int i;
- if (v<0 || v>(G.vexnum-1) || w<0 || w>(G.vexnum-1))
- return -1;
- for (i = w + 1; i < G.vexnum; i++)
- if (G.matrix[v][i] == 1)
- return i;
- return -1;
- }
- /*
- * 深度优先搜索遍历图的递归实现
- */
- static void DFS(Graph G, int i, int *visited)
- {
- int w;
- visited[i] = 1;
- printf("%c ", G.vexs[i]);
- // 遍历该顶点的所有邻接顶点。若是没有访问过,那么继续往下走
- for (w = first_vertex(G, i); w >= 0; w = next_vertix(G, i, w))
- {
- if (!visited[w])
- DFS(G, w, visited);
- }
-
- }
- /*
- * 深度优先搜索遍历图
- */
- void DFSTraverse(Graph G)
- {
- int i;
- int visited[MAX]; // 顶点访问标记
- // 初始化所有顶点都没有被访问
- for (i = 0; i < G.vexnum; i++)
- visited[i] = 0;
- printf("DFS: ");
- for (i = 0; i < G.vexnum; i++)
- {
- //printf("\n== LOOP(%d)\n", i);
- if (!visited[i])
- DFS(G, i, visited);
- }
- printf("\n");
- }
- /*
- * 广度优先搜索(类似于树的层次遍历)
- */
- void BFS(Graph G)
- {
- int head = 0;
- int rear = 0;
- int queue[MAX]; // 辅组队列
- int visited[MAX]; // 顶点访问标记
- int i, j, k;
- for (i = 0; i < G.vexnum; i++)
- visited[i] = 0;
- printf("BFS: ");
- for (i = 0; i < G.vexnum; i++)
- {
- if (!visited[i])
- {
- visited[i] = 1;
- printf("%c ", G.vexs[i]);
- queue[rear++] = i; // 入队列
- }
- while (head != rear)
- {
- j = queue[head++]; // 出队列
- for (k = first_vertex(G, j); k >= 0; k = next_vertix(G, j, k)) //k是为访问的邻接顶点
- {
- if (!visited[k])
- {
- visited[k] = 1;
- printf("%c ", G.vexs[k]);
- queue[rear++] = k;
- }
- }
- }
- }
- printf("\n");
- }
- /*
- * 打印矩阵队列图
- */
- void print_graph(Graph G)
- {
- int i,j;
- printf("Martix Graph:\n");
- for (i = 0; i < G.vexnum; i++)
- {
- for (j = 0; j < G.vexnum; j++)
- printf("%d ", G.matrix[i][j]);
- printf("\n");
- }
- }
- void main()
- {
- Graph* pG;
- // 自定义"图"(输入矩阵队列)
- //pG = create_graph();
- // 采用已有的"图"
- pG = create_example_graph();
- print_graph(*pG); // 打印图
- DFSTraverse(*pG); // 深度优先遍历
- BFS(*pG); // 广度优先遍历
- }
复制代码
|
|