‘壹’ OD矩阵和邻接矩阵是一回事么
这是图论的知识，OD矩阵是图顶点的出度的矩阵 图的邻接矩阵如下介绍 1．图的邻接矩阵表示法 在图的邻接矩阵表示法中： ① 用邻接矩阵表示顶点间的相邻关系 ② 用一个顺序表来存储顶点信息 2．图的邻接矩阵(Adacency Matrix) 设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵： 【例】下图中无向图G 5 和有向图G 6 的邻接矩阵分别为A l 和A 2 。 从图的邻接矩阵表示法中可以得到如下结论： （1）对于n个顶点的无向图，有A（i，i）=0，1≤i≤n。 （2）无向图的邻接矩阵是对称的，即A（i，j）=A（j，i），1≤i≤n，1≤j≤n。 （3）有向图的邻接矩阵不一定对称的。因此用邻接矩阵来表示一个具有n个顶点的有向图时需要n 2 个单位来存储邻接矩阵；对有n个顶点的无向图则需存入上（下）三角形，故只需n（n+1）/2个单位。 （4）无向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度TD（v i ）。 （5）有向图的邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的出度OD（v i ）[或入度ID（v i ）]。 3．网（带权值的图）的邻接矩阵 若G是网络，则邻接矩阵可定义为： 其中： w ij 表示边上的权值； ∞表示一个计算机允许的、大于所有边上权值的数。 【例】下面(a)是一个带权图，（b）是对应的邻接矩阵的存储结构 （a）带权图 （b）邻接矩阵 4．邻接矩阵的图类 const int MaxVertices=10; const int MaxWeight=32767; class AdjMWGraph { private: int Vertices[10]; //顶点信息的数组 int Edge[MaxVertices][MaxVertices]; //边的权值信息的矩阵 int numE; //当前的边数 int numV; //当前的顶点数 public: ………; //公有函数 private: ………; //私有函数 } 注意： ① 在简单应用中，可直接用二维数组作为图的邻接矩阵（顶点表及顶点数等均可省略）。 ② 当邻接矩阵中的元素仅表示相应的边是否存在时，EdgeTyPe可定义为值为0和1的枚举类型。 ③ 无向图的邻接矩阵是对称矩阵，对规模特大的邻接矩阵可压缩存储。 ④ 邻接矩阵表示法的空间复杂度S(n)=0(n 2 )。
‘贰’ 设计一个采用邻接矩阵存储结构的图类MGraph及深度优先遍历非递归算法。
你是要整个代码还是要关键程序段？
我这边的程序接口你也许不能用。
请详细说明。
‘叁’ c/c++图的邻接矩阵存储结构
关于图的深度优先遍历代码如下：
#include <stdio.h>
#include <stdlib.h>
#define FALSE 0
#define TURE 1
#define OK 1
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef struct ArcCell{
int adj; //顶点关系类型。用1或0表示相邻与否
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //二维数组
typedef struct {
char vexs[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //顶点数和弧数
}MGraph;
int LocateVex(MGraph G,char u)
{ //若图G中存在顶点u，则返回该顶点在图中的位置；否则返回-1
int i;
for(i=0;i<G.vexnum;i++)
if(G.vexs[i]==u)
return i;
else return -1;
}
int CreateDG(MGraph G){ //构造有向图G
int i,j,k;
char va,vb;
printf("请输入有向图G的顶点数 弧数：");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请输入%d个顶点的值(<5个字符)：\n",G.vexnum);
for(i=0;i<G.vexnum;i++) scanf("%s",&G.vexs[i]); //构造顶点向量
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
{
G.arcs[i][j].adj=0;
}
printf("请输入%d条弧的弧尾 弧头：\n",G.arcnum);
for(k=0;k<G.arcnum;++k)
{
scanf("%s%s%*c",&va,&vb);
i=LocateVex(G,va);
j=LocateVex(G,vb);
G.arcs[i][j].adj=1;
}
return OK;
}
int FirstAdjVex(MGraph G,char v)
{ //返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1
int i,k;
k=LocateVex(G,v); //k为顶点v在图G中的序号
for(i=0;i<G.vexnum;i++)
if(G.arcs[k][i].adj!=0)
return i;
else return -1;
return OK;
}
int NextAdjVex(MGraph G,char v,char w)
{ //返回v的相对于（w）的下一个邻接顶点的序号，若w是v的最后一个邻接顶点，则返回-1
int i,k1,k2;
k1=LocateVex(G,v); //k1为顶点v在图G中的序号
k2=LocateVex(G,w); //k2为顶点w在图G中的序号
for(i=k2+1;i<G.vexnum;i++)
if(G.arcs[k1][i].adj!=0)
return i;
else return -1;
return OK;
}
int visited[MAX_VERTEX_NUM];
int DFS(MGraph G,int v)
{ //从第v个顶点出发递归的深度优先遍历图G
int w;
visited[v]=TURE; //设置访问标志为TURE
printf("%s",G.vexs[v]);
for(w=FirstAdjVex(G,G.vexs[v]);w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w]))
if(!visited[w])
DFS(G,w); //对尚未访问的序号为w的邻接顶点递归的调用DFS
return OK;
}
int DFSTraverse(MGraph G)
{ //从第一个顶点起，深度优先遍历图G
int v;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; //访问标志数组初始化
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); //对尚未访问的顶点v调用DFS
printf("\n");
return OK;
}
int main()
{
MGraph G;
CreateDG(G);
DFSTraverse(G);
system("pause");
return OK;
}
广度可以自己参照改写。。
‘肆’ 邻接矩阵vex是什么意思
typedef char VertexType[MAX_NAME];
。。。。。
2. typedef struct
3. {
4. VertexType vexs[MAX_VERTEX_NUM]; // 顶点向量
5. AdjMatrix arcs; // 邻接矩阵
6. int vexnum,arcnum; // 图的当前顶点数和弧数
7. GraphKind kind; // 图的种类标志
8. } MGraph;
。。。。。。
9.
10. VertexType *GetVex(MGraph G,int v)
11. {
12. // 初始条件: 图G存在，v是G中某个顶点的序号。操作结果: 返回v的值
13. if(v>=G.vexnum||v<0)
14. exit(ERROR);
15. return G.vexs[v];
16. }
17. int main()
18. {
19. .
20. printf("%s ",*GetVex(G,v));
21. ..
22. }
编译执行时，提示“15行：warning: function returns address of local variable”，执行时到这个函数就卡住了，问一下怎么修改？
‘伍’ 在线急求熟悉图的两种常用的存储结构，邻接矩阵和邻接表。
#include<stdio.h>
#include<malloc.h>
#define NULL 0
#define maxvernum 100
typedef struct node
{
int adjvex;
struct node *next;
}nodetype;
typedef struct frontnode
{
int data;
struct node *next;
}frontnodetype;
frontnodetype adjlist[maxvernum];
/*********************************************/
void main()
{
void bfs(frontnodetype g[],int v,int c[]);
void travelgraph(frontnodetype g[],int n);
frontnodetype adjlist[6];
int i,j,m;
for(i=1;i<=5;i++)
{
adjlist[i].data=i;
adjlist[i].next=NULL;
}
for(j=1;j<=5;j++)
{
printf("进入第%d次循环\n",j);
printf("开始输入前请输入一个不为0的m值以便输入\n");
scanf("%d",&m);
while(m!=0)
{
int x;
printf("请输入结点序号（x=0表示后面没有结点）：\n");
if(x!=0)
{
scanf("%d",&x);
nodetype *p;
p=(nodetype *)malloc(sizeof(nodetype));
p->adjvex=x;p->next=NULL;
p->next=adjlist[j].next;
adjlist[j].next=p;
}
else break;
printf("是否停止？（m为0时停止输入，m为1时继续输入。）\n");
scanf("%d",&m);
}
}
printf("广度优先搜索序列为：\n");
travelgraph(adjlist,5);
}
/************************************************/
void bfs(frontnodetype g[],int v,int c[])
{
int q[6],r=0,f=0;
nodetype *p;
c[v]=1;
printf("%d\n",v);
q[0]=v;
whille(f<=r)
{
v=q[f++];
p=g[v].next;
while(p!=NNLL)
{
v=p->adjvex;
if(c[v]==0)
{
c[v]=1;
printf("%d\n",v);
}
p=p->next;
}
}
}
/************************************************/
void travelgraph(frontnodetype g[],int n)
{
int v;
int c[6];
for(v=1;v<=n;v++)
c[v]=0;
for(v=1;v<=n;v++)
if(c[v]==0)
dfs(g,v,c);
}
‘陆’ 图的邻接矩阵和邻接表的存储结构各有什么特点
图的邻接表数据类型描述如下：
const int N=maxn； // maxn表示图中最大顶点数
const int E=maxe ； // maxe图中最大边数
struct Edge{
int u,v; //边所邻接的两个顶点
int w; //边的权值
int next; //边指针，指向下一条边的内存池地址
}edge[E]; // 静态内存池，用于分配边
int head[N]; // 表头
int num; // 内存池的指针
‘柒’ 图的存储结构——所存储的信息有哪些
一、邻接矩阵存储方法
邻接矩阵是表示顶点之间相邻关系的矩阵。
设G=(V，E)是具有n（n＞0）个顶点的图，顶点的顺序依次为0～n-1，则G的邻接矩阵A是n阶方阵，其定义如下：
（1）如果G是无向图，则：
A[i][j]=1：若(i,j)∈E(G) 0:其他
（2）如果G是有向图，则：
A[i][j]=1：若<i,j>∈E(G) 0:其他
（3）如果G是带权无向图，则：
A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他
（4）如果G是带权有向图，则：
A[i][j]= wij ：若i≠j且<i,j>∈E(G) 0：i=j∞：其他
注意：带权图和不带权图表示的元素类型不同。
带权图（不论有向还是无向图）A[i][j]用double表示，不带权图（不论有向还是无向图）A[i][j]用int表示。
用一维数组G[ ]存储有4个顶点的无向图如：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
则顶点2和顶点0之间是有边的。
如：
邻接矩阵的特点如下：
（1）图的邻接矩阵表示是唯一的。
（2）无向图的邻接矩阵一定是一个对称矩阵。因此，按照压缩存储的思想，在具体存放邻接矩阵时只需存放上（或下）三角形阵的元素即可。
（3）不带权的有向图的邻接矩阵一般来说是一个稀疏矩阵。因此，当图的顶点较多时，可以采用三元组表的方法存储邻接矩阵。
（4）对于无向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的度。
（5）对于有向图，邻接矩阵的第i行（或第i列）非零元素（或非∞元素）的个数正好是第i个顶点的出度（或入度）。
（6）用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是用邻接矩阵存储图的局限性。
邻接矩阵的数据类型定义如下：
#define MAXV <最大顶点个数>
typedef struct
{ int no; //顶点编号
InfoType info; //顶点其他信息
} VertexType; //顶点类型
typedef struct //图的定义
{ int edges[MAXV][MAXV]; //邻接矩阵
int n，e; //顶点数，弧数
VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵表示类型
二、 邻接表存储方法
图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。
在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的节点表示依附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链表上附设一个表头节点。
其中，表节点由三个域组成，adjvex指示与顶点i邻接的点在图中的位置，nextarc指示下一条边或弧的节点，info存储与边或弧相关的信息，如权值等。
表头节点由两个域组成，data存储顶点i的名称或其他信息，firstarc指向链表中第一个节点。
typedef struct ANode
{ int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
InfoType info; //该边的相关信息
} ArcNode; //边表节点类型
typedef struct Vnode
{ Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
} VNode; //邻接表头节点类型
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct
{ AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} ALGraph; //完整的图邻接表类型
邻接表的特点如下：
（1）邻接表表示不唯一。这是因为在每个顶点对应的单链表中，各边节点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。
（2）对于有n个顶点和e条边的无向图，其邻接表有n个顶点节点和2e个边节点。显然，在总的边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间。
（3）对于无向图，邻接表的顶点i对应的第i个链表的边节点数目正好是顶点i的度。
（4）对于有向图，邻接表的顶点i对应的第i个链表的边节点数目仅仅是顶点i的出度。其入度为邻接表中所有adjvex域值为i的边节点数目。
例， 给定一个具有n个节点的无向图的邻接矩阵和邻接表。
（1）设计一个将邻接矩阵转换为邻接表的算法；
（2）设计一个将邻接表转换为邻接矩阵的算法；
（3）分析上述两个算法的时间复杂度。
解：
（1）在邻接矩阵上查找值不为0的元素，找到这样的元素后创建一个表节点并在邻接表对应的单链表中采用前插法插入该节点。
void MatToList(MGraph g，ALGraph *&G)
//将邻接矩阵g转换成邻接表G
{ int i，j，n=g.n; ArcNode *p; //n为顶点数
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;i<n;i++) //给所有头节点的指针域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<n;i++) //检查邻接矩阵中每个元素
for (j=n-1;j>=0;j--)
if (g.edges[i][j]!=0)
{ p=(ArcNode *)malloc(sizeof(ArcNode));
//创建节点*p
p->adjvex=j;
p->nextarc=G->adjlist[i].firstarc;
//将*p链到链表头
G->adjlist[i].firstarc=p;
}
G->n=n;G->e=g.e;
}
（2）在邻接表上查找相邻节点，找到后修改相应邻接矩阵元素的值。
void ListToMat(ALGraph *G，MGraph &g)
{ int i，j，n=G->n;ArcNode *p;
for (i=0;i<n;i++)
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ g.edges[i][p->adjvex]=1;
p=p->nextarc;
}
}
g.n=n;g.e=G->e;
}
（3）算法1的时间复杂度均为O(n2)。算法2的时间复杂度为O(n+e)，其中e为图的边数。
‘捌’ 有向图的邻接矩阵存储
有向图的邻接矩阵，用类似于二维链表做过，下面是c++的代码：
//顶点结构
structVexNode
{
chardata;
ArcNode*firstarc;
};
//弧结构
structArcNode
{//邻接顶点的下标
intadjvex;
ArcNode*nextarc;
};
classAdjList
{
private:
VexNodedata[100];
intvn,an;//顶点数弧数
public:
//构造函数以及其他的一些函数
AdjList();
virtual~AdjList();
};
‘玖’ 试以邻接矩阵为存储结构，写出连通图的深度优先搜索算法。
/* MGraph.cc: 图的邻接矩阵存储表示和实现 */
/* 包含图类型Graph定义；创建图；深度优先遍历；广度优先遍历 */
/* 用到引用型参数，在TC下无法通过编译，VC等C++编译器可通过 */
#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX
#define VType char //顶点值类型
#define EType int //边权值类型
#define MAXVNUM 50 //最大顶点个数
#define DIGRAPH 0 //有向图(网)
#define UNDIGRAPH 1 //无向图(网)
#define INVALID INT_MAX //无效权值(最大整数表示无穷大)
#define EMPTY -1 //"空"顶点序号
//定义邻接矩阵表示的图类型Graph:
typedef struct
{
VType v[MAXVNUM]; //顶点序列(顶点编号从0开始)
EType w[MAXVNUM][MAXVNUM]; //邻接矩阵
int vn, en; //顶点数,边数
int kind; //图的种类：=DIGRAPH表示有向图(网)，=UNDIGRAPH表示无向图(网)
}Graph;
int visited[MAXVNUM]; //访问标志数组(=1已访问，=0未访问)。遍历时用到的全局量。
/* 创建图G
参数Vex是存放顶点序列的数组
参数VVW是整数数组，以{Vi,Vj,Wij,...,-1}的形式依次存放各边的起止点序号(Vi,Vj)和权(Wij)，-1是数据结束标志
参数kind=DIGRAPH表示有向图(网)，=UNDIGRAPH表示无向图(网)
*/
void CreateGraph(Graph &G, VType *Vex, int VVW[], int kind)
{
int i, j, p, n, w;
n = strlen(Vex);
G.vn = n; //顶点数
G.kind = kind; //图的种类
//置顶点序列:
for (i = 0; i < n; i++)
G.v[i] = Vex[i];
//初始化邻接矩阵:
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
G.w[i][j] = INVALID;
//构造邻接矩阵:
p = 0; //VVW数组元素“指针”
n = 0; //边计数器
while (VVW[p] != -1)
{//只要p未到结束位置便继续:
i = VVW[p]; //边的起点序号
j = VVW[p + 1]; //边的终点序号
w = VVW[p + 2]; //边的权
G.w[i][j] = w; //置邻接矩阵的(i,j)位置元素
if (G.kind == UNDIGRAPH) //若是无向图(网),
G.w[j][i] = G.w[i][j]; //则置(i,j)的对称位置(j,i)
n++; //边计数器加1
p += 3; //p指向下一组(Vi,Vj,Wij)
}//end while
G.en = n; //边数
}//CreateGraph
/* 返回G中顶点i的一个未曾访问过的邻接点(序号) */
int NextAdjVex(Graph &G, int i)
{
int j, a;
a = EMPTY; //邻接点序号初始为"空"
//在邻接矩阵的第v行找有效元素：
for (j = 0; j < G.vn; j++)
{
if (G.w[i][j] == INVALID) //若当前元素是无效元素,
continue; //则继续找。
if (!visited[j])
{//若当前有效元素未曾访问过,则作为邻接点a:
a = j;
break;
}//end if
}//end for
return a;
}//NextAdjVex
/* 访问顶点i */
void visit(Graph &G, int i)
{
printf("%c", G.v[i]);
}//visit
/* 从第i个顶点出发深度优先遍历连通图G */
/* 调用DFS前可能需初始化数组visited[] */
void DFS(Graph &G, int i)
{int a;
visit(G, i); //访问i顶点
visited[i] = 1; //标注i顶点已访问
a = NextAdjVex(G, i); //找出一个i的邻接点a
while (a != EMPTY)
{//只要a存在便继续:
if (visited[a] == 0) //若a未曾访问,
DFS(G, a); //则从a出发继续进行深度优先遍历。
a = NextAdjVex(G, i); //找出i的下一个邻接点a
}//end while
}//DFS
/* 从第i个顶点出发深度优先遍历图G */
void DFSTrav(Graph &G, int i)
{int k;
//初始化各顶点的访问标志为0(未曾访问):
for (k = 0; k < G.vn; k++)
visited[k] = 0;
DFS(G, i); //从i出发遍历
//若G非连通图，执行一次DFS无法遍历所有顶点，还需用如下for对尚未访问的顶点DFS。
//若G是连通图，执行一次DFS就已遍历所有顶点，此时如下for什么也不做，因所有visited=1。
for (k = 0; k < G.vn; k++)
if (!visited[k]) DFS(G, k); //对尚未访问的顶点DFS
}//DFSTrav
//显示图的邻接矩阵
void ShowM(Graph &G)
{
int row, col, n;
n = G.vn; //顶点数
//以表格形式输出数组：
//输出表头：
printf(" ");
for(col = 0; col < n; col++)
printf("%3d",col);
printf("\n");
printf("---+");
for(col = 0; col < n; col++)
printf("---");
printf("\n");
//输出表体(矩阵元素)：
for(row = 0; row < n; row++)
{
printf("%3d|", row);
for(col = 0; col < n; col++)
{
if (G.w[row][col] == INVALID)
printf("%3c", '*');
else
printf("%3d", G.w[row][col]);
}//end for col
printf("\n");
}//end for row
printf("\n");
}//ShowM