实验目的

掌握图的邻接矩阵和邻接表存储结构；
掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用；
掌握图的最小生成树、拓扑排序等应用及算法思想。

实验内容
以邻接矩阵或邻接表方式建立有向图，并分别利用深度优先遍历和广度优先遍历方法输出各结点元素。
下面代码是用邻接表建立的有向图
Source Code
#include<stdio.h>
#include<malloc.h>
#define MAXV 100				//顶点数目的最大值 

int visited[MAXV];				//深度访问标记数组 
int BFSvisited[MAXV];			//广度访问标记数组 

typedef struct ANode
{	
	int adjNode;	//该边的邻接点编号
	ANode *next;	//指向下一条边的指针
}ArcNode;	//边结点类型

typedef struct Vnode
{
	char data;		//顶点信息
	ArcNode *first;	//指向第一个边结点
}VNode,AdjList[MAXV];	//头结点类型
 
typedef struct
{
	AdjList vertices;
	int n,e;//顶点数n和边数e
}ALGraph;	//图邻接表类型
 
//创建有向图 
void CreateGraph(ALGraph &g){
	printf("请输入顶点数和边数：");
	int n,e;
	scanf("%d%d",&n,&e);
	g.n=n;
	g.e=e;
	for(int i=0;i<g.n;i++){
		g.vertices[i].data=i;
		g.vertices[i].first=NULL; 
	}
	printf("请输入每条边的两个顶点(用空格隔开)\n");
	int x,y;
	for(i=0;i<g.e;i++){
		scanf("%d%d",&x,&y);
		ArcNode *p =(ArcNode*)malloc(sizeof(ArcNode));
		p->adjNode=y;
		p->next=g.vertices[x].first;
		g.vertices[x].first=p;
		ArcNode *q=(ArcNode*)malloc(sizeof(ArcNode));
		q->adjNode=x;
		q->next=g.vertices[y].first;
		g.vertices[y].first=q;
	
	}
} 
 
//深度优先遍历图,从第v个顶点开始遍历 
void DFS(ALGraph g,int v)
{
	visited[v]=true;
	printf("%d  ",g.vertices[v].data); 
	ArcNode *p=g.vertices[v].first;
	int w;
	while(p!=NULL){
		w=p->adjNode;
		if(!visited[w]){
			DFS(g,w);		//递归深度遍历 
		}
		p=p->next;
	}
} 

//广度优先遍历借助队列,从v开始遍历 
void BFS(ALGraph g,int v)
{
	BFSvisited[v]=true;
	ArcNode *p;
	printf("%d  ",g.vertices[v].data);
	int que[MAXV];
	int front=0,rear=0;
	rear=(rear+1)%MAXV;
	que[rear]= v;
	int j;
	while(rear!=front)	//当队列不空的时候
	{						 
		front=(front+1)%MAXV;//出队 
		j =que[front];
		p =g.vertices[j].first;
		while(p!=NULL)
		{
			if(!BFSvisited[p->adjNode])
			{
				printf("%d  ",g.vertices[p->adjNode].data);
				BFSvisited[p->adjNode]=true;
				rear=(rear+1)%MAXV;
				que[rear]=p->adjNode; 
			}
			p=p->next;//用的是邻接表，用p-next就可访问同层的相邻结点 
			
		}	
	}
}

int main()
{
	ALGraph g;
	CreateGraph(g);
	printf("深度优先遍历顺序：\n"); 
	DFS(g,0); 
	printf("\n");
	printf("广度优先遍历顺序：\n"); 
	BFS(g,0);
	printf("\n");
} 


Computational Results

Hint
此代码遍历过程是从初始点0开始遍历的，对应的图是

一、图的种类和定义
图由顶点集和边集组成。
主要有4种类型：无向图、有向图、无向网和有向网、
常见的存储结构有邻接矩阵、邻接表、邻接多重表、十字链表等。
二、图的表示方法
2.1图的邻接矩阵表示方法：
 
转载于:https://www.cnblogs.com/xleer/p/5628211.html

一、实验目的及要求

