【数据结构】图的邻接矩阵储存和广度、深度优先遍历

【数据结构】图的邻接矩阵存储和广度、深度优先遍历

示例：建立如图所示的无向图

由上图知，该图有5个顶点，分别为a,b,c,d,e,有6条边.示例输入（按照这个格式输入）：56abcde0 1 10 2 10 3 12 3 12 4 11 4 1输入结束（此行不必输入）注：0 1 1表示该图的第0个顶点和第1个定点有边相连，如上图中的a->b所示      0 2 1表示该图的第0个顶点和第2个定点有边相连，如上图中的a->c所示      2 3 1表示该图的第2个顶点和第3个定点有边相连，如上图中的c->d所示

#include <stdio.h>#define MAX_GRAPH 100#define MAX_QUEUE 30typedef struct{char vex[MAX_GRAPH]; /* 顶点 */ int edge[MAX_GRAPH][MAX_GRAPH]; /* 邻接矩阵 */int n; /* 当前的顶点数 */int e; /* 当前的边数 */}GRAPH;void Create(GRAPH *G); /* 图的邻接矩阵表示法 */void BFS(GRAPH *G,int k); /* 广度优先遍历 */ void DFS(GRAPH *G,int k); /*  深度优先遍历 */int visited[MAX_GRAPH];int main(int argc, char *argv[]){int i;for(i = 0 ; i < MAX_QUEUE ; ++i)visited[i] = 0;GRAPH G;Create(&G); /*BFS(&G,0);*/DFS(&G,0);return 0;}void BFS(GRAPH *G,int k){int queue[MAX_QUEUE]; /* 队列 */int front = -1,rear = -1,amount = 0;int visited[MAX_GRAPH]; /* 标记已经访问过的元素 */int i,j;for(i = 0 ; i < MAX_GRAPH ; ++i)visited[i] = 0;printf("访问顶点%c\n",G->vex[k]);visited[k] = 1;rear = (rear + 1) % MAX_QUEUE; /* 入队操作 */queue[rear] = k;front = rear;++amount;while(amount > 0){i = queue[front]; /* 出队操作 */front = (front + 1) % MAX_QUEUE;--amount;for(j = 0 ; j < G->n ; ++j){if(G->edge[i][j] != 0 && visited[j] == 0){printf("访问顶点%c\n",G->vex[j]);visited[j] = 1;rear = (rear + 1) % MAX_QUEUE; /* 入队 */queue[rear] = j;++amount;}}}printf("遍历结束\n");}void DFS(GRAPH *G,int k){int j;printf("访问顶点：%c\n",G->vex[k]);visited[k] = 1;for(j = 0 ; j < G->n ; ++j){if(G->edge[k][j] != 0 && visited[j] == 0)DFS(G,j);}}void Create(GRAPH *G){printf("输入顶点数：\n");scanf("%d",&G->n);printf("输入边数：\n");scanf("%d",&G->e);getchar();int i,j,k,w;printf("请输入端点(char型)：\n");for(i = 0 ; i < G->n ; ++i) /* 建立表头 */scanf("%c",&G->vex[i]);for(i = 0 ; i < G->n ; ++i) /* 初始化邻接矩阵 */for(j = 0 ; j < G->n ; ++j)G->edge[i][j] = 0;printf("请输入边：\n");for(k = 0 ; k < G->e ; ++k){scanf("%d%d%d",&i,&j,&w); /* 输入(vi,vj)上的权w */G->edge[i][j] = w;G->edge[j][i] = w;}}

查看更多 下一篇