7-1.将图以邻接矩阵存储，实现DFS。

code

#include<bits/stdc++.h>
using namespace std;
int book[100], sum, n, e[100][100];

void dfs(int cur){
   
	printf("%d ", cur);
	sum++;
	if (sum == n)
		return;
	for (int i = 1; i <= n; i++){
   
		if (e[cur][i] == 1 && book[i] == 0){
   
			book[i] = 1;
			dfs(i);
		}
	}
	return;
}

int main(){
   
	int i, j, m, a, b;
	printf("请输入顶点数和边数:\n");
	scanf("%d%d", &n, &m);
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			if (i == j)
				e[i][j] = 0;
			else
				e[i][j] = 99999;//假设99999为无穷大；
	for (i = 0; i < m; i++){
   
		printf("请输入第%d条边:\n", i + 1);
		scanf("%d%d", &a, &b);
		e[a][b] = 1;
		e[b][a] = 1;
	}
	book[1] = 1;
	printf("深度优先遍历结果为：");
	dfs(1);
	return 0;
}

运行截图

7-2.将图以邻接表存储，实现BFS。

code

#include<bits/stdc++.h>
using namespace std;

//边表节点结构，一个adjvex用来存储邻接点的位置，一个next指针用来指向下一个节点
typedef struct EdgeNode
{
   
    int adjvex;
    struct EdgeNode * next;
} EdgeNode;
 
//顶点表节点结构，一个data用来存储数据，一个firstedge是用来指向边表的第一个节点
typedef struct
{
   
    string data;
    EdgeNode * firstedge;
} AdjList;

//里面的adjList[15]表示我给顶点表开了15的单位大小，然后numVertex,numEdge是一个图的顶点数和边数
typedef struct
{
   
    AdjList adjList[15];
    int numVertex,numEdge;
} GraphAdjList;
//这个函数是这样的，它会遍历图的顶点，然后返回一个位置（其实也就是它所在的下标）
int local(GraphAdjList G,string val)
{
   
    for(int i=0; i<G.numVertex; i++)
    {
   
        if(G.adjList[i].data==val)
            return i;
    }
    return -1;
}
//比如v2的位置是在2 这个可以看上面的顶点表图 
void CreateGraph(GraphAdjList & G)
{
   
    int i,j,k;
    string v1,v2;
    EdgeNode * e,* p,*q;
    cout<<"请输入顶点数和边数，并以空格隔开:"<<endl;
    cin>>G.numVertex>>G.numEdge;
    cout<<"请输入顶点的信息："<<endl;
    for(i=0; i<(G.numVertex); i++)
    {
   
        //cout<<"第"<<i+1<<"个顶点："<<endl;
        cin>>G.adjList[i].data;
        G.adjList[i].firstedge=NULL;
    }
    for(k=0; k<(G.numEdge); k++)
    {
   
        //cout<<"请输入边（Vi,Vj）上的顶点信息:"<<endl;
        cin>>v1>>v2;
        i=local(G,v1);
        j=local(G,v2);
 
        if(G.adjList[i].firstedge==NULL)
        {
   
            e= new EdgeNode;
            e->adjvex=j;
            e->next=NULL;
            G.adjList[i].firstedge=e;
        }
        else
        {
   
            p=G.adjList[i].firstedge;
            while(p->next!=NULL)
            {
   
                p=p->next;
            }
            e = new EdgeNode;
            e->adjvex=j;
            e->next=NULL;
            p->next=e;
        }
        if(G.adjList[j].firstedge==NULL)
        {
   
            e= new EdgeNode;
            e->adjvex=i;
            e->next=NULL;
            G.adjList[j].firstedge=e;
        }
        else
        {
   
            p=G.adjList[j].firstedge;
            while(p->next!=NULL)
            {
   
                p=p->next;
            }
            e = new EdgeNode;
            e->adjvex=i;
            e->next=NULL;
            p->next=e;
        }
    }
}
void Prin(GraphAdjList G)
{
   
    cout<<"所建立的邻接表如以下所示："<<endl;
    for(int i=0; i<G.numVertex; i++)
    {
   
        cout<<G.adjList[i].data;             //先输出顶点信息
        EdgeNode * e = G.adjList[i].firstedge;
        while(e)                              //然后就开始遍历输出每个边表所存储的邻接点的下标
        {
   
            cout<<"-->"<<e->adjvex;
            e=e->next;
        }
        cout<<endl;
    }
}
bool DFSvisited[50];  //用于深搜的标记数组
bool BFSvisited[50];  //用于广搜的标记数组
void DFS(GraphAdjList  G,int i)
{
   
 
    EdgeNode * p;
    DFSvisited[i]=true;
    cout<<G.adjList[i].data<<" ";
    p=G.adjList[i].firstedge;
    while(p)
    {
   
        if(!DFSvisited[p->adjvex])
            DFS(G,p->adjvex);
        p=p->next;
    }
}
void DFSTraverse(GraphAdjList  G)
{
   
    for(int i=0; i<G.numVertex; i++)
        DFSvisited[i]=false;
    for(int i=0; i<G.numVertex; i++)
    {
   
        if(!DFSvisited[i])
            DFS(G,i);
    }
}
void BFSTraverse(GraphAdjList  G)
{
   
    EdgeNode * p;
    queue<int>q;
    for(int i=0; i<G.numVertex; i++)
        BFSvisited[i]=false;
    for(int i=0; i<G.numVertex; i++)
    {
   
        if(!BFSvisited[i])
        {
   
            BFSvisited[i]=true;
            cout<<G.adjList[i].data<<" ";
            q.push(i);
            while(!q.empty())
            {
   
                int count =q.front();
                q.pop();
                p=G.adjList[count].firstedge;
                while(p)
                {
   
                    if(!BFSvisited[p->adjvex])
                    {
   
                        BFSvisited[p->adjvex]=true;
                        cout<<G.adjList[p->adjvex].data<<" ";
                        q.push(p->adjvex);
                    }
                    p=p->next;
                }
            }
        }
    }
}

