首页 > 代码库 > 图的概念与实现
图的概念与实现
图是由顶点的有穷非空集合和顶点之间边的集合组成，所以，图不允许没有顶点。可以有空表，空树，但是没有空图。
图分有向图和无向图。无向图油顶点和边构成，有向图油顶点和狐构成。弧有弧头和弧尾。
图按照边或弧的多少分希疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。
无向图顶点的边数叫度，有向图顶点分为入度和出度。图上的边或弧带权叫网。
图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两点间都是连通的，则图就是连通图，有向则称为强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。
无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入读为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。
1 /*图的实现*/ 2 #include <stdio.h> 3 #include <stdlib.h> 4 #include <time.h> 5 #include "Queue.h" 6 7 #define OK 1 8 #define ERROR 0 9 typedef int Status; 10 11 typedef char VertexType; 12 typedef int EdgeType; 13 #define MAXVEX 100 14 #define INFINITY 65535 15 16 /*邻接矩阵*/ 17 typedef struct 18 { 19 VertexType vex[MAXVEX]; 20 EdgeType arc[MAXVEX][MAXVEX]; 21 int numVertexes, numEdges; 22 }MGraph; 23 24 void CreateMGraph(MGraph *G) 25 { 26 int i, j, k, w; 27 char tmp; 28 tmp = getchar(); 29 printf("Input ver and edg :"); 30 scanf("%d %d", &G->numVertexes, &G->numEdges); 31 tmp = getchar(); 32 for (i = 0; i < G->numVertexes; i++) 33 { 34 printf("Input vertex :"); 35 //scanf(&G->vex[i]); 36 char s = getchar(); 37 G->vex[i] = s; 38 tmp = getchar(); 39 } 40 for(i=0;i<G->numEdges;i++) 41 for (j = 0; j < G->numEdges; j++) 42 { 43 G->arc[i][j] = INFINITY; 44 } 45 for (k = 0; k < G->numEdges; k++) 46 { 47 printf("Input ver1 and ver2 and w:"); 48 scanf("%d %d %d", &i, &j, &w); 49 tmp = getchar(); 50 G->arc[i][j] = w; 51 G->arc[j][i] = G->arc[i][j]; 52 } 53 } 54 /*邻接表*/ 55 typedef struct EdgeNode 56 { 57 int adjvex; 58 EdgeType weight; 59 struct EdgeNode * next; 60 }EdgeNode; 61 typedef struct VertexNode 62 { 63 VertexType data; 64 EdgeNode *firstedge; 65 }VertexNode, AdjList[MAXVEX]; 66 typedef struct 67 { 68 AdjList adjList; 69 int numVertexes, numEdges; 70 }GraphAdjList; 71 void CreateALGraph(GraphAdjList *G) 72 { 73 int i, j, k; 74 EdgeNode *e; 75 char tmp; 76 printf("Input ver and edg :"); 77 scanf("%d %d", &G->numVertexes, &G->numEdges); 78 tmp = getchar(); 79 for (i = 0; i < G->numVertexes; i++) 80 { 81 printf("Input vertex :"); 82 //scanf("%c",&G->adjList[i].data); 83 char s; 84 s = getchar(); 85 tmp = getchar(); 86 G->adjList[i].data =http://www.mamicode.com/ s; 87 G->adjList[i].firstedge = NULL; 88 } 89 for (k = 0; k < G->numEdges; k++) 90 { 91 printf("Input ver1 and ver2:"); 92 scanf("%d %d", &i, &j); 93 tmp = getchar(); 94 e = (EdgeNode*)malloc(sizeof(EdgeNode)); 95 e->adjvex = j; 96 97 e->next = G->adjList[i].firstedge; 98 G->adjList[i].firstedge = e; 99 e = (EdgeNode*)malloc(sizeof(EdgeNode));100 e->adjvex = i;101 e->next = G->adjList[j].firstedge;102 G->adjList[j].firstedge = e;103 }104 }105 /*邻接矩阵的深度优先遍历*/106 typedef int Boolean;107 Boolean visited[MAXVEX];108 void DFSM(MGraph G, int i)109 {110 int j;111 visited[i] = true;112 printf("%c ", G.vex[i]);113 for (j = 0; j < G.numVertexes; j++)114 {115 if (G.arc[i][j] == 1 && !visited[j])116 DFSM(G, j);117 }118 }119 void DFSMTraverse(MGraph G)120 {121 int i;122 for (i = 0; i < G.numVertexes; i++)123 visited[i] = false;124 for (i = 0; i < G.numVertexes; i++)125 if (!visited[i])126 DFSM(G, i);127 }128 /*邻接表的深度优先遍历，递归算法*/129 void DFSAL(GraphAdjList G, int i)130 {131 EdgeNode* p;132 visited[i] = true;133 printf("%c ", G.adjList[i].data);134 p = G.adjList[i].firstedge;135 while (p)136 {137 if (!visited[p->adjvex])138 DFSAL(G, p->adjvex);139 p = p->next;140 }141 }142 void DFSALTraverse(GraphAdjList G)143 {144 int i;145 for (i = 0; i < G.numVertexes; i++)146 visited[i] = false;147 for (i = 0; i < G.numVertexes; i++)148 if (!visited[i])149 DFSAL(G, i);150 }151 /*邻接矩阵的广度优先遍历*/152 void BFSMTraverse(MGraph G)153 {154 int i, j;155 SqQueue Q;156 for (i = 0; i < G.numVertexes; i++)157 visited[i] = false;158 InitQueue(&Q);159 for (i = 0; i < G.numVertexes; i++)160 {161 if (!visited[i])162 {163 visited[i] = true;164 printf("%c ", G.vex[i]);165 EnQueue(&Q, i);166 while(!QueueEmpty(Q))167 {168 DeQueue(&Q, &i);169 for (j = 0; j < G.numVertexes; j++)170 {171 if (G.arc[i][j] == 1 && !visited[j])172 {173 visited[j] = true;174 printf("%c ", G.vex[j]);175 EnQueue(&Q, j);176 }177 }178 }179 }180 }181 }182 /*邻接表的广度优先遍历*/183 void BFSALTraverse(GraphAdjList G)184 {185 int i;186 EdgeNode *p;187 SqQueue Q;188 for (i = 0; i < G.numVertexes; i++)189 visited[i] = false;190 InitQueue(&Q);191 for (i = 0; i < G.numVertexes; i++)192 {193 if (!visited[i])194 {195 visited[i] = true;196 printf("%c ", G.adjList[i].data);197 EnQueue(&Q, i);198 while (!QueueEmpty(Q))199 {200 DeQueue(&Q, &i);201 p = G.adjList[i].firstedge;202 while(p)203 {204 if (!visited[p->adjvex])205 {206 visited[p->adjvex] = true;207 printf("%c ", G.adjList[p->adjvex].data);208 EnQueue(&Q, p->adjvex);209 }210 p = p->next;211 }212 }213 }214 }215 }216 int main()217 {218 MGraph T;219 GraphAdjList G;220 char opp = ‘-1‘;221 222 printf("\n1.创建邻接矩阵图 \n2.创建邻接表图 \n3.深度遍历邻接矩阵 \n4.深度遍历邻接表 \n5 广度遍历邻接矩阵 \n6 广度遍历邻接表 \n0 退出 \n请选择你的操作：\n");223 224 while (opp != ‘0‘) {225 opp = getchar();226 switch (opp) {227 case ‘1‘:228 CreateMGraph(&T);229 printf("create finish!\n");230 break;231 case ‘2‘:232 CreateALGraph(&G);233 printf("create finish!\n");234 break;235 case ‘3‘:236 DFSMTraverse(T);237 printf("\n");238 break;239 case ‘4‘:240 DFSALTraverse(G);241 printf("\n");242 break;243 case ‘5‘:244 BFSMTraverse(T);245 printf("\n");246 break;247 case ‘6‘:248 BFSALTraverse(G);249 printf("\n");250 break;251 case ‘0‘:252 exit(0);253 }254 }255 }
图的概念与实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。