熟悉各种图的存储结构（邻接矩阵和邻接表）。
掌握图的深度优先和广度优先遍历算法。
掌握克鲁斯卡尔算法生成最小生成树的方法。
掌握狄克斯特拉算法计算最短路径和最短路径长度的方法。

二、实验内容（或实验原理、实验拓扑）

编写一个程序，输出下面带权有向图的邻接表，并根据该邻接表，实现图的深度优先遍历算法，具体要求如下：

(1)从顶点0开始的深度优先遍历序列(递归算法)

(2)从顶点0开始的深度优先遍历序列(非递归算法)


三、实验设计方案（包括实验步骤、设计思想、算法描述或开发流程等）
（一）在graph.h中创建图的邻接表存储结构：

1.首先定义邻接表类型中的边结点类型ArcNode；

2.然后定义邻接表头结点类型VNode；

3.接着定义完整的图邻接表类型AdjGraph。

（二）在main.cpp中完成图的基本运算算法：

1. 创建图的邻接表CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e)；

2. 输出邻接表G DispAdj(AdjGraph G)；

3. 销毁图的邻接表DestroyAdj(AdjGraph *&G)；

4.定义全局函数visited[MAXV]；

5. 递归深度优先算法(AdjGraph *G,int v)；

6. 非递归深度优先算法DFS1(AdjGraph *G,int v)；

5.主函数 main()根据问题依次调用基本操作函数并编写通俗易懂的语句输出。
四、实验结果（包括设计效果、测试数据、运行结果等）
运行结果如下：


五、实验小结（包括收获、心得体会、注意事项、存在问题及解决办法、建议等）
从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程为图的遍历。深度优先搜索遍历的过程是：从图中某个初始顶点v出发，首先访问初始顶点v。然后选择一个与顶点v相邻且没被访问过的顶点w为初始顶点，再从w出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。
六、附录（包括作品、流程图、源程序及命令清单等）
graph.h：
//图的邻接表存储结构
#define INF 32767				//定义∞
#define	MAXV 100				//最大顶点个数
typedef char InfoType;
//以下定义邻接表类型
typedef struct ANode
{	int adjvex;					//该边的邻接点编号
	struct ANode *nextarc;		//指向下一条边的指针
	int weight;					//该边的相关信息，如权值（用整型表示）
} ArcNode;						//边结点类型
typedef struct Vnode
{	InfoType info;				//顶点其他信息
	int count;					//存放顶点入度,仅仅用于拓扑排序
	ArcNode *firstarc;			//指向第一条边
} VNode;						//邻接表头结点类型
typedef struct 
{	VNode adjlist[MAXV];		//邻接表头结点数组
	int n,e;					//图中顶点数n和边数e
} AdjGraph;						//完整的图邻接表类型

