在图的邻接矩阵表示法中：

① 用邻接矩阵表示顶点间的相邻关系

② 用一个顺序表来存储顶点信息

图的矩阵

设G=(V，E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：

【例】

下图中无向图G 5 和有向图G 6 的邻接矩阵分别为A l 和A 2 。

网络矩阵

若G是网络，则邻接矩阵可定义为：

其中：

w ij 表示边上的权值

∞表示一个计算机允许的、大于所有边上权值的数。

【例】下面带权图的两种邻接矩阵分别为A 3 和A 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 )。

⑤建立无向网络的算法。

void CreateMGraph(MGraph *G)

{//建立无向网的邻接矩阵表示

int i，j，k，w

scanf("%d%d"，&G->n，&G->e)//输入顶点数和边数

for(i = 0i <ni++) //读入顶点信息，建立顶点表

{

G->vexs=getchar()

}

for(i = 0i <G->ni++)

{

for(j = 0j <G->nj++)

{

G->edges[i][j] = 0//邻接矩阵初始化

}

}

for(k = 0k <G->ek++)

{//读入e条边，建立邻接矩阵

scanf("%d%d%d"，&i，&j，&w)//输入边(v i ,v j )上的权w

G->edges[i][j]=w

G->edges[j][i]=w

}

}//CreateMGraph

该算法的执行时间是0(n+n 2 +e)。由于e

根据图的定义可知，图的逻辑结构分为两部分：V和E的集合。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，称这个二维数组为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。

Matlab表达N=4//图中的节点数目

dag=zeros(N,N)//邻接矩阵初始化，值均为0

C=1S=2R=3

W=4//制定各节点编号

dag(C,[RS])=1//有两条有向边：C->R,C->S

dag(R,W)=1//有向边：R->W

dag(S,W)=1//有向边：S->W

图的遍历演示

以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历.

以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集.

*******************************************/

#include<iostream>

# include <string.h>

# include <malloc.h>

# include <conio.h>

using namespace std

int visited[30]

# define MAX_VERTEX_NUM 30

# define OK 1

//typedef int VertexType

typedef int InfoType

typedef struct ArcNode //弧

{

int adjvex

struct ArcNode *nextarc

}ArcNode

typedef struct VNode//表头

{

int data

ArcNode *firstarc

}VNode,AdjList[MAX_VERTEX_NUM]

typedef struct//图

{

AdjList vertices

int vexnum,arcnum

int kind

}ALGraph

void CreateDG(ALGraph &G)

{

int k,i,v1

cout<<endl<<"请输入结点个数: "

cin>>G.vexnum

cout<<"请输入弧的个数: "

cin>>G.arcnum

for(i=1i<=G.vexnumi++)//初使化表头

{

G.vertices[i].data=i

G.vertices[i].firstarc=NULL

}

for(k=1k<=G.vexnumk++) //输入边

{

int v2

cout<<"请输入与结点"<<k<<"相邻的边数:"

cin>>v2

cout<<"请输入与第"<<k<<"个结点相连的结点编号: "

cin>>v1

ArcNode *p

p=(ArcNode*)malloc(sizeof(ArcNode))

if(!p) exit(-1)

p->adjvex=v1

p->nextarc=NULL

G.vertices[k].firstarc=p

for(int i=1i<v2i++)

{

int m

cout<<"请输入与第"<<k<<"个结点相连的结点编号: "

cin>>m

ArcNode *q

q=(ArcNode *)malloc(sizeof(ArcNode))//动态指针

if(!q) exit(-1)

q->adjvex=m //顶点给P

q->nextarc=NULL

p->nextarc=q

p=q

//free(q)

}

//free(p)

}

}

void DFS (ALGraph G,int v )//深度搜索

{

visited[v]=1

cout<<G.vertices[v].data<<" "

ArcNode *x

x=(ArcNode*)malloc(sizeof(ArcNode))

if(!x) exit(-1)

x=G.vertices[v].firstarc

int w

for (xx=x->nextarc)

{ w=x->adjvex

if(visited[w]==0)

DFS(G,w)

}

}

void DFSB (ALGraph G,int v)//深度搜索的边集

{

visited[v]=1

ArcNode *y

y=(ArcNode*)malloc(sizeof(ArcNode))

if(!y) exit(-1)

y=G.vertices[v].firstarc

int u=G.vertices[v].data

int w

for(yy=y->nextarc)

{ w=y->adjvex

if(visited[w]==0)

{

cout<<u<<"--->"<<w<<endl

DFSB(G,w)

}

}

}

