无向图作业

设无向图如下：C=（D，R），其中：
D={14，22，36，48，57，69，9，74，83}，
R={（14,22），（14，83），（14，36），（14，48），（22,36）,（22，57），（22，69），（36,83），（48,57），（48,74），（48,83），（57,9），（57,74），（69，9），（9，74）}
要求：
（1）绘制此图。
（2）给出此图的邻接矩阵和邻接表表示。
（3）设计算法实现图的邻接矩阵和邻接表并进行输出。
（4）在（3）的基础上，给出图的深度优先遍历的非递归算法和图的广度 优先算法。并将遍历结果存储到一维数组t1和t2中。
（5）利用t1数组实现二分查找算法，并进行算法分析。
（6）利用t2数组实现shell排序算法。
解答：
（1）
（2）

（3）

#include 
#include 
using namespace std;
#define MaxSize 50
typedef int ElemType;
bool visited1[MaxSize];
bool visited2[MaxSize];
unsigned int num=1,num1=1;
typedef struct
{ 
	int arc[MaxSize][MaxSize];
	int vextexnum,arcnum;
	ElemType vertex[MaxSize];
}MGraph;
typedef struct ArcNode
{
	int adjvex;
	struct ArcNode *next;
}ArcNode;
typedef struct VertexNode
{
	ElemType vertex;
	ArcNode *firstedge;
}VertexNode;
typedef struct ALGraph
{ 
	VertexNode adjlist[MaxSize];
	int vextexnum,arcnum;
}ALGraph;
int xuhao(ElemType a[],ElemType n)//序号查询函数，查找出该元素位于数组中的第几项，n为元素项
{
	int i;
	for(i=0;a[i]!=NULL;i++)
	{
		if(n==a[i])
		break;
	}
	return i;
}
void MGraph1(MGraph &g,ElemType a[],int n,int e)//邻接矩阵函数，g为需要生成的邻接矩阵数组，a为顶点数组，n为顶点个数，e为边的条数
{
	g.vextexnum=n;
	g.arcnum=e;
	int i,j,k;
	ElemType x,y;
	for(i=0;i
		cin>>x>>y;
		i=xuhao(a,x);
		j=xuhao(a,y);
		g.arc[i][j]=1;
		g.arc[j][i]=1;
	}
}
void ALGraph1(ALGraph &g,ElemType a[],int n,int e)//邻接表函数，g为需要生成的邻接表，a为顶点数组，n为顶点个数，e为边的条数
{
	g.vextexnum=n;
	g.arcnum=e;
	int i,j,k;
	ElemType x,y;
	ArcNode *s,*m;
	for(i=0;i
		g.adjlist[i].vertex=a[i];
		g.adjlist[i].firstedge=NULL;
	}
	for(k=0;k
		cin>>x>>y;
		i=xuhao(a,x);
		j=xuhao(a,y);
		s=new ArcNode;
		m=new ArcNode;
		s->adjvex=j;
		s->next=g.adjlist[i].firstedge;
		g.adjlist[i].firstedge=s;
		m->adjvex=i;
		m->next=g.adjlist[j].firstedge;
		g.adjlist[j].firstedge=m;
	}
}
void DispMat(MGraph &g)//邻接矩阵的输出函数，g为需要输出的邻接矩阵
{
	int i,j;
	for(i=0;i
		for(j=0;j
	int i;
	ArcNode *p;
	for(i=0;i
		p=G.adjlist[i].firstedge;
		  if(p!=NULL)
			  cout<
			  cout<adjvex<<"  ";
			  p=p->next;
		  }
		  cout<
    stack s;
    s.push(v); 
    cout<
        if(g.arc[v][j]==1&&visited1[j]==0)
		{
            visited1[j]=1;
            s.push(j);
            cout<
            if(t==s.top())
            break;
            s.pop();
            v=s.top();j=0;
        }
    }
}
void BFSraverse(MGraph g,int v,ElemType t2[])//广度优先遍历函数，g为需要遍历的图，v为开始遍历的序号，t2为需要存储遍历结果的数组
{
	int j;
	int front,rear;
    int Q[MaxSize];
    front=rear=-1;
	cout<
		v=Q[++front];
		for(j=0;j 
			if(g.arc[v][j]==1&&visited2[j]==0)
			{ 
				num1++;
				t2[num1]=g.vertex[j];
				cout<
	int i,j,k;
	for(i=0;i<8;i++)
		for(j=1;j<9;j++)
		{
			if(a[j]>a[j+1])
			{
				k=a[j+1];
				a[j+1]=a[j];
				a[j]=k;
			}
		}
}
int erfen(ElemType r[],int low,int high,int k)//二分法查找函数，r数组为需要查找的数组，low为该数组的最小的元素序号，high为最高的序号，k为需要查找的元素
{
   int mid;
   if(low<=high )
{
   mid=(low+high)/2;
   if(k==r[mid])
   return mid;   
   else if(k
	int i,j;
	for(i=d+1;i<=n;i++) 
	{
	    r[0]=r[i];                  
	    j=i-d;                   
	   while(j>0&&r[0] 
	        r[j+d]=r[j];     
	       j=j-d;                 
	    }
	   r[j+d]=r[0];
	 }
}
void main()
{ 
	int i,n,x,d;
	ElemType t1[20],t2[20];
	MGraph g;
	ALGraph g1;
	ElemType a[]={14,22,36,48,57,69,9,74,83};
	cout<<"请输入图的15条边两端的顶点："<>x;
	n=erfen(t1,1,9,x);
	if(n==0)
		cout<<"没有此数值"<=1;d=d/2)
	shell(t2,9,d);
	for(i=1;i<10;i++)
	cout< 
需要输入的数据：
 14 22
 14 83
 14 36
 14 48
 22 36
 22 57
 22 69
 36 83
 48 57
 48 74
 48 83
 57 9
 57 74
 69 9
 9 74
 
 
 （4）
 （5）
 （6）