实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法
//实现有向图、无向图、有权图、无权图的邻接矩阵和邻接表表示方法 //邻接矩阵 #define maxn 64 //最大顶点数 typedef char vtype //设当前顶点为字符类型 typedef int adjtype //设邻接矩阵A中元素aij为整型 typedef struct { vtype V[maxn]; //顶点存储空间 adjtype A[maxn][maxn]; //邻接矩阵 }mgraph; //图的说明符 void createmgraph(mgraph G) //建立无向图的邻接矩阵法的算法 { int i, j, n; vtype ch, u, v; adjtype w; i = n = 0; ch = getchar(); //输入顶点 while(ch != '#') //'#'为结束符 { n++; //顶点计数 if(n > maxn - 1) ERROR(n); //溢出处理 G.V[i++] = ch; //存入顶点 ch = getchar(); } for(i = 0; i < n; i++) //初始化邻接矩阵 for(j = 0; j < n; j++) G.A[i][j] = max; //设max为机器表示的无穷大 scanf("%c %c %d", &u, &v, &w) //读入一条边 while(u != '#') //u='#'时结束 { i = locatevex(G, u); //求u的序号 j = locatevex(G, v); //求v的序号 G.A[i][j] = G.A[j][i] = w; //邻接矩阵的赋值（对称） scanf("%c %c %d", &u, &v, &w); //读入下一条边 } } //邻接表 typedef struct node //链表节点类型 { int adj; //临界点域 int w; //存放边上的权 struct node *next; //指向下一弧或边 }linknode; typedef struct //顶点类型 { vtype data; //顶点值域 linknode *farc; //指向与本顶点关联的第一条弧或边 }Vnode; Vnode G[maxn]; //顶点表 void createadj(vnode G[maxn]) //建立无向图邻接表算法 { int i, j, n; linknode *p; vtype ch, u, v; i = n = 0; ch = getchar(); //读入顶点（设数据为字符） while(ch != '#') //'#'为结束符 { n++; //顶点计数 G[i].data = ch; //存入顶点 G[i].farc = NULL; //置空表 i++; ch = getchar(); } scanf("%c %c", u, v); //读入一条边 while(u != '#') //u='#'时结束 { i = locatevex(G, u); //求u的序号 j = locatevex(G, v); //求v的序号 //建立v1到v2的链接 p = (linknode*)malloc(sizeof(linknode)); //申请链表节点 p -> adj = j; //存入临界点序号 p -> next = G[i].farc; //将p节点作为单链表的第一节点插入 G[i].farc = p; //由无向图的对称性建立V1到V2的链接 p = (linknode*)malloc(sizeof(linknode)); p -> adj = i; p -> next = G[j].farc; G[j].farc = p; scanf("%c %c", &u, &v); //读下一条边 } }实现图的深度优先搜索、广度优先搜索
//实现图的深度优先搜索、广度优先搜索 //深度优先搜索算法 void DFS(Vnode G[], int v) { int u; visit(G, v); visited[v] = True; u = firstadj(G, v); while(u >= 0) { if(visit[u] == False) DFS{G, u}; u = nextadj(G, v, u); } } //广度优先搜索算法 void BFS(Vnode G[], int v) { int u; Clearqueue(Q); visit(G, v); visited[v] = True; Equeue(Q, v); while(!Emptyqueue(Q)) { v = Delqueue(Q); u = firstadj(G, v); while(u >= 0) { if(visitied[u] == False) { visit(G, u); visited[u] = True; Equeue(Q, u); } u = nextadj(G, v, u); } } }实现 Dijkstra 算法、A* 算法
//实现 Dijkstra 算法、A* 算法 typedef struct { int pi[n]; int end; }pathtype; pathtype path[n]; int dist[n]; void Dijkstra(mgraph G, pathtype path[], int dist[], int v, int n) { int i, count, S[n], m, u, w; for(i = 0; i < n; i++) { S[i] = 0; dist[i] = G.A[v][i]; path[i].pi[0] = v; path[i].end = 0; } S[v] = 1; count = 1; while(count <= n-1) { m = max; for(w = 0; w <= n - 1; w++) { if(S[w] == 0 && dist[w] < m){ u = w; m = dist[w]; } if(m = max) break; S[u] = 1; path[u].end++; path[u].pi[end] = u; for(w = 0; w <= n - 1; w++) { if(S[w] == 0 && dist[w] > dist[u] + G.A[u][w]) { dist[w] = dist[u] + G.A[u][w]; path[w] = path[u]; } count++; } } } }实现拓扑排序的 Kahn 算法、DFS 算法
//实现拓扑排序的 Kahn 算法、DFS 算法 void Creatid(Vexnode G[], int n, int id[]) { int count, i; arcnode *p; for(i = 0; i < n; i++){ count = 0; p = G[i].fin; while(p) { count++; p = p->hlink; } id[i] = count; } } void Topsort(Vexnode G[], int n) { int i, j, k, count, id[]; arcnode *p; Creatid(G, n, id); Clearstack(s); for(i = 0; i < n; i++) if(id[i] == 0) Push(s, i); count = 0; while(!Emptystack(s)) { j = Pop(s); output(j, G[j].data); count++; p = G[j].fout; while(p) { k = p->head; id[k]--; if(id[k] == 0) Push(s, k); p = p->tlink; } } if(count == n) printf("This graph has not cycle."); else printf("This graph has cycle."); }