int main(){
   
	GraphAdjList G;
	CreateGraph(G);
	Prin(G);
	cout << "BFS:" << endl;
	BFSTraverse(G);
	return 0;
}

运行截图

7-3. 将图以邻接矩阵存储，实现prim算法。

code

#include <bits/stdc++.h>
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

typedef int Status;
typedef int ElemType;

#define INFINITY 65535 //最大值∞
#define MAX_VERTEX_NUM 20 //最大顶点个数

typedef int Status;
typedef int VRType;
typedef char InfoType;
typedef int VertexType;
typedef enum
{
   
    DG,
    DN,
    UDG,
    UDN
} GraphKind; //{有向图，有向网，无向图，无向网}

typedef struct ArcCell
{
   
    VRType adj;     //VRType 是顶点关系类型。对无权图，用0或1表示相邻否；对带权图，则为权值类型
    InfoType *info; //该弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
   
    VertexType vexs[MAX_VERTEX_NUM]; //顶点向量
    AdjMatrix arcs;                  //邻接矩阵
    int vexnum, arcnum;              //图的当前顶点数和弧数
    GraphKind kind;                  //图的种类标志
} MGraph;

typedef struct
{
   
    VertexType adjvex;
    VRType lowcost;
} CLOSEDGE;

/*******************************声明部分****************************************/
Status CreateUDN(MGraph *G);
//构造无向网
int LocateVex(MGraph G, VertexType v);
//确定v在G中的位置
int minimum(CLOSEDGE closedge[], int n);
//返回最小连接的顶点序号
void MiniSpanTree_PRIM(MGraph G, VertexType u);
//用普里姆算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边
//记录从顶点集U到V-U的代价最小的边的辅助数组定义
/*******************************函数部分****************************************/
Status CreateUDN(MGraph *G)
{
   
    printf("\n构造无向网\n");
    int i, j, k;       //i,j,k用于计数
    int w;             //权重
    VertexType v1, v2; //弧头，弧尾

    printf("请输入顶点个数：");
    scanf("%d", &(*G).vexnum);
    printf("请输入弧个数：");
    scanf("%d", &(*G).arcnum);
    //假定该图不含其他信息
    int IncInfo = 0;
    cout << "依次输入顶点(空格隔开)：\n";
    for (i = 0; i < (*G).vexnum; i++){
   
        scanf("%d", &(*G).vexs[i]);
    } //for

    for (i = 0; i < (*G).vexnum; i++) //初始化邻接矩阵
        for (j = 0; j < (*G).vexnum; j++)
        {
   
            (*G).arcs[i][j].adj = INFINITY; //无向网
            (*G).arcs[i][j].info = NULL;
        }
    printf("请输入弧头(初始点)、弧尾(终端点)、权值：\n"); //输入一条弧的始点和终点
    for (k = 0; k < (*G).arcnum; k++){
       //构造邻接矩阵
        scanf("%d%d%d", &v1, &v2, &w);
        i = LocateVex(*G, v1);
        j = LocateVex(*G, v2);

        if (i >= 0 && j >= 0)
            (*G).arcs[i][j].adj = (*G).arcs[j][i].adj = w; //置<v1,v2>的对称弧<v2,v1>

        //不再输入该弧含有的相关信息
    }
    (*G).kind = UDN;
    return OK;
}