main.cpp:
#include <stdio.h>
#include <malloc.h>
#include "graph.h"
//----创建图的邻接表G----------------------------------
void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e) //创建图的邻接表
{
	int i,j;
	ArcNode *p;
	G=(AdjGraph *)malloc(sizeof(AdjGraph));
	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 (A[i][j]!=0 && A[i][j]!=INF)			//存在一条边
			{	p=(ArcNode *)malloc(sizeof(ArcNode));	//创建一个结点p
				p->adjvex=j;
				p->weight=A[i][j];
				p->nextarc=G->adjlist[i].firstarc;	//采用头插法插入结点p
				G->adjlist[i].firstarc=p;
			}
	G->n=n; G->e=n;
}
//----输出邻接表G----------------------------------
void DispAdj(AdjGraph *G)
{
	int i;
	ArcNode *p;
	for (i=0;i<G->n;i++)
	{
		p=G->adjlist[i].firstarc;
		printf("%3d: ",i);
		while (p!=NULL)
		{
			printf("%3d[%d]→",p->adjvex,p->weight);
			p=p->nextarc;
		}
		printf("∧\n");
	}
}
//----销毁图的邻接表----------------------------------
void DestroyAdj(AdjGraph *&G)
{	int i;
	ArcNode *pre,*p;
	for (i=0;i<G->n;i++)			//扫描所有的单链表
	{	pre=G->adjlist[i].firstarc;	//p指向第i个单链表的首结点
		if (pre!=NULL)
		{	p=pre->nextarc;
			while (p!=NULL)			//释放第i个单链表的所有边结点
			{	free(pre);
				pre=p; p=p->nextarc;
			}
			free(pre);
		}
	}
	free(G);						//释放头结点数组
}
//----深度优先递归算法----------------------------------
int visited[MAXV];						//全局数组
void DFS(AdjGraph *G,int v)   //递归深度优先算法
{
	ArcNode *p;
	visited[v]=1;                   	//置已访问标记
	printf("%3d",v); 					//输出被访问顶点的编号
	p=G->adjlist[v].firstarc;      		//p指向顶点v的第一条弧的弧头结点
	while (p!=NULL)
	{
		if (visited[p->adjvex]==0)		//若p->adjvex顶点未访问,递归访问它
			DFS(G,p->adjvex);
		p=p->nextarc;              		//p指向顶点v的下一条弧的弧头结点
	}
}
//----深度优先非递归算法----------------------------------
void DFS1(AdjGraph *G,int v)   //非递归深度优先算法
{
	ArcNode *p;
	ArcNode *St[MAXV];
	int top=-1,w,i;
    for (i=0;i<G->n;i++)
		visited[i]=0;		//顶点访问标志均置成0
	printf("%3d",v);        //访问顶点v
	visited[v]=1;
	top++;                  //将顶点v的第一个相邻顶点进栈
	St[top]=G->adjlist[v].firstarc;
	while (top>-1)          //栈不空循环
	{
		p=St[top]; top--;   //出栈一个顶点作为当前顶点
		while (p!=NULL)     //查找当前顶点的第一个未访问的顶点
		{
			w=p->adjvex;
			if (visited[w]==0)
			{
				printf("%3d",w); //访问w
				visited[w]=1;
				top++;           //将顶点w的第一个顶点进栈
				St[top]=G->adjlist[w].firstarc;
				break;           //退出循环
			}
			p=p->nextarc;        //找下一个相邻顶点
		}
	}
	printf("\n");
}
int main()
{
	AdjGraph *G;
	int A[MAXV][MAXV]={
		{0,5,INF,7,INF,INF},
		{INF,0,4,INF,INF,INF},
		{8,INF,0,INF,INF,9},
		{INF,INF,5,0,INF,6},
		{INF,INF,INF,5,0,INF},
		{3,INF,INF,INF,1,0}};
	int n=6, e=10;
	CreateAdj(G,A,n,e);             //建立实验讲义中的邻接表
	printf("图G的邻接表:\n");
	DispAdj(G);                     //输出邻接表
	printf("从顶点0开始的DFS(递归算法):\n");
	DFS(G,0);printf("\n");
	printf("从顶点0开始的DFS(非递归算法):\n");
	DFS1(G,0);
}

图的存储结构主要有邻接矩阵，邻接表，十字链表等。笔者在这里主要介绍邻接矩阵和邻接表两种存储结构。并将分别采用两种存储方法去实现无向图的基本操作，包括加点，删点，加边，删边、深度优先遍历以及广度优先遍历。（文末附完整代码）

邻接矩阵部分

主要包含如下函数

void visit()

该函数意在将标注数组初始化为false；（标志数组在dfs和bfs均有用到)

void insert_node(char c) 加点函数

void delete_node(char c) 删点函数

insert_edge(char u, char v) 加边函数

delete_edge(char u, char v) 删边函数

bfs(int v) 广度优先遍历

dfs(int u) 深度优先遍历

每个函数的具体算法思想均在代码种给出注释

以下为邻接矩阵的完整代码

#include <iostream>
#include <algorithm>
#include <string.h> 
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <cstdio>
const int N = 100;

using namespace std;

