图的基本运算

【文件属性】：
文件名称：图的基本运算
文件大小：17KB
文件格式：DOCX
更新时间：2016-06-16 15:58:31
图的运算 好资源#include #include #include using namespace std; //表结点 typedef struct ArcNode{ int adjvex;//该弧所指向的顶点的位置 ArcNode *nextarc;//指向下一条弧的指针 }ArcNode; //头结点 typedef struct VNode{ string data;//顶点信息 ArcNode* firstarc;//第一个表结点的地址，指向第一条依附该顶点的弧的指针 }VNode, AdjList[10]; typedef struct{ AdjList vertices; int vexnum, arcnum;//图的顶点数和弧数 }ALGraph; int LocateVex(ALGraph G, string u)//返回顶点u在图中的位置 { for(int i=0; i>G.vexnum>>G.arcnum; cout<<"请输入顶点："; for(i=0; i>G.vertices[i].data; G.vertices[i].firstarc=NULL; } cout<<"请输入边："; cout<>v1>>v2; i=LocateVex(G, v1); j=LocateVex(G, v2); //插入v1的邻接表,为了提高效率，总在表头插入结点。 ArcNode *arc=new ArcNode; arc->adjvex=j; arc->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=arc; //插入v2的邻接表,为了提高效率，总在表头插入结点。 arc=new ArcNode; arc->adjvex=i; arc->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=arc; } } void Print(ALGraph G)//打印邻接表 { cout<<"打印邻接表如下："; cout<"<adjvex].data; p=p->nextarc; } cout<adjvex; else return -1; } int NextAdjVex(ALGraph G, int v, int w)//返回顶点v的相对于w的下一个邻接点序号 { ArcNode* p=G.vertices[v].firstarc; while(p) { if(p->adjvex==w) break; p=p->nextarc; } if(p->adjvex!=w || !p->nextarc)//如果没找到w或者w是最后一个邻接点 return -1; return p->nextarc->adjvex; } bool visited[10]; void DFS(ALGraph G, int v) { visited[v]=true; cout<=0; w=NextAdjVex(G, v, w) ) if(!visited[w]) DFS(G, w); } void DFSTraverse(ALGraph G)//深搜 { for(int i=0; i q; for(int i=0; i=0; w=NextAdjVex(G, v, w)) { if (!visited[w]) { q.push(w); visited[w]=true; } } } } } } void main() { ALGraph G; CreateUDG(G); Print(G); cout<<"深搜："; DFSTraverse(G); cout<