typedef struct QNode

{

int data

QNode *next

}QNode,*QueuePtr

typedef struct

{

QueuePtr front

QueuePtr rear

}LinkQueue

void InitQueue (LinkQueue &Q)//建立一个空队列

{

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))

if(!Q.front) exit(-1)

Q.front->next=NULL

}

void EnQueue (LinkQueue &Q,int e)//进队

{

QNode *p

p=(QNode*)malloc(sizeof(QNode))

if(!p) exit(-1)

p->data=e

p->next=NULL

Q.rear->next=p

Q.rear=p

//free(p)

}

int DeQueue (LinkQueue &Q,int &e)//出队

{

if(Q.front==Q.rear)

return -1

QNode *p

p=(QNode*)malloc(sizeof(QNode))

if(!p) exit(-1)

p=Q.front->next

e=p->data

Q.front->next=p->next

if(Q.rear==p)

Q.rear=Q.front

free(p)

return e

}

int QueueEmpty (LinkQueue Q)//判断队列是否为空

{

if(Q.front==Q.rear)

return 1

return 0

}

void BFS(ALGraph G,int v)//广度搜索

{

int u

LinkQueue Q

InitQueue(Q)

if(visited[v]==0)

{

visited[v]=1

cout<<G.vertices[v].data<<" "

EnQueue(Q,v)

while(QueueEmpty(Q)!=1)

{

DeQueue(Q,u)

ArcNode *z

z=(ArcNode*)malloc(sizeof(ArcNode))

if(!z) exit(-1)

z=G.vertices[u].firstarc

/*

for(int w=z->adjvexw>=0w=z->nextarc->adjvex)

{

if(visited[w]==0)

{

visited[w]=1

cout<<w<<" "

EnQueue(Q,w)

}

}*/

int w

for(zz=z->nextarc)

{ w=z->adjvex

if(visited[w]==0)

{

visited[w]=1

cout<<w<<" "

EnQueue(Q,w)

}

}

}

}

}

void BFSB (ALGraph G,int v)//广度搜索的边集

{

int u

LinkQueue Q

InitQueue(Q)

if(visited[v]==0)

{

visited[v]=1

EnQueue(Q,v)

while(QueueEmpty(Q)!=1)

{

DeQueue(Q,u)

ArcNode *r

r=(ArcNode*)malloc(sizeof(ArcNode))

if(!r) exit(-1)

r=G.vertices[u].firstarc

int w

for(r!=NULLr=r->nextarc)

{ w=r->adjvex

if(visited[w]==0)

{

visited[w]=1

cout<<u<<"--->"<<w<<endl

EnQueue(Q,w)

}

}

}

}

}

int main()

{

int i

ALGraph G

CreateDG(G)

int x

cout<<"请输入结点数:"

cin>>x

cout<<"邻接表为："<<endl

for(int j=1j<=xj++)

{

cout<<G.vertices[j].data<<" "

ArcNode *p

p=(ArcNode*)malloc(sizeof(ArcNode))

if(!p) exit(-1)

p=G.vertices[j].firstarc

while(p)

{

cout<<p->adjvex<<" "

p=p->nextarc

}

cout<<endl

}

cout<<"请输入第一个要访问的结点序号："<<endl

int n

cin>>n

for( i=0i<30i++)

visited[i]=0

cout<<"广度搜索："<<endl

BFS(G,n)

for( i=0i<30i++)

visited[i]=0

cout<<endl

cout<<"边集："<<endl

BFSB(G,n)

for( i=0i<30i++)

visited[i]=0

cout<<"深度搜索："<<endl

DFS(G,n)

for( i=0i<30i++)

visited[i]=0

cout<<endl

cout<<"边集："<<endl

DFSB(G,n)

//system("pause")

return 0

}

前几天上机刚好做了这个,个人感觉很完美,尽管老师说用的是邻接表而不是多重表,太简单,但还不错,界面输入过程比较繁琐,要严格按照提示来输入,是无向图,等级太低,没办法把执行结果粘出来,应该能看懂吧

#include"stdlib.h"

#define MaxVertexNum 50 //定义最大顶点数