int V, E;
class matrix
{
private:
    int no, ed;
    char node[N];
    int edge[N][N];
    bool vis[N];

public:
    matrix()
    {
        memset(edge, 0,sizeof(edge));
        for (int i = 0; i < N; ++i)
            node[i] = '#', vis[i] = false;
        no = ed = 0;
    }
    void visit()
    {
        for (int i = 0; i < N; ++i)
            vis[i] = false;
    }
    void insert_node(char c) //扩容
    /**
     * @description: 由于采用的是顺序表结构存储
     * 只需在设置一个记录结点个数的变量，每次新
     * 加入一个结点就顺序接在数组尾巴，然后记录
     * 结点个数的变量自增 1
     * @param {*char c}
     */
    {
        node[no++] = c;
    }
    void delete_node(char c)
    /**
     * @description: 顺序遍历存储结点的数组。直至找到该节点
     * 然后将该节点后面的数据全部往前移一个位置。同时记录边问题
     * 的数组也应将包含该节点边关系的对应数据行和列采取将后面的
     * 数据往前移动位置，以覆盖边数组种被删除结点的信息
     * @param {*char c}
     */
    {
        int i;
        for (i = 0; i < no; ++i)
            if (node[i] == c)
                break;
        for (int j = i; j < no - 1; ++j)
            node[j] = node[j + 1];
        for (int k = 0; k < no; ++k)
            for (int j = i; j < no - 1; ++j)
                edge[k][j] = edge[k][j + 1];
        for (int k = 0; k < no - 1; ++k)
            for (int j = i; j < no - 1; ++j)
                edge[j][k] = edge[j + 1][k];
        no--;
    }
    void insert_edge(char u, char v)
    /**
     * @description: 通过设置两个变量x，y，顺序变量结点数组
     * 在找到相应结点后存储它的位置下标，然后在边数组中将其
     * 连接起来
     * @param {*char u, char v}
     */
    {
        int x = -1, y = -1; //不存在的情况
        for (int i = 0; i < no; ++i)
            if (node[i] == u)
                x = i;
            else if (node[i] == v)
                y = i;
        edge[x][y] = edge[y][x] = 1;
        ed++;
    }
    void delete_edge(char u, char v)
    /**
     * @description: 同加边操作，首先应找出两个结点对应的
     * 下标，然后在边数组中删除相应的边
     * @param {*char u, char v}
     */
    {
        int x = -1, y = -1; //不存在的情况
        for (int i = 0; i < no; ++i)
            if (node[i] == u)
                x = i;
            else if (node[i] == v)
                y = i;
        edge[x][y] = edge[y][x] = 0;
        ed--;
    }
    void bfs(int v)
    /**
     * @description: 广度优先遍历，借助队列来实现
     * 首先将开始结点V输出，同时将下标存入队列中，然后
     * 在队列不为空的情况下逐一出队队首元素，判断是否存在
     * 以该元素为起点的边，同时边的终点未被访问，若满足该
     * 两项条件则可以输出数据，并标记该节点已输出，然后将
     * 该结点入队，如此往复直至队列为空。
     * @param {*int v}
     */
    {
        queue<int> q;
        q.push(v);
        cout << node[v] << " ";
        vis[v] = true;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < no; ++i)
            {
                if (edge[u][i] == 1 && !vis[i])
                {
                    cout << node[i] << " ";
                    vis[i] = true;
                    q.push(i);
                }
            }
        }
    }
    void dfs(int u)
    /**
     * @description: 深度优先遍历。采用递归形式实现
     * 首先输出开始结点对应数据，然后顺序遍历以开始结点
     * 为起点的边，且边的终点尚未被访问过，则往下搜索，如此
     * 往复，直至输出全部结点
     * @param {*int u}
     */
    {
        cout << node[u] << " ";
        vis[u] = true;
        for (int i = 0; i < no; ++i)
            if (edge[u][i] == 1 && !vis[i])
                dfs(i);
    }
    void display_node()
    /**
     * @description: 通过顺序遍历结点数组，以输出结点来进行展示
     */
    {
        for (int i = 0; i < no; ++i)
            cout << node[i] << " ";
        cout << endl;
    }
    void display_edge()
    /**
     * @description: 顺序遍历边数组，输出边信息来进行展示
     */
    {
        for (int i = 0; i < no; cout << endl, ++i)
            for (int j = 0; j < no; ++j)
                cout << edge[i][j] << " ";
    }
};
void Matrix()
{
    cout << "邻接矩阵：\n";
    matrix G;
    cout << "请输入点数，边数：\n";
    cin >> V >> E;
    cout << "请输入点\n";
    char cc, u, v;
    for (int i = 0; i < V; ++i)
    {
        cin >> cc;
        G.insert_node(cc);
    }
    cout << "请输入边\n";
    for (int i = 0; i < E; ++i)
    {
        cin >> u >> v;
        G.insert_edge(u, v);
    }
    G.display_node();
    G.display_edge();
    cout << "请输出宽搜结果\n";
    G.bfs(0);
    G.visit();
    cout << endl;
    cout << "请输出深搜结果\n";
    G.dfs(0);
    G.visit();
    cout << endl;
    cout << "请输入要删除的点的数及点\n";
    cin >> V;
    for (int i = 0; i < V; ++i)
    {
        cin >> cc;
        G.delete_node(cc);
    }
    cout << "请输入要删除的边的数及边\n";
    cin >> E;
    for (int i = 0; i < E; ++i)
    {
        cin >> u >> v;
        G.delete_edge(u, v);
    }
    G.display_node();
    G.display_edge();
}
int main()
{
    int _ = 1;
    //sf(_);
    while (_--)
    {
        Matrix();
    }

    return 0;
}

