图采用邻接矩阵存储结构

#define TRUE 1 #define FALSE 0 #define MAXV 20 typedef int VertexType; //用顶点编号表示顶点 typedef struct { // 图的定义

int edges[MAXV][MAXV] ; // 边数组 int n, e; //顶点数，弧数 VertexType vexs[MAXV]; // 顶点信息 } MGraph;

1、创建具有n个顶点e条边的无向图 void CreateUDG(MGraph &G,int n,int e) {

int i,j,u,v; G.n=n;G.e=e; /*

printf(\"请输入%d个顶点的编号：\\n\ for(i=0;iscanf(\"%d\.vexs[i]); */

//初始化顶点信息，假设顶点的编号和顶点在数组内的下标相同

for(i=0;i//初始化邻接矩阵 for(i=0;ifor(j=0;jprintf(\"请输入一条边的两个顶点编号：\"); scanf(\"%d%d\ G.edges[u][v]=G.edges[v][u]=1; }

}

2、创建具有n个顶点e条弧的有向图

void CreateDG(MGraph &G,int n,int e) {

int i,j,u,v; G.n=n;G.e=e; /*

printf(\"请输入%d个顶点的编号：\\n\ for(i=0;iscanf(\"%d\.vexs[i]); */

//初始化顶点信息，假设顶点的编号和顶点在数组内的下标相同

for(i=0;i//初始化邻接矩阵 for(i=0;ifor(j=0;j{

printf(\"请输入一条弧的两个顶点编号（注意先输入的为弧尾）：\"); scanf(\"%d%d\ G.edges[u][v]=1; }

}

3、求图G中顶点v的第一个邻接点 int FirstAdjVex(MGraph G, int v) {

for(int i=0;i}

4、求图G中顶点v相对于w的下一个邻接点 int NextAdjVex(MGraph G, int v，int w) {

for(int i=w;ireturn i; return -1; }

5、深度优先搜索算法

Boolean visited[MAXV];

void DFSTravse (MGraph G) {

// 对图 G 作深度优先遍历。

for (v=0; vvisited[v] = FALSE; // 访问标志数组初始化 for (v=0; vif (!visited[v]) DFS(G, v);

// 对尚未访问的顶点调用DFS

}

void DFS(MGraph G, int v) {

// 从顶点v出发，深度优先搜索遍历连通图 G visited[v] = TRUE; printf(v);

for(int w=FirstAdjVex(G, v);

w>=0; w=NextAdjVex(G,v,w)) if (!visited[w]) DFS(G, w);

// 对v的尚未访问的邻接顶点w // 递归调用DFS } // DFS

6、广度优先搜索算法 void BFSTraverse(MGraph G)

{

for (v=0; vvisited[v] = FALSE; //初始化访问标志 InitQueue(Q); // 置空的辅助队列Q for ( v=0; v{ // v 尚未访问

visited[v] = TRUE; printf(v); // 访问v EnQueue(Q, v); // v入队列 while (!QueueEmpty(Q))

{

DeQueue(Q, u); // 队头元素出队并置为u

for(w=FirstAdjVex(G, u); w>=0; w=NextAdjVex(G,u,w)) if ( ! visited[w])

{

visited[w]=TRUE; printf(w);

EnQueue(Q, w); // 访问的顶点w入队列 } // if } // while } //if } // BFS

图采用邻接表存储结构

typedef struct ANode /*弧（边）的结点结构类型*/ { int adjvex; /*该弧（边）的终点位置*/

struct ANode *nextarc; /*指向下一条弧（边）的指针*/ } ArcNode;

typedef struct Vnode /*邻接表头结点的类型*/ { VertexType data; /*顶点信息*/ ArcNode *firstarc; /*指向第一条弧（边）*/ } VNode;

typedef VNode AdjList[MAXV]; /*AdjList是邻接表类型*/ typedef struct

{ AdjList adjlist; /*邻接表*/

int n,e; /*图中顶点数n和边数e*/ } ALGraph; /*图的类型*/

1、创建具有n个顶点e条边的无向图 void CreateUDG(ALGraph &G,int n,int e) {

int i,j,u,v;ArcNode *p1,*p2,*q; G.n=n;G.e=e;

//初始化顶点信息(头结点)，假设顶点的编号和顶点在数组内的下标相同

for(i=0;i{ G.adjlist[i].data=i; G.adjlist[i].firstarc=NULL; }

//生成每个顶点的邻接点的单链表

for(j=0;j{

printf(\"请输入一条边的两个顶点编号：\"); scanf(\"%d%d\

p1=(ArcNode *)malloc(sizeof(ArcNode)); p1->adjvex=v;p1->nextarc=NULL;

if(G.adjlist[u].firstarc==NULL) G.adjlist[u].firstarc=p1; else

{ q=G.adjlist[u].firstarc;

while(q->nextarc!=NULL) q=q->nextarc; q->nextarc=p1; }

p2=(ArcNode *)malloc(sizeof(ArcNode));

p2->adjvex=u;p2->nextarc=NULL;

if(G.adjlist[v].firstarc==NULL) G.adjlist[v].firstarc=p2; else

{ q=G.adjlist[v].firstarc;

while(q->nextarc!=NULL) q=q->nextarc; q->nextarc=p2; }

}//for }

2、创建具有n个顶点e条弧的有向图 void CreateUDG(ALGraph &G,int n,int e) {

int i,j,u,v;ArcNode *p,*q; G.n=n;G.e=e;

//初始化顶点信息(头结点)，假设顶点的编号和顶点在数组内的下标相同

for(i=0;i{ G.adjlist[i].data=i; G.adjlist[i].firstarc=NULL; }

//生成每个顶点的邻接点的单链表

for(j=0;j{

printf(\"请输入一条弧的两个顶点编号（先输入的为弧尾）：\"); scanf(\"%d%d\

p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=v;p->nextarc=NULL;

if(G.adjlist[u].firstarc==NULL) G.adjlist[u].firstarc=p; else

{ q=G.adjlist[u].firstarc;

while(q->nextarc!=NULL) q=q->nextarc; q->nextarc=p; } }//for }

3、求图G中顶点v的第一个邻接点 int FirstAdjVex(ALGraph G, int v) { ArcNode *p=G.adjlist[v].firstarc; if(p!=NULL) return p->adjvex; else return -1;

}

4、求图G中顶点v相对于w的下一个邻接点 int NextAdjVex(ALGraph G, int v，int w) { ArcNode *p=G.adjlist[v].firstarc; while(p!=NULL&&p->adjvex!=w) p=p->nextarc; if(p) return p->adjvex; else return -1; }