tu.cpp

以邻接表为存储结构

#include<iostream.h>
#define exit 0 ;
#define MAX_VERTEX_NUM 20
typedef int InfoType  ;
typedef struct ArcNode {                         //表结点
  int       adjvex;                              // 该弧所指向的顶点的位置
  struct ArcNode *nextarc;                       // 指向下一条弧指针
  InfoType  info;                                // 该弧相关信息的指针
} ArcNode;
typedef char VertexType ;
typedef struct VNode {                           //头结点
 VertexType  data;                               // 顶点信息
  ArcNode  *firstarc;                            // 指向第一条依附该顶点的弧
  } VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { 
    AdjList  vertices;
    int  vexnum,arcnum;                          //图的当前顶点数和弧数
}ALGraph;
typedef struct QNode{
    VertexType  data;
      struct QNode *next;
     } QNode,*QueuePtr;
typedef struct{
         QueuePtr front;
         QueuePtr rear;
    }LinkQueue; 
 void InitQueue(LinkQueue  &Q)
          {
             Q.front=Q.rear=new QNode;
             if(!Q.front) exit(1);
             Q.front->next=NULL;
           }
void EnQueue(LinkQueue &Q,VertexType e)
{                                               // 在当前队列的尾元素之后，插入元素 e 为新的 队列尾元素
QNode *p;
p=new QNode;
if(!p)exit(1);                                  // 存储分配失败
p->data=e;
p->next=NULL;
Q.rear->next=p;                                 // 修改尾结点的指针
Q.rear=p;                                       // 移动队尾指针　
}
void DeQueue(LinkQueue &Q,VertexType &e)        // 若队列不空，则删除当前队列 Q 中的头元素，用 e 返回其值，
                                                //并返回 TRUE；否则返回 FALSE 
{
if(Q.front==Q.rear)exit(1);                     // 链队列中只有一个头结点
QNode *p;
p=Q.front->next;
e=p->data;                                      // 返回被删元素
Q.front->next=p->next;                          // 修改头结点指针
if(Q.rear==p)Q.rear=Q.front;
delete p;                                       // 释放被删结点
}    
void CreateGraph (ALGraph &G) {
int head,tail;
InfoType weight;
cout<<"输入顶点数和边数"<<endl;
    cin >> G.vexnum >> G.arcnum;                //输入顶点数和边数
	cout<<"输入各顶点的信息"<<endl;
    for ( int i = 0; i < G.vexnum; i++) { 
		//cout<<"输入顶点"<<i<<"的信息"<<endl;
        cin >> G. vertices[i].data;             //输入顶点信息
        G. vertices[i].firstarc = NULL;
    }
	cout<<"**************逐条边输入各边的信息**************"<<endl;
    for ( i = 0; i < G.arcnum; i++) {           //逐条边输入
	
	cout<<"请输入第 "<<i+1<<"条边的尾结点"<<'\t'<<"头结点"<<'\t'<<"权值"<<endl;
        cin >> tail >> head >> weight;
        ArcNode * p = new ArcNode;
		p->adjvex = head;  
		p->info = weight; 
       p->nextarc = G. vertices[tail].firstarc; //链入第
                                                //  tail 号链表的前端
        G. vertices[tail].firstarc = p;
     }
}
int visited[MAX_VERTEX_NUM];                    //对顶点是否被访问进行标记，若未被访问则标记为0；否则标记为1
int FirstAdjVex(ALGraph G,int v)
{
	if(G.vertices[v].firstarc)
		return G.vertices[v].firstarc->adjvex;
	else
         return -1;
}
int NextAdjVex(ALGraph G,int v,int w)
{
	ArcNode *p=G.vertices[v].firstarc;
    while(p->nextarc&&p->adjvex!=w)
         p=p->nextarc;
	if(p->nextarc)
	{p=p->nextarc;
	return p->adjvex;}

	else
         return -1;
}
void DFS(ALGraph G,int v)
{
cout<<G. vertices[v].data<<'\t';
visited[v]=1;
for(int w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
 if(!visited[w]) DFS(G,w);                       //对v的尚未访问的邻接顶点w递归调用DFS

}
void DFSTraverse(ALGraph G, int v)
{
for(int i=0;i<G.vexnum;++i)
visited[i]=0;
//for(v=0;v<G.vexnum;++v)
 if(visited[v]==0)  DFS(G,v);
}  

void BFSTraverse(ALGraph G)
{                                                //按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited.
    LinkQueue Q;
	VertexType u;
	for(int v=0;v<G.vexnum;++v)
		visited[v]=0;
	InitQueue(Q);
	for(v=0;v<G.vexnum;++v)
		if(!visited[v])
		{
		visited[v]=1;
		cout<<G. vertices[v].data<<'\t';
		EnQueue(Q,v);
		while(Q.front!=Q.rear)
		{
		DeQueue(Q,u);
		 for(int w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
			 if(!visited[w])
			 {
				visited[w]=1;
				cout<<G. vertices[w].data<<'\t';
			 EnQueue(Q,w);
			 }
		}
		}
}
void main()
{
ALGraph G;
cout<<"**************************图的基本操作**************************"<<endl;
cout<<"---------创建图---------"<<endl;
CreateGraph( G) ;
int v; 
cout<<"输入要开始的结点下标：";
cin>>v;
cout<<"-------图的深度遍历-------"<<endl;
DFSTraverse( G,v);
cout<<endl;
cout<<"-------图的广度遍历-------"<<endl;
BFSTraverse( G);
cout<<endl;
}