邻接矩阵定义
const int vnum=20;
typedef struct gp
{
VertexType vexs[vnum]; //顶点信息
int arcs[vnum][vnum]; //邻接矩阵
int vexnum,arcnum;
}Graph;
带权图的邻接矩阵
int最大整数：32767，表示无穷大
Graphm.h
const int vnum=20;
const int MAX_INT=32767;
typedef struct gp
{
VertexType vexs[vnum];
WeightType arcs[vnum][vnum];
int vexnum,arcnum;
}WGraph;
无向带权图邻接矩阵
void GreatGraph(Graph *g)
{
int i,j,n,e,w;
char ch;
scanf("%d %d",&n,&e); //读入顶点个数和边数
g->vexnum=n;
g->arcnum=e;
for (i=0;i<g->vexnum;i++)
{
scanf("%c“,&ch); //读入顶点信息
g->vexs[i]=ch;
}
for (i=0;i<g->vexnum;i++)
for (j=0;j<g->vexnum;j++)
g->arcs[i][j]=MAX_INT; //初始化邻接矩阵
for (k=0;k<g->arcnum;k++)
{
scanf("%d %d %d",&i,&j,&w); //读入边(顶点对)和权值
g->arcs[i][j]=w;
g->arcs[j][i]=w;
}
}
邻接表 Graphlk.h
#define vnum 20
typedef struct arcnode
{
int adjvex; //下一条边的顶点编号
WeightType weight; //带权图的权值域，若是非带权图
struct arcnode *nextarc; //指向下一条边的指针
}ArcNode;
typedef struct vexnode
{
int vertex; //顶点编号
ArcNode *firstarc; //指向第一条边的指针
}AdjList[vnum];
typedef struct gp
{
AdjList adjlist;
int vexnum,arcnum; //顶点和边的个数
}Graph;
建立有向图的邻接表的算法描述如下：
GreateAdjlist(Graph *g)
{
int n,e,i,j,k;
ArcNode *p;
scanf("%d %d",&n,&e); //读入顶点个数和边数
g->vexnum=n;
g->arcnum=e;
for (i=0;i<n;i++)
{
g->adjlis[i].vertex=i; //初始化顶点Vi的信息
g->adjlis[i].firstarc=NULL; //初始化i的第一个邻接点为NULL
}
for (k=0;k<e;k++) //输入e条弧
{
scanf("%d %d",&i,&j);
p=(ArcNode*)malloc(sizeof(ArcNode)); //生成j的表结点
p->adjvex=j;
p->nextarc=g->adjlis[i].firstarc; //将结点j链到i的单链表中
g->adjlis[i].firstarc=p;
}
}
连通图的深度优先搜索
Dfs(Graph g,int v)
{
访问v;
visited[v]=1; //置已访问标志
找出g中v的第一个邻接点w;
while (w存在)
{
if w未被访问Dfs(g,w);
w=g中v的下一个邻接点;
}
如果以邻接表为存储结构，查找邻接点操作实际上是顺序查找链表，相应的深度优先搜索算法描述如下：
Dfs(Graph g,int v)
{
ArcNode *p;
printf("%d",v); //访问顶点
visited[v]=1; //置已访问标志
p=g.adjlist[v].firstarc;
while (p != NULL);
{
if (!visited[p->adjvex]) Dfs(g,p->adjvex);
p=p->nextarc;
}
}