邻接表部分

主要实现思想同邻接矩阵，这里就不再赘述，直接放代码，代码中包含了详细注释

#include <iostream>
#include <algorithm>
#include <string.h> 
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <vector>
#include <cstdio>
const int N = 100;

using namespace std;

int V, E;
typedef struct arcnode
{
    struct arcnode *next;
    int vex;
    arcnode(const int &d) : vex(d), next(NULL) {}
} arcnode;
typedef struct node
{
    char ve;
    arcnode *fir = new arcnode(0);
} arclist[N];
class arc
{
private:
    arclist ar;
    int no, ed;
    bool vis[N];

public:
    arc()
    {
        no = ed = 0;
        for (int i = 0; i < 100; ++i)
            ar[i].ve = '#';
    }
    void visit()
    {
        for (int i = 0; i < 100; ++i)
            vis[i] = false;
    }
    void insert_node(char c)
    /**
     * @description: 由于采用的是顺序表结构存储
     * 只需在设置一个记录结点个数的变量，每次新
     * 加入一个结点就顺序接在数组尾巴，然后记录
     * 结点个数的变量自增 1
     * @param {*char c}
     */
    {
        ar[no++].ve = c;
    }
    void delete_node(char c)
    /**
     * @description: 首先在结点数组中找到要删除结点的下标，然后
     * 将该结点后面的数据均往前移动一个位置以覆盖数据，从而达到删除
     * 该结点目的。同时在邻接表中也要删除对应的边关系，首先将该节点
     * 的边关系的存储链表删除，然后遍历其他每一个结点的存储边关系的
     * 存储链表，找到其中包含该节点的下标的结点，将其删去，同时对大于
     * 该节点的其他数据，若存储下标大于它，则应自减 1
     * @param {*char c}
     */
    {
        int i;
        for (i = 0; i < no; ++i)
            if (ar[i].ve == c)
                break;
        for (int j = i; j < no - 1; ++j)
            ar[j] = ar[j + 1];
        no--;
        for (int k = 0; k < no; ++k)
        {
            arcnode *T = ar[k].fir;
            while (T->next)
            {
                if (T->next->vex == i)
                {
                    if (T->next->next)
                        T->next = T->next->next;
                    else
                        T->next = NULL;
                    break;
                }
                else if (T->next->vex > i)
                {
                    T->next->vex--;
                    T = T->next;
                }
                else
                    T = T->next;
            }
        }
    }
    void insert_edge(char u, char v)
    /**
     * @description: 首先应找到边对应两个结点的存储下标。然后分别
     * 在以u为起点的存储边关系的链表中连接v；然后在以v为起点的存储
     * 边关系的链表中连接u
     * @param {*char u, char v}
     */
    {
        int x = -1, y = -1;
        for (int i = 0; i < no; ++i)
            if (ar[i].ve == u)
                x = i;
            else if (ar[i].ve == v)
                y = i;
        arcnode *p = new arcnode(0);
        p->vex = y;
        arcnode *q = ar[x].fir;
        while (q->next)
            q = q->next;
        p->next = q->next;
        q->next = p;

        arcnode *r = new arcnode(0);
        r->vex = x;
        q = ar[y].fir;
        while (q->next)
            q = q->next;
        r->next = q->next;
        q->next = r;

        ed++;
    }
    void delete_edge(char u, char v)
    /**
     * @description: 
     * 删边操作同删点操作的思想
     * @param {*char u, char v}
     */
    {
        int x = -1, y = -1;
        for (int i = 0; i < no; ++i)
            if (ar[i].ve == u)
                x = i;
            else if (ar[i].ve == v)
                y = i;
        arcnode *T = ar[x].fir;
        while (T->next)
            if (T->next->vex != y)
                T = T->next;
            else
            {
                if (T->next->next)
                    T->next = T->next->next;
                else
                    T->next = NULL;
                break;
            }

        T = ar[y].fir;
        while (T->next)
            if (T->next->vex != y)
                T = T->next;
            else
            {
                if (T->next->next)
                    T->next = T->next->next;
                else
                    T->next = NULL;
                break;
            }
        ed--;
    }

