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……

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

//此程序可以实现带权有向/无向图 #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无向不同 } }……