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