数据结构 |
您所在的位置：网站首页 › 16570r13是什么意思用图给我 › 数据结构 |
数据结构
|
邻接矩阵法
用一维数组图中顶点的信息，用一个二维数组存储图中边的信息（各顶点之间的邻接关系）。存储顶点之间邻接关系的二维数组称为邻接矩阵。 结点数为n的图G=(V,E)的邻接矩阵A是n*n的，将G的顶点编号为v1,v2,......vn。若（vi,vj)∈E，则A[i][j]=1，否则A[i][j]=0。
对于带权图而言，若顶点vi,vj之间有边相连，则邻接矩阵中对应项存放着该边对应的权值，若顶点vi和vj不相连，则用∞来表示这两个顶点之间不存在边 运行结果如下： 代码基本是一样的，只是对称的位置上权值不一样 /***********创建有向图************/ void create_Graph2(MGraph *G) { int i, j; int start, end; //边的起点序号、终点序号 int numV, numE; int w; //边上的权值 printf("请输入所创建有向图的顶点数和边数(用空格隔开):"); scanf_s("%d%d", &numV, &numE); G->vexnum = numV; G->edgenum = numE; printf("\n"); //图的初始化 for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { if (i == j) G->Edge[i][j] = 0; else G->Edge[i][j] = 32767; } } //顶点信息存入顶点表 for (i = 0; i < G->vexnum; i++) { printf("请输入第%d个顶点的信息:", i + 1); scanf_s("%d", &G->Vex[i]); } printf("\n"); //输入无向图边的信息 for (i = 0; i < G->edgenum; i++) { printf("请输入边的起点序号，终点序号，权值(用空格隔开)："); scanf_s("%d%d%d", &start, &end, &w); G->Edge[start - 1][end - 1] = w; //有向图只在这里不一样 } }深度优先遍历 /**********深度优先遍历*********/ int visitDFS[maxSize]; void DFS(MGraph G,int i) { int j; visitDFS[i] = 1; printf("%d ", G.Vex[i]); for (j = 0; j < G.vexnum; j++) { if (G.Edge[i][j] != 32767 && !visitDFS[j]) DFS(G, j); } } void DFSTraverse(MGraph G) { int i; for (i = 0; i < G.vexnum; i++) visitDFS[i] = 0; for (i = 0; i < G.vexnum; i++) { if (!visitDFS[i]) DFS(G, i); } } 广度优先遍历 /**************广度优先遍历*************/ //队列 typedef struct { int data[maxSize]; int front, rear; }Queue; //初始化 void InitQueue(Queue *Q) { Q->front = Q->rear = 0; } //判断队空 int IsEmpty(Queue *Q) { if (Q->front == Q->rear) return 1; else return 0; } //入队 void EnQueue(Queue *Q,int e) { if ((Q->rear + 1) % maxSize == Q->front) return; else { Q->data[Q->rear] = e; Q->rear = (Q->rear + 1) % maxSize; } } //出队 void DeQueue(Queue *Q,int *e) { if (Q->rear == Q->front) return; *e = Q->data[Q->front]; Q->front = (Q->front + 1) % maxSize; } //广度优先遍历 int visitBFS[maxSize]; void BFS(MGraph G) { int i, j; Queue Q; for (i = 0; i < G.vexnum; i++) visitBFS[maxSize] = 0; InitQueue(&Q); for (i = 0; i < G.vexnum; i++) { if (!visitBFS[i]) { visitBFS[i] = 1; printf("%d ", G.Vex[i]); EnQueue(&Q, i); while (!IsEmpty(&Q)) { DeQueue(&Q, &i); for (j = 0; j < G.vexnum; j++) { if (!visitBFS[j] && G.Edge[i][j] != 32767) { visitBFS[j] = 1; printf("%d ", G.Vex[j]); EnQueue(&Q, j); } } } } } }
|
【本文地址】
公司简介
联系我们
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |