【文件属性】：
文件名称：图的基本运算
文件大小：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<