int LocateVex(MGraph G, VertexType v)
{
   
    int ct;
    for (ct = 0; ct < G.vexnum; ct++)
        if (G.vexs[ct] == v)
            return ct;
    return -1;
}

int minimum(CLOSEDGE closedge[], int n)
{
   
    int i = 0, j, min, k;
    while (!closedge[i].lowcost)
        i++;
    min = closedge[i].lowcost;
    k = i;
    for (j = 1; j < n; j++)
        if (closedge[j].lowcost)
            if (min > closedge[j].lowcost)
            {
   
                min = closedge[j].lowcost;
                k = j;
            } //if
    return k;
}

void MiniSpanTree_PRIM(MGraph G, VertexType u)
{
   
    CLOSEDGE closedge[G.vexnum + 1];
    int k, j, i;

    k = LocateVex(G, u);
    for (j = 0; j < G.vexnum; ++j)
        if (j != k)
        {
    //辅助数组初始化
            closedge[j].adjvex = u;
            closedge[j].lowcost = G.arcs[k][j].adj;
        } //if

    closedge[k].lowcost = 0; //初始，U = {u}
    for (i = 1; i < G.vexnum; ++i)
    {
    //选择其余G.vexnum-1个顶点

        k = minimum(closedge, G.vexnum);                    //求出T的下一个结点：第k个顶点
        printf("(%d,%d)\n", closedge[k].adjvex, G.vexs[k]); //输出生成树的边

        closedge[k].lowcost = 0; //第k顶点并入U集

        for (j = 0; j < G.vexnum; ++j)
        {
   
            if (G.arcs[k][j].adj < closedge[j].lowcost)
            {
    //新顶点并入U集后重新选择最小边
                closedge[j].adjvex = G.vexs[k];
                closedge[j].lowcost = G.arcs[k][j].adj;
            } //if
        }     //for
    }         //for
}

/*******************************主函数部分**************************************/

int main()
{
   
    MGraph G;
    printf("P174 图7.16（a）\n");
    CreateUDN(&G);
    printf("\n输出生成树上的5条边为：\n");
    MiniSpanTree_PRIM(G, 1);
    return 0;
}

运行截图

7-4. 将图以邻接表存储，实现Kruskal算法。

code

#include<iostream>
#define Vnum 10
#define MAX 10000
#include<string.h>
#include<algorithm>
using namespace std;
typedef char Datatype;
typedef struct arcnode{
   
	int adjvex;
	int weight;
	struct arcnode *nextarc;
} arcnode;
typedef struct{
   
	Datatype vexdata;
	arcnode *firstarc;
} Adjlist;
typedef struct{
   
	int arcnum, vexnum;
	Adjlist adjlist[Vnum];
} GraphTp;
int visit[Vnum];
int quan[Vnum][Vnum];
void creat(GraphTp *g){
   
	int i, j, k, ii, quanz;
	char tailarc, headarc;
	arcnode *p;
	cout << "enter vexnum and arcnum:" << endl;
	cin >> g->vexnum >> g->arcnum;
	cout << "enter the vexdata:" << endl;
	for (i = 0; i < g->vexnum; i++){
   
		cin >> g->adjlist[i].vexdata;
		g->adjlist[i].firstarc = NULL;
	}
	cout << "enter the arcdata:" << endl;
	for (ii = 0; ii < g->arcnum; ii++){
   
		cin >> tailarc >> headarc >> quanz;
		for (k = 0; k < g->vexnum; k++)
			if (g->adjlist[k].vexdata == tailarc){
   
				i = k;
				break;
			}
		for (k = 0; k < g->vexnum; k++)
			if (g->adjlist[k].vexdata == headarc){
   
				j = k;
				break;
			}
		p = new arcnode;
		p->adjvex = j;
		p->weight = quanz;
		quan[i][j] = quanz;
		quan[j][i] = quanz;
		//cout << "the data is:" << i << ' ' << j << ' ' << quanz << endl;
		p->nextarc = g->adjlist[i].firstarc;
		g->adjlist[i].firstarc = p;
	}
}
struct edge{
   
