① 有向图的邻接表存储如图所示，请画出其邻接矩阵存储结构
有向图的邻接表存储如图所示，其邻接矩阵存储如图：
② 给出一个有向图的邻接表存，怎么画出其邻接矩阵存储，求详解，谢谢了
将每一行的链表中的结点的邻接点下标（比如第i个头结点的链表中的弧结点中的信息为j），放到邻接矩阵中就是A[i][j]=1，如果结点还有权值则为权值，除了这些非0元素外，其他的都是0（如果有权图则其他的都是无穷大）
如果有向图的邻接表中有k个弧（边）结点，则邻接矩阵中就有k个1（或者权值）
③ 带权邻接矩阵的图的邻接矩阵表示法
1.图的邻接矩阵表示法
在图的邻接矩阵表示法中：
① 用邻接矩阵表示顶点间的相邻关系
② 用一个顺序表来存储顶点信息
2.图的邻接矩阵(Adjacency Matrix)
设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：
【例】下图中无向图G 5 和有向图G 6 的邻接矩阵分别为A l 和A 2 。
3.网络的邻接矩阵
若G是网络，则邻接矩阵可定义为：
其中：
w ij 表示边上的权值;
∞表示一个计算机允许的、大于所有边上权值的数。
【例】下面带权图的两种邻接矩阵分别为A 3 和A 4 。
4.图的邻接矩阵存储结构形式说明
#define MaxVertexNum l00 //最大顶点数，应由用户定义
typedef char VertexType; //顶点类型应由用户定义
typedef int EdgeType; //边上的权值类型应由用户定义
typedef struct{
VextexType vexs[MaxVertexNum] //顶点表
EdeType edges[MaxVertexNum][MaxVertexNum];
//邻接矩阵，可看作边表
int n，e; //图中当前的顶点数和边数
}MGragh;
注意：
① 在简单应用中，可直接用二维数组作为图的邻接矩阵(顶点表及顶点数等均可省略)。
② 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的枚举类型。
③ 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。
④ 邻接矩阵表示法的空间复杂度S(n)=0(n 2 )。
5.建立无向网络的算法。
void CreateMGraph(MGraph *G)
{//建立无向网的邻接矩阵表示
int i，j，k，w;
scanf(%d%d，&G->n，&G->e); //输入顶点数和边数
for(i = 0;i < n;i++) //读人顶点信息，建立顶点表
{
G->vexs=getchar();
}
for(i = 0;i < n;i++)
{
for(j = 0;j < n;j++)
{
G->edges[j] = 0; //邻接矩阵初始化
}
}
for(k = 0;k < e;k++)
{//读入e条边，建立邻接矩阵
scanf(%d%d%d，&i，&j，&w); //输入边(v i ,v j )上的权w
G->edges[j]=w;
G->edges[j]=w;
}
}//CreateMGraph
该算法的执行时间是0(n+n 2 +e)。由于e
根据图的定义可知，图的逻辑结构分为两部分：V和E的集合。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，称这个二维数组为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。
④ 已知有向图的邻接表存储结构如下图所示
深度优先是从某个顶点出发，访问完后，寻找一个未访问的邻接顶点继续深度优先，如果此路不同就往回退，所以看邻接表，首先访问V1，完了后顺链寻找没有访问的邻接顶点，自然链表中的第一个结点就是v3，接着转到v3再来深度优先，访问v3后，在其链表中第一个邻接顶点是v4
接着访问v4，下面走不通，回到v3，继续顺链往后，自然是v5，v5的邻接顶点中v2还没有访问
所以序列为v1, v3, v4, v5, v2
再看广度优先，从某个顶点完成后，需要一口气将其邻接未访问的所有顶点都访问，后面类推
于是过程是先v1，再顺链将v3，v2依次访问完，然后再依次访问v3和v2的各个未访问邻接顶点，v3链表中顺链可以访问v4，v5，所以最后访问序列为v1, v3, v2, v4, v5
⑤ 请编写一个完整的程序，建立有向图的邻接表存储结构，要求：
给你一个邻接表的完整程序：
#include <iostream.h>
struct node
{
int data;
node *next;
};
class list
{
public:
list(){head=NULL;};
void MakeEmpty();
int Length();
void Insert(int x,int i);//将x插入到第i个结点（不含头结点）的之后
void Insertlist(int a,int b);//将节点b插入a之前
int Delete(int x);
int Remove(int i);
int Find(int x);
void Display();
private:
node *head;
};
void list::Display()
{
node *current=head;
while (current!=NULL)
{
cout<<current->data<<" ";
current=current->next;
}
cout<<endl;
}
void list::MakeEmpty()
{
head=NULL;
}
int list::Length()
{int n=1;
node *q=head;
if(q==NULL)
n=1;
else
while(q!=NULL)
{
n++;
q=q->next;
}
return n;
}
int list::Find(int x)//在链表中查找数值为x的结点，成功返回1，否则返回0
{
node *p=head;
while(p!=NULL&&p->data!=x)
p=p->next;
if(p->data==x)
return 1;
else
return 0;
}
void list::Insert (int x,int i)//将x插入到第i个结点（不含头结点）的之后；
{
node *p;//p中放第i个结点
node *q;//q中放i后的结点
node *h;//h中存要插入的结点
h=new node;
h->data =x;
p=head;
if(p->next !=NULL) //链表不是只有一个结点或者空链表时候
{
int n=1;
while(p->next !=NULL)
{
n++;
p=p->next ;
}// 得到链表的结点的个数
p=head;//使p重新等于链首
if(i==n)//i=n时，直接加在最后面就行了
{
while(p->next !=NULL)
p=p->next;
p->next=h;
h->next =NULL;
}
else if(i<n&&i>1)//先找到第i个结点，用p存第i个结点，用q存i后的结点，用h存要插入的结点
{
for(int j=1;j<i;j++)
p=p->next;//找到第i个结点，用p存第i个结点
q=p->next;//q存i后的结点
p->next=h;
h->next=q;
}
else
cout<<"超出链表结点个数的范围"<<endl;
}
else
cout<<"这个链表是空链表或者结点位置在首位"<<endl;
}
void list::Insertlist(int a,int b)//将b插入到结点为a之前
{
node *p,*q,*s;//p所指向的结点为a,s所指为要插入的数b,q所指向的是a前的结点
s=new node;
s->data=b;
p=head;
if(head==NULL)//空链表的时候
{
head=s;
s->next=NULL;
}
else
if(p->data==a)//a在链首时候
{
s->next=p;
head=s;
}
else
{
while(p->data!=a&&p->next!=NULL)//使p指向结点a,q指向a之前的结点
{
q=p;
p=p->next;
}
if(p->data==a)//若有结点a时候
{
q->next=s;
s->next=p;
}
else//没有a的时候
{
p->next=s;
s->next=NULL;
}
}
}
int list::Delete(int x)//删除链表中值为x的结点，成功返回1，否则返回0；
{
node *p,*q;
p=head;
if(p==NULL)
return 0;
if(p->data==x)
{
head=p->next;
delete p;
return 1;
}
else
{
while(p->data!=x&&p->next!=NULL)
{ q=p;
p=p->next;
}
if(p->data==x)
{
q->next =p->next;
delete p;
return 1;
}
else
return 0;
}
}
int list::Remove(int i)
{
node *p,*q;
p=head;
if(p!=NULL)
{ int n=1;
while(p->next !=NULL)
{
n++;
p=p->next ;
}//得到链表结点的个数
p=head;
if(i==n)//i结点在结尾的时候
{
while(p->next!=NULL)
{
q=p;
p=p->next;
}
q->next=NULL;
delete p;
return 1;
}
else if(i<n&&i>1)//i结点在中间的时候
{
for(int j=1;j<i;j++)
{
q=p;//q中放i前的结点
p=p->next ;//p中放第i个结点
}
q->next=p->next;
delete p;
return 1;
}
else if(i==1)//i结点在首位的时候
{
q=p->next;
head=q;
delete p;
return 1;
}
else
return 0;
}
else
return 0;
}
void main()
{
list A;
int data[10]={1,2,3,4,5,6,7,8,9,10};
A.Insertlist(0,data[0]);
for(int i=1;i<10;i++)
A.Insertlist(0,data[i]);
A.Display();
menu:cout<<"1.遍历链表"<<'\t'<<"2.查找链表"<<'\t'<<"3.插入链表"<<endl;
cout<<"4.删除链表"<<'\t'<<"5.链表长度"<<'\t'<<"6.置空链表"<<endl;
int m;
do
{
cout<<"请输入你想要进行的操作（选择对应操作前面的序号）："<<endl;
cin>>m;
}while(m<1||m>6);//当输入的序号不在包括中，让他重新输入
switch(m)
{
case 1:
{
A.Display ();
goto menu;
};break;
case 2:
{
cout<<"请输入你想要找到的结点："<<endl;
int c;
cin>>c;//输入你想要找到的结点
if(A.Find (c)==1)
{
cout<<"可以找到"<<c<<endl;
A.Display ();//重新显示出链表A
}
else
{
cout<<"链表中不存在"<<c<<endl;
A.Display ();//重新显示出链表A
}
goto menu;
};break;
case 3:
{
cout<<"请选择你要插入的方式(选择前面的序号进行选择）"<<endl;
cout<<"1.将特定的结点加入到特定的结点前"<<'\t'<<"2.将特定的结点加到特定的位置后"<<endl;
int b1;
do
{
cout<<"请输入你想要插入的方式（选择前面的序号进行选择）："<<endl;
cin>>b1;
}while(b1<1||b1>2);//当输入的序号不在包括中，让他重新输入
if(b1==1)
{
cout<<"请输入你想要插入的数和想要插入的结点（为此结点之前插入）："<<endl;
int a1,a2;
cin>>a1>>a2;
A.Insertlist (a1,a2);//将a1插入到结点为a2结点之前
cout<<"此时链表为："<<endl;
A.Display ();//重新显示出链表A
}
else
{
cout<<"请输入你想要插入的数和想要插入的位置（为此结点之后插入）："<<endl;
int a1,a2;
cin>>a1>>a2;
A.Insert (a1,a2);//将a1插入到结点位置为a2的结点之后
cout<<"此时链表为："<<endl;
A.Display ();//重新显示出链表A
}
goto menu;
};break;
case 4:
{
cout<<"请选择你要删除的方式(选择前面的序号进行选择）"<<endl;
cout<<"1.删除特定的结点"<<'\t'<<"2.删除特定位置的结点"<<endl;
int b1;
do
{
cout<<"请输入你想要插入的方式（选择前面的序号进行选择）："<<endl;
cin>>b1;
}while(b1<1||b1>2);//当输入的序号不在包括中，让他重新输入
if(b1==1)
{
cout<<"请输入你想要删除的结点："<<endl;
int a;
cin>>a;//输入你想要删除的结点
if(A.Delete (a)==1)
{
cout<<"成功删除"<<a<<endl;
cout<<"删除后的链表为："<<endl;
A.Display ();
}
else
{
cout<<"此链表为："<<endl;
A.Display ();//重新显示出链表A
cout<<"链表中不存在"<<a<<endl;
}
}
else
{
cout<<"请输入你想要删除的结点位置："<<endl;
int b;
cin>>b;//输入你想要删除的结点的位置
if(A.Remove(b)==1)
{
cout<<"成功删除第"<<b<<"个结点"<<endl;
cout<<"删除后的链表为："<<endl;
A.Display ();//重新显示出链表A
}
else
{
cout<<"当前链表的结点个数为："<<A.Length ()<<endl;
cout<<"您输入的结点位置越界"<<endl;
}
}
goto menu;
};break;
case 5:
{
cout<<"这个链表的结点数为:"<<A.Length ()<<endl;
goto menu;
};break;
case 6:
{
A.MakeEmpty ();
cout<<"这个链表已经被置空"<<endl;
goto menu;
};break;
}
}
评论(3)|1
sunnyfulin |六级采纳率46%
擅长：C/C++JAVA相关Windows数据结构及算法网络其它产品
按默认排序|按时间排序
其他1条回答
2012-04-23 17:41121446881|六级
我写了一个C语言的，只给你两个结构体和一个初始化函数：
#include "stdio.h"
#include "malloc.h"
struct adjacentnext//邻接表项结构体
{
int element;
int quanvalue;
struct adjacentnext *next;
};
struct adjacenthead//邻接表头结构体
{
char flag;
int curvalue;
int element;
struct adjacenthead *previous;
struct adjacentnext *son;
};
//初始化图，用邻接表实现
struct adjacenthead *mapinitialnize(int mapsize)
{
struct adjacenthead *ahlists=NULL;
struct adjacentnext *newnode=NULL;
int i;
int x,y,z;
ahlists=malloc(sizeof(struct adjacenthead)*mapsize);
if(ahlists==NULL)
return NULL;
for(i=0;i<mapsize;i++)
{
ahlists[i].curvalue=0;
ahlists[i].flag=0;
ahlists[i].previous=NULL;
ahlists[i].son=NULL;
ahlists[i].element=i+1;
}
scanf("%d%d%d",&x,&y,&z);//输入源结点，目的结点，以及源结点到目的结点的路权值
while(x!=0&&y!=0)//x,y至少有一个零就结束
{
newnode=malloc(sizeof(struct adjacentnext));
newnode->element=y;
newnode->quanvalue=z;
newnode->next=ahlists[x-1].son;
ahlists[x-1].son=newnode;
scanf("%d%d%d",&x,&y,&z);
}
return ahlists;//返回邻接表头
}
⑥ 求！！！设有向图的存储结构为邻接表,试定义邻接表的结构,并编写算法计算给定有向图中指定顶点的出度。
有个模板，可以参考一下嘛
http://wenku..com/view/2ed5c337ccbff121dd368383?fr=prin
⑦ 有向图的邻接矩阵存储
有向图的邻接矩阵，用类似于二维链表做过，下面是c++的代码：
//顶点结构
structVexNode
{
chardata;
ArcNode*firstarc;
};
//弧结构
structArcNode
{//邻接顶点的下标
intadjvex;
ArcNode*nextarc;
};
classAdjList
{
private:
VexNodedata[100];
intvn,an;//顶点数弧数
public:
//构造函数以及其他的一些函数
AdjList();
virtual~AdjList();
};
⑧ 已知带权有向图如图所示,画出该图的邻接矩阵存储结构.
∞ 2 ∞ 6 ∞ 9 ∞ ∞
∞ ∞ 30 1 ∞ ∞ ∞ ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ 5
∞ ∞ ∞ ∞ 2 ∞ ∞ ∞
∞ ∞ 8 ∞ ∞ ∞ 7 ∞
∞ ∞ ∞ ∞ 3 ∞ 24 ∞
∞ ∞ ∞ ∞ ∞ ∞ ∞ 21
∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