如何根据点之间距离的远近建立无向图的邻接矩阵

二者的区别：
邻接矩阵（Adjacency Matrix）：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：
①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
②在无向图中，任一顶点i的度为第i列所有元素的和，在有向图中顶点i的出度为第i行所有元素的和，而入度为第i列所有元素的和。
③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。

1代表有边,0代表没有边(第i行第j列若是1,则顶点i到j有边,表示:i->j),所以:
0 ->1->2
1 ->3
2 ->3
3 ->0->4
4 ->1->3
另外,其中的顺序是可以任意的:如
0 ->2->1也行!

第一步 整理excel数据表

这里需要把原始数据处理成标准NN的矩阵，可以只填写上三角（或者下三角），这样画出的表示有向图，填写为对称矩阵则“表示”无向图，所谓无向图也即是任一连线都带箭头（看到这没学过图论的可能有点晕）。

看个例子，解释一下就清楚了：

部分是下三角，橙色部分是上三角，绿色部分是标题行，蓝色是对角线。

解释上图，矩阵的数值，简单的说可以表示张三跟李四借了钱（从左起，三行二列为1），张三后来又把钱还给了李四（从左起，二行三列为1），以此类推。

如上图表示的是对称矩阵，矩阵里的值可以为0-1（表示有关系或没关系，即借了或没借，若为0也可不填），或者任意实数（表示产生关系的次数或者上面例子中借的金额数）。

第二步 导入excel数据。

保存就是菜单view下面那个磁盘的图标拉。

第三步 二值化（这一步是可选的）

上面说了，矩阵的数值可以是0-1，也可以是任意实数，那么这一步就是要把实数矩阵转成0-1矩阵，也就是把定量问题定性考虑

举个例子，张三借给李四多少钱算借钱呢，好吧，10块钱以上算借钱，那就让ucinet帮你把矩阵里10以上（以上、以下、等于都是可以自己设定的，这里以“以上”为例）的数值都改成1，10以下的数值就无视掉（变0）

下图中的10表示表中大于10的都换为1，否则为0，cut-off operator即规则，Greater Than就是大于。点ok后选择保存地点，得到一个处理后的#h文件。

第四步，用netdraw画图

导入第三步或者第二步得到的#h文件，OK。

最后是结果的实例了，但需要说明的是得到的图的节点大小，连线长度等属性本无意义，但是可以用ANALYSIS里的各种分析重画图，赋予这些属性新的意义，例如下图是中心性分析得到的结果，节点的大小表示中心性，点越大越是中心，如图，图书馆处于所有关键词的中心。

第五步 把图进一步处理，让图“更漂亮”。

//Floyed 实现赋权无向图定点对间的最短路径，时间复杂度O(n^3)
1，从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
#include<stdioh>
int main()
{
int c[20][20],parth[20][20],i,j,k,t1,t2,t3,n,x,y,re;
printf("输入图的顶点数:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=i+1;j<=n;j++)
{
printf("输入边(%d,%d)的权值,若不存在输入10000:",i,j);
scanf("%d",&c[i][j]);
}
}
如果是有向图就删掉这里"//for(i=1;i<=n;i++)
//{
///////////////////////////////////////for(j=1;j<=i;j++)
////////////////////////////////////////c[i][j]=c[j][i];
/////////////////////////////////////////}"
for(i=1;i<=n;i++)
c[i][i]=0;//自己到自己的权值为0
for(i=1;i<=n;i++) //初始化路径
{
for(j=1;j<=n;j++)
parth[i][j]=0;
}
for(k=1;k<=n;k++)//k是中间节点，i是起点j是中点。其实就是枚举中间节点，来求i j 的最短路径
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
t1=c[i][k];
t2=c[k][j];
t3=c[i][j];
if(t1!=10000&&t2!=10000&&(t3==10000||t1+t2<t3)) //松弛 覆盖原来的最短路
{c[i][j]=t1+t2,parth[i][j]=k;}//记录i j的中间点是k
}
}
}
while(1)//也可以用递归的形式输出parth
{
printf("输入2点:");
scanf("%d%d",&x,&y);
printf("最短距离为%d\n",c[x][y]);
printf("%d ",x);
re=y;
while(parth[x][y]!=0)
{
printf("%d ",parth[x][y]);
y=parth[x][y];
}
printf("%d\n",re);
}
return 0;
}