	int weight;
	int u, v;
} bian[Vnum];
int cmp(edge A, edge B){
   
	return A.weight < B.weight;
}
void Kruskal(int n, int C[Vnum][Vnum])   {
     //Kuruskral算法，顶点数n，带权临接矩阵V[n][n]
	int i, j;
	int nodeset[n];                       //顶点所属集合，之后用于判断顶点是否在同一暂时的树中
	int count = 0;
	bool flag[n];                         //该数组用来判断顶点是否已经被选进生成树中
	for (i = 0; i < n; i++)   	{
              //将图中所有边存入数组边中

		nodeset[i] = i;
		flag[i] = false;
		for (j = 0; j < n; j++)
			if (C[i][j] < MAX)		{
   

				bian[count].u = i;
				bian[count].v = j;
				bian[count].weight = C[i][j];
				count++;
			}
	}
	sort(bian, bian + count, cmp);           /*将图中各边权值升序排列*/
	int edgeset = 0;
	int w = 0;                             /*用来存放生成树总权值*/
	count = 0;
	while (edgeset < n - 1)     	{
          /*核心算法*/

		if (!flag[bian[count].u] && flag[bian[count].v]){
    /*u未加入某一集合，v已经加入某个集合， 这个集合由已经找到的生成树顶点组成，开始可能形成多个*/
			w += bian[count].weight;
			flag[bian[count].u] = true;
			nodeset[bian[count].u] = nodeset[bian[count].v];
			edgeset++;
		}
		else if (flag[bian[count].u] && !flag[bian[count].v])/*v未加入，u已经加入*/
		{
   
			w += bian[count].weight;
			flag[bian[count].v] = true;
			nodeset[bian[count].v] = nodeset[bian[count].u];
			edgeset++;
		}
		else if (!flag[bian[count].u] && !flag[bian[count].v])            /*两个都未加入*/
		{
   
			w += bian[count].weight;
			flag[bian[count].u] = true;
			flag[bian[count].v] = true;
			nodeset[bian[count].u] = nodeset[bian[count].v];
			edgeset++;
		}
		else if (nodeset[bian[count].u] != nodeset[bian[count].v])/*如果两个加入集合，判断加入集合是否相同，相同说明形成环，跳出此次循环，转向下一次。*/
		{
                                                         /*否则将两个集合合并*/
			w += bian[count].weight;
			edgeset++;
			int tmp = nodeset[bian[count].v];
			for (i = 0; i < n; i++)
				if (nodeset[i] = tmp)
					nodeset[i] = nodeset[bian[count].u];
		}
		count++;                          /*转向次小边，进行下一次判断*/
	}
	cout << "该图权值是：" << w;              /*输出权值*/
}
int main()
{
   
	int i, j;
	for (i = 0; i < Vnum; i++)
		for (j = 0; j < Vnum; j++)
			quan[i][j] = MAX;
	GraphTp g;
	creat(&g);
	cout << endl;
	Kruskal(g.vexnum, quan);
	return 0;
}

运行截图

7-5.将图以邻接矩阵或邻接表存储，实现Dijkstra算法。

code

#include<bits/stdc++.h>
using namespace std;

/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2 
typedef int Status; 
typedef int Boolean;  
#define MAX_NAME 5 
#define MAX_INFO 20 
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];

/* --------------------------------- 图的数组(邻接矩阵)存储表示 --------------------------------*/
 
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef enum {
    DG, DN, AG, AN }GraphKind; 