    void bfs(int u)
    {
        queue<int> q;
        int v;
        cout << ar[u].ve << " ";
        q.push(u);
        vis[u] = true;
        while (!q.empty())
        {
            v = q.front();
            q.pop();
            arcnode *p = ar[v].fir;
            while (p->next)
            {
                p = p->next;
                if (!vis[p->vex])
                {
                    cout << ar[p->vex].ve << " ";
                    vis[p->vex] = true;
                    q.push(p->vex);
                }
            }
        }
    }
    void dfs(int u)
    {
        cout << ar[u].ve << " ";
        vis[u] = true;
        arcnode *p = ar[u].fir;
        while (p->next)
        {
            p=p->next;
            if (!vis[p->vex])
                dfs(p->vex);
        }
    }

    void display_edge()
    {
        cout << "修改后的结果" << endl;
        for (int i = 0; i < no; cout << endl, ++i)
        {
            cout << ar[i].ve << "  :";
            arcnode *T = new arcnode(0);
            T = ar[i].fir->next;
            while (T)
            {
                cout << T->vex << " ";
                T = T->next;
            }
            delete T;
        }
    }
};
void Arc()
{
    cout << "邻接表：\n";
    arc g;
    cout << "请输入点数，边数：\n";
    cin >> V >> E;
    cout << "请输入点\n";
    char cc, u, v;
    for (int i = 0; i < V; ++i)
    {
        cin >> cc;
        g.insert_node(cc);
    }
    cout << "请输入边\n";
    for (int i = 0; i < E; ++i)
    {
        cin >> u >> v;
        g.insert_edge(u, v);
    }
    g.display_edge();
    cout << "请输出宽搜结果\n";
    g.visit();
    g.bfs(0);
    cout << endl;
    cout << "请输出深搜结果\n";
    g.visit();
    g.dfs(0);
    cout << endl;
    cout << "请输入要删除的点的数及点\n";
    cin >> V;
    for (int i = 0; i < V; ++i)
    {
        cin >> cc;
        g.delete_node(cc);
    }
    g.display_edge();
    cout << "请输入要删除的边的数及边\n";
    cin >> E;
    for (int i = 0; i < E; ++i)
    {
        cin >> u >> v;
        g.delete_edge(u, v);
    }
    g.display_edge();
}

int main()
{
    int _ = 1;
    //sf(_);
    while (_--)
    {
        Arc();
    }

    return 0;
}