在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。
在有向图中，通常将边称作弧，含箭头的一端称为弧头，另一端称为弧尾，记作<vi,vj>，它表示从顶点vi到顶点vj有一条边。
若有向图中有n个顶点，则最多有n(n-1)条弧，我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。在无向图中，边记作(vi,vj)，它蕴涵着存在< vi,vj>和<vj,vi>两条弧。若无向图中有n个顶点，则最多有n(n-1)/2条弧，我们又将具有n(n-1)/2条弧的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。
路径长度是指路径上边或弧的数目。
若第一个顶点和最后一个顶点相同，则这条路径是一条回路。
若路径中顶点没有重复出现，则称这条路径为简单路径。
在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。
在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。
图的基本操作
（1）创建一个图结构 CreateGraph(G)
（2）检索给定顶点 LocateVex(G,elem)
（3）获取图中某个顶点 GetVex(G,v)
（4）为图中顶点赋值 PutVex(G,v,value)
（5）返回第一个邻接点 FirstAdjVex(G,v)
（6）返回下一个邻接点 NextAdjVex(G,v,w)
（7）插入一个顶点 InsertVex(G,v)
（8）删除一个顶点 DeleteVex(G,v)
（9）插入一条边 InsertEdge(G,v,w)
（10）删除一条边 DeleteEdge(G,v,w)
（11）遍历图 Traverse(G,v)
d打开ＩＤＥ
我们来创建一个工程
类的声名如下
#if !defined(AFX_GRAPH_H__DB7A5E72_86CB_45E7_B575_00831A6D3C5F__INCLUDED_)#define AFX_GRAPH_H__DB7A5E72_86CB_45E7_B575_00831A6D3C5F__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
//图的相关数据类型的定义graph.h
//最多顶点数
const int MaxV=10;
//最大权值
const int MaxValue=99;
//定义邻接表中的边结点类型
struct edgenode {
int adjvex; //邻接点域
int weight; //权值域
edgenode* next;//指向下一个边结点的链域
};
//定义邻接表类型
typedef edgenode** adjlist;
//邻接矩阵类定义
class AdjMatrix
{private:
char g[MaxV];//顶点信息数组
int size;//当前顶点数
int GA[MaxV][MaxV];//定义邻接矩阵GA
int numE;//当前边数
public:
//构造函数,初始化图的邻接矩阵
AdjMatrix(int n,int k2);
//判断图空否
bool GraphEmpty() {return size==0;}
//取当前顶点数
int NumV() {return size;}
//取当前边数
int NumEdges() {return numE;}
//取顶点i的值
char GetValue(const int i);
//取弧<v1,v2>的权
int GetWeight(const int v1,const int v2);
//在位置pos处插入顶点V
void InsertV(const char &V,int pos);
//插入弧<v1,v2>,权为weight
void InsertEdge(const int v1,const int v2,int weight);
//删除顶点i与顶点i相关的所有边
char DeleteVE(const int i);
//删除弧<v1,v2>
void DeleteEdge(const int v1,const int v2);
//建立图的邻接矩阵
void CreateMatrix(int n, int k1,int k2);
//k1为0则无向否则为有向,k2为0则无权否则为有权
//从初始点vi出发深度优先搜索由邻接矩阵表示的图
void dfsMatrix(bool*& visited,int i,int n,int k2);
//从初始点vi出发广度优先搜索由邻接矩阵表示的图
void bfsMatrix(bool*& visited,int i,int n,int k2);
//由图的邻接矩阵得到图的邻接表
void graphChange(adjlist &GL,int n,int k2);
//检查输入的边序号是否越界,若越界则重输
void Check(int n,int& i,int& j);
//由图的邻接矩阵建立图
void Creatgraph(int n,int k2);
//对非连通图进行深度优先搜索
void dfsMatrix(int n,int k2);
//对非连通图进行广度优先搜索
void bfsMatrix(int n,int k2);
};
#endif // !defined(AFX_GRAPH_H__DB7A5E72_86CB_45E7_B575_00831A6D3C5F__INCLUDED_)
类的实现如下
#include "stdafx.h"//图的相关运算的实现graph.cpp#include "graph.h"//构造函数,初始化图的邻接矩阵AdjMatrix::AdjMatrix(int n,int k2){int i,j; if(k2==0){//初始化无(有)向无权图 for(i=0;i<n;i++) for(j=0;j<n;j++) GA[i][j]=0;} else {//初始化无(有)向有权图 for(i=0;i<n;i++) for(j=0;j<n;j++) if(i==j) GA[i][j]=0; else GA[i][j]=MaxValue;} size=numE=0;}//建立图的邻接矩阵void AdjMatrix::CreateMatrix(int n,int k1,int k2)//k1为0则无向否则为有向,k2为0则无权否则为有权{int i,j,k,e,w; cout<<"输入图的总边数:"; cin>>e; if(k1==0 && k2==0) { //建立无向无权图 cout<<"输入"<<e<<"条无向无权边的起点和终点序号!"<<endl; for(k=1; k<=e; k++) { cin>>i>>j; Check(n,i,j); GA[i][j]=GA[j][i]=1;} } else if(k1==0 && k2!=0) { //建立无向有权图 cout<<"输入"<<e<<"条无向带权边的起点和终点序号及权值!"<<endl; for(k=1; k<=e; k++) { cin>>i>>j>>w; Check(n,i,j); GA[i][j]=GA[j][i]=w;} } else if(k1!=0 && k2==0) { //建立有向无权图 cout<<"输入"<<e<<"条有向无权边的起点和终点序号!"<<endl; for(k=1; k<=e; k++) { cin>>i>>j; Check(n,i,j); GA[i][j]=1;} } else if(k1!=0 && k2!=0) { //建立有向有权图 cout<<"输入"<<e<<"条有向有权边的起点和终点序号及权值!"<<endl; for(k=1; k<=e; k++) { cin>>i>>j>>w; Check(n,i,j); GA[i][j]=w;}} numE=e; cout<<"创建后的邻接矩阵:\n"; for(i=0;i<n;i++) {for(j=0;j<n;j++) cout<<setw(4)<<GA[i][j]; cout<<endl;}}//从初始点vi出发深度优先搜索由邻接矩阵表示的图void AdjMatrix::dfsMatrix(bool*& visited,int i,int n,int k2){cout<<g[i]<<':'<<i<<" "; visited[i]=true; //标记vi已被访问过 for(int j=0; j<n; j++) //依次搜索vi的每个邻接点 if(k2==0) {if(i!=j&&GA[i][j]!=0&&!visited[j]) dfsMatrix(visited,j,n,k2);} else if(i!=j&&GA[i][j]!=MaxValue&&!visited[j]) dfsMatrix(visited,j,n,k2);}//从初始点vi出发广度优先搜索由邻接矩阵表示的图void AdjMatrix::bfsMatrix(bool*& visited,int i,int n,int k2){const int MaxLength=30; //定义一个队列q,其元素类型应为整型 int q[MaxLength]={0}; //定义队首和队尾指针 int front=0,rear=0; //访问初始点vi cout<<g[i]<<':'<<i<<" "; //标记初始点vi已访问过 visited[i]=true; //将已访问过的初始点序号i入队 q[++rear]=i; //当队列非空时进行循环处理 while(front!=rear) { //删除队首元素,第一次执行时k的值为i front=(front+1)%MaxLength; int k=q[front]; //依次搜索vk的每一个可能的邻接点 for(int j=0;j<n;j++) if(k2==0) {if(k!=j&&GA[k][j]!=0&&!visited[j]) {//访问一个未被访问过的邻接点vj cout<<g[j]<<':'<<j<<" "; visited[j]=true; //标记vj已访问过 rear=(rear+1)%MaxLength;//顶点序号j入队 q[rear]=j; } } else if(k!=j&&GA[k][j]!=MaxValue&&!visited[j]) {//访问一个未被访问过的邻接点vj cout<<g[j]<<':'<<j<<" "; visited[j]=true; //标记vj已访问过 rear=(rear+1)%MaxLength;//顶点序号j入队 q[rear]=j; }}}//检查输入的边序号是否越界,若越界则重输void AdjMatrix::Check(int n,int& i,int& j){while(1) { if(i<0||i>=n||j<0||j>=n) cout<<"输入有误,请重输!"; else return; cin>>i>>j; }}//由图的邻接矩阵得到图的邻接表void AdjMatrix::graphChange(adjlist &GL,int n,int k2){int i,j; if(k2==0) {for(i=0;i<n;i++){ for(j=0;j<n;j++) if(GA[i][j]!=0) { edgenode* p=new edgenode; p->adjvex=j; p->next=GL[i];GL[i]=p; cout<<'('<<i<<','<<p->adjvex<<") ";} cout<<endl;}} else { for(i=0;i<n;i++){ for(j=0;j<n;j++) if(GA[i][j]!=0 && GA[i][j]!=MaxValue) { edgenode* p=new edgenode; p->adjvex=j;p->weight=GA[i][j]; p->next=GL[i];GL[i]=p; cout<<'('<<i<<','<<p->adjvex<<','<<p->weight<<") ";} cout<<endl;}}}//由图的邻接矩阵建立图void AdjMatrix::Creatgraph(int n,int k2){int i,j,k,m=0; if(k2==0) {for(i=0;i<n;i++){ k=i; for(j=0;j<n;j++) if(GA[i][j]!=0) if(k==i&&m<n) {g[m]='A'+m;size++; cout<<g[m]<<'('<<i<<','<<j<<") "; m++; } } cout<<endl;} else { for(i=0;i<n;i++){ k=i; for(j=0;j<n;j++) if(GA[i][j]!=0 && GA[i][j]!=MaxValue) if(k==i&&m<n) {g[m]='A'+m;size++; cout<<g[m]<<'('<<i<<','<<j<<','<<GA[i][j]<<") "; m++; } } cout<<endl;} g[n]='\0';}//取顶点i的值char AdjMatrix::GetValue(const int i){if(i<0||i>size) {cerr<<"参数i越界!\n";exit(1);} return g[i];}//取弧<v1,v2>的权int AdjMatrix::GetWeight(const int v1,const int v2){if(v1<0||v1>size||v2<0||v2>size) {cerr<<"参数v1或v2越界!\n";exit(1);} return GA[v1][v2]; }//在位置pos处插入顶点Vvoid AdjMatrix::InsertV(const char &V,int pos){int i; if(size==MaxV) {cerr<<"表已满,无法插入!\n";exit(1);} if(pos<0||pos>size) {cerr<<"参数pos越界!\n";exit(1);} for(i=size;i>pos;i--) g[i]=g[i-1]; g[pos]=V; size++; }//插入弧<v1,v2>,权为weightvoid AdjMatrix::InsertEdge(const int v1,const int v2,int weight){if(v1<0||v1>size||v2<0||v2>size) {cerr<<"参数v1或v2越界!\n";exit(1);} GA[v1][v2]=weight; numE++; }//删除顶点v与顶点v相关的所有边char AdjMatrix::DeleteVE(const int v){for(int i=0;i<size;i++) for(int j=0;j<size;j++) if((i==v||j==v)&&GA[i][j]>0&&GA[i][j]<MaxValue) {GA[i][j]=MaxValue; numE--;} if(size==0) {cerr<<"表已空,无元素可删!\n";exit(1);} if(v<0||v>size-1) {cerr<<"参数v越界!\n";exit(1);} char temp=g[v]; for(int i=v;i<size-1;i++) g[i]=g[i+1]; size--; g[size]='\0'; return temp;}//删除弧<v1,v2>void AdjMatrix::DeleteEdge(const int v1,const int v2){if(v1<0||v1>size||v2<0||v2>size||v1==v2) {cerr<<"参数v1或v2出错!\n";exit(1);} GA[v1][v2]=MaxValue; numE--;}//对非连通图进行深度优先搜索void AdjMatrix::dfsMatrix(int n,int k2){bool *vis=new bool[NumV()]; for(int i=0;i<NumV();i++) vis[i]=false; for(int i=0;i<NumV();i++) if(!vis[i]) dfsMatrix(vis,i,n,k2); delete []vis;}//对非连通图进行广度优先搜索void AdjMatrix::bfsMatrix(int n,int k2){bool *vis=new bool[NumV()]; for(int i=0;i<NumV();i++) vis[i]=false; for(int i=0;i<NumV();i++) if(!vis[i]) bfsMatrix(vis,i,n,k2); delete []vis;}
代码调用如下
#include "stdafx.h"#include "graph.h"void main(){cout<<"graphM.cpp运行结果:\n"; //定义图的点数及搜索起始点序号等 int n,k,i; //k1为0则无向否则为有向,k2为0则无权否则为有权 int k1,k2; //标记已访问过的点 bool *vis; //定义邻接表 adjlist AL; cout<<"输入图的点数n=";cin>>n; AL=new edgenode*[n]; vis=new bool[n]; if(!vis) {cout<<"申请堆内存失败!\n";exit(1);} for(i=0;i<n;i++) vis[i]=false; cout<<"输入选择无向(权)与有向(权)图的值k1,k2:"; cin>>k1>>k2; //定义邻接矩阵 AdjMatrix A(n,k2); A.CreateMatrix(n,k1,k2); cout<<"出发点Vk的序号=";cin>>k; cout<<"\n输出邻接矩阵相应图的每个顶点:\n"; A.Creatgraph(n,k2); cout<<"当前的顶点数为:"<<A.NumV()<<endl; cout<<"当前的边数为:"<<A.NumEdges()<<endl; cout<<"图的深度优先搜索顺序:\n"; A.dfsMatrix(vis,k,n,k2); for(i=0;i<n;i++) vis[i]=false; cout<<"\n图的广度优先搜索顺序:\n"; A.bfsMatrix(vis,k,n,k2); cout<<"\n输出邻接表的每个邻接点:\n"; for(i=0;i<n;i++) vis[i]=false; A.graphChange(AL,n,k2); delete []vis; A.DeleteEdge(0,2); A.DeleteEdge(2,0); cout<<"当前的顶点数为:"<<A.NumV()<<endl; cout<<"当前的边数为:"<<A.NumEdges()<<endl; cout<<"图的深度优先搜索顺序:\n"; A.dfsMatrix(n,k2); cout<<"\n图的广度优先搜索顺序:\n"; A.bfsMatrix(n,k2); cin.get();cin.get();}
效果如下
代码下载
http://download.csdn.net/detail/yincheng01/4789890