typedef struct{
   
	VRType adj; 
	InfoType *info; 
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
   
	VertexType vexs[MAX_VERTEX_NUM];
	AdjMatrix arcs; 
	int vexnum, arcnum; 
	GraphKind kind;
}MGraph;

typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];

/* --------------------------- 需要用的图的数组(邻接矩阵)存储的基本操作 --------------------------*/

int LocateVex(MGraph G, VertexType u){
    
/* 初始条件:图G存在,u和G中顶点有相同特征 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
	int i;
	for (i = 0; i < G.vexnum; ++i)
		if (strcmp(u, G.vexs[i]) == 0)
			return i;
	return -1;
}
 
Status CreateDN(MGraph &G){
   
	int i, j, k, w, IncInfo;
	char s[MAX_INFO], *info;
	VertexType va, vb;
	printf("请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0)(以空格作为间隔): ");
	scanf("%d%d%d", &G.vexnum, &G.arcnum, &IncInfo);
	printf("请输入%d个顶点的值(<%d个字符):\n", G.vexnum, MAX_NAME);
	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 = INFINITY; 
			G.arcs[i][j].info = NULL;
		}
	printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \n", G.arcnum);
	for (k = 0; k < G.arcnum; ++k){
   
		scanf("%s%s%d%*c", va, vb, &w);  
		i = LocateVex(G, va);
		j = LocateVex(G, vb);
		G.arcs[i][j].adj = w;
		if (IncInfo){
   
			printf("请输入该弧的相关信息(<%d个字符): ", MAX_INFO);
			gets(s);
			w = strlen(s);
			if (w){
   
				info = (char*)malloc((w + 1) * sizeof(char));
				strcpy(info, s);
				G.arcs[i][j].info = info; 
			}
		}
	}
	G.kind = DN;
	return OK;
}

 
//算法7.15
void ShortestPath_DIJ(MGraph G, int v0, PathMatrix &P, ShortPathTable &D){
    
/* 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度 D[v]。若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。 final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径 算法7.15 */
	int v, w, i, j, min;
	Status final[MAX_VERTEX_NUM];
	for (v = 0; v < G.vexnum; ++v){
   
		final[v] = FALSE;
		D[v] = G.arcs[v0][v].adj;
		for (w = 0; w < G.vexnum; ++w)
			P[v][w] = FALSE; 
		if (D[v] < INFINITY){
   
			P[v][v0] = TRUE;
			P[v][v] = TRUE;
		}
	}
	D[v0] = 0;
	final[v0] = TRUE;				// 初始化,v0顶点属于S集 
	for (i = 1; i < G.vexnum; ++i) 	//其余G.vexnum-1个顶点 
	{
    								// 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 
		min = INFINITY; 						// 当前所知离v0顶点的最近距离 
		for (w = 0; w < G.vexnum; ++w)
			if (!final[w]) 						// w顶点在V-S中 
				if (D[w] < min){
   
					v = w;
					min = D[w];
				} 								//w顶点离v0顶点更近 
		final[v] = TRUE; 						// 离v0顶点最近的v加入S集 
		for (w = 0; w < G.vexnum; ++w) {
   		// 更新当前最短路径及距离 
			if (!final[w] && min < INFINITY&&G.arcs[v][w].adj < INFINITY && (min + G.arcs[v][w].adj < D[w])){
   
				D[w] = min + G.arcs[v][w].adj;
				for (j = 0; j < G.vexnum; ++j)
					P[w][j] = P[v][j];
				P[w][w] = TRUE;
			}
		}
	}
}
 
int main(){
   
	int i, j, v0 = 0; 
	MGraph g;
	PathMatrix p;
	ShortPathTable d;
	CreateDN(g);
	ShortestPath_DIJ(g, v0, p, d);
	printf("最短路径数组 PathMatrix[i][j] 如下:\n");
	for (i = 0; i < g.vexnum; ++i){
   
		for (j = 0; j < g.vexnum; ++j)
			printf("%2d", p[i][j]);
		printf("\n");
	}
	printf("%s到各顶点的最短路径长度为：\n", g.vexs[0]);
	for (i = 1; i < g.vexnum; ++i)
		printf("%s-%s:%d\n", g.vexs[0], g.vexs[i], d[i]);
	return 0;
}

运行截图