Tag:图论

Tag (图论)'s result:

邻接表+有向图+深广搜

#include <stdio.h> #include <stdlib.h> #include <queue> using namespace std; char vertex[20]; //深搜用栈,广搜用队列 typedef struct enode { //表结点 int nexttov; //相邻顶点 struct enode * nextedge; //相邻下一个表结点 }enode; typedef struct { //头结点 char vertex; //顶点信息 enode *firstedge; //第一条边(出度)/第一个表结点 }vnode; typedef struct { //图 int vnum,edgenum; vnode vnodestr[20]; //头结点信息数组 }graph; void creategraph(graph *g) { int i,from,to; enode *p,*pedge; printf(“输入有向图顶点个数\n”); scanf(“%d”,&g->vnum); getchar(); printf(“输入有向图顶点名字\n”); for(i=0;i<g->vnum;i++) { scanf(“%c”,&g->vnodestr[i].vertex); g->vnodestr[i].firstedge = NULL; //顶点的第一个表结点初始化空 } printf(“输入有向图边个数\n”); scanf(“%d”,&g->edgenum); printf(“输入有向图边信息\n”); printf(“起点 终点\n”); for(i=0;i<g->edgenum;i++) { scanf(“%d%d”,&from,&to); pedge = (enode*)malloc(sizeof(enode)); //开空间给表结点 pedge->nextedge = NULL; pedge->nexttov = to; p = g->vnodestr[from].firstedge; if(!p) { g->vnodestr[from].firstedge = pedge; } else //尾插 { while(p->nextedge) { p = p->nextedge; } p->nextedge = pedge; } } } int findvsite(graph *g,char v) { int i; for(i=0;i<g->vnum;i++) { if(g->vnodestr[i].vertex==v) //返回顶点位序 return i; } return -1; } int getarcsnum(graph *g,int index) { int k = 0; enode *p = g->vnodestr[index].firstedge; if(index>=0&&index<g->vnum) { while(p) { k++; //有一个邻接点就是有一个出度 p = p->nextedge; } return k; } return -1; } int connected(graph *g,int from,int to) //看有没边 { enode *p = g->vnodestr[from].firstedge; if((from<0||from>=g->vnum) || (to<0&&to>=g->vnum)) return……

拓扑排序

http://acm.hdu.edu.cn/showproblem.php?pid=1285 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出 现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。 —————–摘自《百度百科》 简单的说,就是要求一项工程的完成时的先后序列,比如做暑假作业,先数学,再语文,最后英语,这是一种。注意拓扑排序不能有环! 排序方法: 步骤:1、找入度0的点进序列,接着去掉这个点的出边 2、再找入度0的点进序列,接着去掉这个点的出边 3、如此循环直到点都进了序列,如果同时有入度为0的点就随便进一个点到序列 上个hdu题目的解题代码: #include <stdio.h> #include <stdlib.h> #include <string.h> int graph[505][505]; int du[505]; void topological_sort(int n) { int i,j,k,w; for (i=1; i<=n; i++) //要遍历n次 { for (j=1; j<=n; j++) //找入度为0的点 { if (du[j]==0) //找到了 { printf(“%d%c”,j,i==n?’\n’:’ ‘); du[j]–; //入度变-1表示去掉这个点(已经排序了) k = j; //记录 break; } } for (w=1; w<=n; w++) //找和k点邻接的点(被k打败过的对手) { if (graph[k][w]==1) { // graph[k][w] = 0; //标记为找过了 du[w]–; //入度-1(表示把k的出度/出边去光了) } } } } int main() { int n,m,x,y; while (scanf(“%d%d”,&n,&m)==2) { memset(graph,0,sizeof(graph)); memset(du,0,sizeof(du)); while (m–) { scanf(“%d%d”,&x,&y); if (graph[x][y]==0) //x打败y { graph[x][y] = 1; //在邻接矩阵中记录为1表示不能被同一个对手重复打败 du[y]++; //y被打败过就入度+1 } } topological_sort(n); } return 0; }  

邻接矩阵+有向/无向图+深广搜

//此程序可以实现带权有向/无向图 #include <stdio.h> #include <queue> #include <iostream> #define INF 32768 //两点无连接则权值无穷大 using namespace std; int visited1[20]; //标记数组,表示已经访问过 int visited2[20]; typedef struct { int adj; //权值 int *info; //弧相关信息的指针 } arccell; typedef struct { char vexs[20]; //顶点向量 arccell arcs[20][20]; //邻接矩阵 int vexnum,arcnum; // 图的当前顶点数,弧数 int kind; //图的种类 } graph; int locat(graph G,char v) //返回顶点v在顶点向量中的位置 { for (int i=0; v!=G.vexs[i]&&i<G.vexnum; i++) { if (i>=G.vexnum) { return -1; } } return i; //返回Vx的位置 } int create(graph &G) //&是引用 { int incinfo = 0; printf(“input specise\n”); scanf(“%d”,&G.kind); printf(“input v\n”); scanf(“%d”,&G.vexnum); printf(“input a\n”); scanf(“%d”,&G.arcnum); printf(“incinfo?\n”); scanf(“%d”,&incinfo); printf(“build v\n”); for (int i1=0; i1<G.vexnum; i1++) //输入顶点名字 { printf(“input %d’s informations “,i1+1); scanf(“%s”,&G.vexs[i1]); //构造顶点向量 } for (int i=0; i<G.vexnum; i++) //初始化邻接矩阵 { for (int j=0; j<G.vexnum; j++) { G.arcs[i][j].adj = INF; G.arcs[i][j].info = 0; } } char v1,v2; int w; for (int k=0; k<G.arcnum; k++) //构造邻接矩阵 { printf(“input %d’s v1:”,k+1); scanf(“%s”,&v1); printf(“input %d’s v2:”,k+1); scanf(“%s”,&v2); printf(“input %d’s w:”,k+1); scanf(“%d”,&w); int i=locat(G,v1); int j=locat(G,v2); G.arcs[i][j].adj = w; if (incinfo) { scanf(“%d”,&G.arcs[i][j].info); } if (!G.kind) { G.arcs[j][i].adj=G.arcs[i][j].adj; //1有向与0无向不同 } }……