typedef struct node{ //边表结点

int adjvex//邻接点域

struct node *next//链域

}EdgeNode

typedef struct vnode{ //顶点表结点

char vertex//顶点域

EdgeNode *firstedge//边表头指针

}VertexNode

typedef VertexNode AdjList[MaxVertexNum]//AdjList是邻接表类型

typedef struct {

AdjList adjlist//邻接表

int n,e//图中当前顶点数和边数

} ALGraph//图类型

//=========建立图的邻接表=======

void CreatALGraph(ALGraph *G)

{

int i,j,k

char a

EdgeNode *s//定义边表结点

printf("Input VertexNum(n) and EdgesNum(e): ")

scanf("%d,%d",&G->n,&G->e)//读入顶点数和边数

fflush(stdin)//清空内存缓冲

printf("Input Vertex string:")

for(i=0i<G->ni++) //建立边表

{

scanf("%c",&a)

G->adjlist[i].vertex=a//读入顶点信息

G->adjlist[i].firstedge=NULL//边表置为空表

}

printf("Input edges,Creat Adjacency List\n")

for(k=0k<G->ek++) { //建立边表

scanf("%d%d",&i,&j)//读入边（Vi，Vj）的顶点对序号

s=(EdgeNode *)malloc(sizeof(EdgeNode))//生成边表结点

s->adjvex=j//邻接点序号为j

s->next=G->adjlist[i].firstedge

G->adjlist[i].firstedge=s//将新结点*S插入顶点Vi的边表头部

s=(EdgeNode *)malloc(sizeof(EdgeNode))

s->adjvex=i//邻接点序号为i

s->next=G->adjlist[j].firstedge

G->adjlist[j].firstedge=s//将新结点*S插入顶点Vj的边表头部

}

}

//=========定义标志向量，为全局变量=======

typedef enum{FALSE,TRUE} Boolean

Boolean visited[MaxVertexNum]

//========DFS：深度优先遍历的递归算法======

void DFSM(ALGraph *G,int i)

{//以Vi为出发点对邻接链表表示的图G进行DFS搜索

EdgeNode *p

printf("%c",G->adjlist[i].vertex)//访问顶点Vi

visited[i]=TRUE//标记Vi已访问

p=G->adjlist[i].firstedge//取Vi边表的头指针

while(p) { //依次搜索Vi的邻接点Vj，这里j=p->adjvex

if(! visited[p->adjvex]) //若Vj尚未被访问

DFSM(G,p->adjvex)//则以Vj为出发点向纵深搜索

p=p->next//找Vi的下一个邻接点

}

}

void DFS(ALGraph *G)

{

int i

for(i=0i<G->ni++)

visited[i]=FALSE//标志向量初始化

for(i=0i<G->ni++)

if(!visited[i]) //Vi未访问过

DFSM(G,i)//以Vi为源点开始DFS搜索

} //==========BFS：广度优先遍历=========

void BFS(ALGraph *G,int k)

{ //以Vk为源点对用邻接链表表示的图G进行广度优先搜索

int i,f=0,r=0EdgeNode *p

int cq[MaxVertexNum]//定义FIFO队列

for(i=0i<G->ni++)

visited[i]=FALSE//标志向量初始化

for(i=0i<=G->ni++)

cq[i]=-1//初始化标志向量

printf("%c",G->adjlist[k].vertex)//访问源点Vk

visited[k]=TRUE

cq[r]=k//Vk已访问，将其入队。注意，实际上是将其序号入队

while(cq[f]!=-1) { // 队列非空则执行

i=cq[f]f=f+1//Vi出队

p=G->adjlist[i].firstedge//取Vi的边表头指针

while(p) { //依次搜索Vi的邻接点Vj（令p->adjvex=j）

if(!visited[p->adjvex]) { //若Vj未访问过

printf("%c",G->adjlist[p->adjvex].vertex)//访问Vj

visited[p->adjvex]=TRUE

r=r+1cq[r]=p->adjvex//访问过的Vj入队

}

p=p->next//找Vi的下一个邻接点

}

}//endwhile

}

//==========主函数===========

void main()

{

//int i

ALGraph *G

G=(ALGraph *)malloc(sizeof(ALGraph))

CreatALGraph(G)

printf("Print Graph DFS: ")

DFS(G)

printf("\n")

printf("Print Graph BFS: ")

BFS(G,3)

printf("\n")

}