这是用邻接表创建的一个图
实现了广度和深度遍历
希望能帮助你
#include <iostream>
using namespace std;
#define MaxSize 50
struct ArcNode // 保存结点后面的所连边对应的点
{
int adjvex;
struct ArcNode nextarc;
};
// 用来存放一个节点的结构体,存放首节点,后面定义的是一个结构体数组
struct Vnode
{
int data;
struct ArcNode firstarc;
};
int m,n,v;
void creatgraph(struct Vnode A[MaxSize]); // 创建图
void dfs(struct Vnode A[MaxSize]); // 深搜
void bfs(struct Vnode A[MaxSize]); // 广搜
int main()
{
struct Vnode AdjList[MaxSize];
int cord;
do
{
cout<<" 主菜单"<<endl;
cout<<" 1 建立无向图的邻接表"<<endl;
cout<<" 2 按深度遍历图"<<endl;
cout<<" 3 按广度遍历图"<<endl;
cout<<" 4 结束程序运行"<<endl;
cout<<"------------------------------"<<endl;
cout<<" 请输入你的选择1 ,2 ,3 ,4:"<<endl;
cin>>cord;
switch(cord)
{
case 1:creatgraph(AdjList);break;
case 2:dfs(AdjList);break;
case 3:bfs(AdjList);break;
case 4:exit(0);
}
}while(cord <= 4);

return 0;
}
void creatgraph(struct Vnode A[MaxSize]) //创建图
{
int i,j,k;
struct ArcNode p;
cout<<" 输入边和点的个数:"<<endl;
cin>>m>>n; // m代表边的个数 ，n代表顶点个数
for(k=0;k<n;k++) // 首先对邻接表的所有顶点初始化
{
A[k]data = k+1;
A[k]firstarc = NULL;
}

for (k=0;k<m;k++) // 输入边,并插入到邻接表
{
cout<<" input arc:"<<endl;
cin>>i>>j; // 这代表一条无向边,顶点i与顶点j相连
p = (struct ArcNode )malloc(sizeof(struct ArcNode));
p->adjvex = j;
p->nextarc = A[i-1]firstarc;
A[i-1]firstarc=p;

p = (struct ArcNode )malloc(sizeof(struct ArcNode));
p->adjvex = i;
p->nextarc = A[j-1]firstarc;
A[j-1]firstarc=p;
}
cout<<endl;
for(k=0;k<n;k++) // 输出邻接表
{
cout<<" vex"<<A[k]data<<" arc is:";
p=A[k]firstarc;
while(p)
{
cout<<p->adjvex<<" ";
p=p->nextarc;
}
cout<<endl;
}
}
void dfs(struct Vnode A[MaxSize])
{
struct ArcNode p, ar[MaxSize];
int x,i,y,top=-1;
int visited[MaxSize];

for(i = 0 ; i < n ; i++) visited[i] = 0; // 这个数组用于代表这个节点是否被遍历过

cout<<"input x of start vex"<<endl;
cin>>x; // 输入从哪个节点开始遍历
cout<<x;

visited[x-1]=1; // 首先根节点被发现
p=A[x-1]firstarc; // 然后要遍历的是根节点的邻接点
while( (p) || top>=0) // 直到栈为空,并且没有邻接点就退出循环
{
if(!p) // 出栈
{
p = ar[top];
top--;
}

y = p->adjvex;

if(visited[y-1] == 0)
{
visited[y-1] = 1; // 被发现
cout<<" -> "<<y;
p = p->nextarc;
if(p) {top++;ar[top] = p;} // 入栈
p=A[y-1]firstarc;
}
else
p=p->nextarc;
}
}
void bfs(struct Vnode A[MaxSize])
{
struct ArcNode p;
int x,i,y,front=-1,rear=-1,ar[MaxSize],visited[MaxSize];

for(i=0;i<n;i++) // 这个数组用于代表这个节点是否被遍历过
visited[i]=0;

cout<<"input x"<<endl;
cin>>x; // 代表从哪个节点开始遍历
cout<<x;

visited[x-1]=1; //代表x的结点被发现
p=A[x-1]firstarc; // x被发现之后就遍历x的邻接点
while( (p) || (front!=rear)) // 如果队列为空,并且这个结点没有了邻接点则退出循环
{

if (!p) // 这个当p的邻接点全部入队之后进入这句
{
front++; //队列的队首元素的下标往下偏移
y=ar[front]; //首先y出队,即去队首元素
p=A[y-1]firstarc; //之后就要遍历y的邻接点了
}

y=p->adjvex; //取p的数据域
if(visited[y-1] == 0)
{
visited[y-1]=1;
cout<<" -> "<<y;
rear++; //把p的邻接点全部入队,知道遍历到p没有邻接点为止
ar[rear]=y;
}
p=p->nextarc;
}
}

有向图在图中的边是有方向的，表现出来就是有个箭头指示方向，节点只能单向通信或传递消息，相当于单行道，无向图边没方向是双向的，边连接的两个节点有通路可以双向通信，类似于双行道。

无向图，边没有方向的图称为无向图。邻接矩阵则是对称的，且只有0和1，因为没有方向的区别后，要么有边，要么没边。

有向图，一个有向图D是指一个有序三元组(V(D)，A(D)，ψD)，其中ψD为关联函数，它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。

扩展资料：

的G2和(c)图中的G3均是无向图，它们的顶点集和边集分别为：

V(G2)={v1，v2，v3，v4}

E(G2)={(vl，v2)，(v1，v3)，(v1，v4)，(v2，v3)，(v2，v4)，(v3，v4)}

V(G3)={v1，v2，v3，v4，v5，v6，v7}

E(G3)={(v1，v2)，(vl，v3)，(v2，v4)，(v2，v5)，(v3，v6)，(v3，v7)}

参考资料来源：百度百科-无向图

int nodeNum=10;//顶点数
int tu[nodeNum][nodeNum]={0};//初始化邻接矩阵
while(次数条件){
//随机生成有连接的顶点标号
int nodeBegin=random();
int nodeEnd=random();
//双向连接，实现无向
tu[nodeBegin][nodeEnd]=1;
tu[nodeEnd][nodeBegin]=1;
}

数组
v1 v2 v3 v4 v5 v6
v1 0 1 0 0 1 1
v2 0 1 1 0 0 1
v3 0 1 0 1 0 0
v4 0 0 1 0 0 1
v5 0 1 0 0 0 1
v6 1 1 0 1 1 0
邻接表
v1->v2,v5,v6
v2->v1,v3,v6
v3->v2,v4
v4->v3,v6
v5->v1,v6
v6->v1,v2,v4,v5

---