1. 邻接矩阵和邻接表删除有向图或无向图的一条边的算法。。。急用。。尽量简单些就好。。。。
#include <iostream>
using namespace std;
const int DoctorCount = 7;
struct Constraint
{
int doc1;
int relation;
int doc2;
int days;
};
bool check(int *doctors, Constraint *constrains, int n, int index)
{
if (index < 0 || index > DoctorCount || doctors[index] == -1)
{
return false;
}
for (int i = 0; i <= index; i++)
{
for (int j = 0; j < index; j++)
{
if (doctors[i] == doctors[j] && i != j)
{
return false;
}
}
}
for (int i = 0; i < n; i++)
{
Constraint *p = &constrains[i];
if (p->doc1 <= index && p->doc2 <= index)
{
if (p->relation == 1)
{
if (doctors[p->doc2] - doctors[p->doc1] != p->days)
{
return false;
}
}
else
{
if (doctors[p->doc1] - doctors[p->doc2] != p->days)
{
return false;
}
}
}
}
return true;
}
bool slove(int *doctors, Constraint *constrains, int n, int index)
{
if (index >= DoctorCount)
{
return true;
}
if (doctors[index] != -1)
{
return slove(doctors, constrains, n, index + 1);
}
for (int i = 1; i <= 7; i++)
{
doctors[index] = i;
if (check(doctors, constrains, n, index))
{
if (slove(doctors, constrains, n, index + 1))
{
return true;
}
}
doctors[index] = -1;
}
return false;
}
int main( )
{
int n;
cin>>n;
int doctors[7];
for (int i = 0; i < 7; i++)
{
doctors[i] = -1;
}
Constraint *constraints;
constraints = new Constraint[n];
int constraints_count = 0;
for (int i = 0; i < n; i++)
{
char tmp[20];
cin>>tmp;
if (tmp[1] == '=')
{
doctors[tmp[0] - 'A'] = tmp[2] - '0';
}
else
{
constraints[i].doc1 = tmp[0] - 'A';
constraints[i].relation = tmp[1] == '>' ? 1 : 0;
constraints[i].doc2 = tmp[2] - 'A';
constraints[i].days = tmp[3] - '0';
constraints_count++;
}
}
slove(doctors, constraints, constraints_count, 0);
for (int i = 0; i < 7; i++)
{
cout<<(char)(i + 'A')<<" "<<doctors[i]<<endl;
}
delete []constraints;
return 0;
}
2. 存储结构为邻接矩阵，怎么编写无向图添加、删除一个顶点，添加、删除一条边的算法
邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。
/* MGraph.cc: 图的邻接矩阵存储表示和实现 */
/* 包含图类型Graph定义；创建图；深度优先遍历；广度优先遍历 */
/* 用到引用型参数，在TC下无法通过编译，VC等C++编译器可通过 */
#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX
#define VType char //顶点值类型
#define EType int //边权值类型
#define MAXVNUM 50 //最大顶点个数
#define DIGRAPH 0 //有向图(网)
#define UNDIGRAPH 1 //无向图(网)
#define INVALID INT_MAX //无效权值(最大整数表示无穷大)
#define EMPTY -1 //"空"顶点序号
3. 求一个数组的邻接矩阵的算法描述
1.先求出第1行和第2行中最大的数6
这个数就是顶点的个数
邻接矩阵即为6阶方阵
2.
构造6阶矩阵,
元素全部赋值0
3.
循环(i=1,...,9)读取每条边的起点和终点，比如第一条边的起点和终点:
1，3
将矩阵第1行第3列的元素赋值为
1.
4.
循环完毕退出.
可显示看看邻接矩阵
4. 用一个邻接矩阵存储有向图g最多有多少条弧
矩阵的元素数目为N^2 也就是答案B 非零元素数目为E 也就是答案C
5. 无向图添加，删除一个顶点，添加，删除一条边的算法，存储结构为邻接矩阵，写得好的再加分！
/* MGraph.cc: 图的邻接矩阵存储表示和实现 */
/* 包含图类型Graph定义；创建图；深度优先遍历；广度优先遍历 */
/* 用到引用型参数，在TC下无法通过编译，VC等C++编译器可通过 */
#include <stdio.h>
#include <string.h>
#include <limits.h> //含INT_MAX
#define VType char //顶点值类型
#define EType int //边权值类型
#define MAXVNUM 50 //最大顶点个数
#define DIGRAPH 0 //有向图(网)
#define UNDIGRAPH 1 //无向图(网)
#define INVALID INT_MAX //无效权值(最大整数表示无穷大)
#define EMPTY -1 //"空"顶点序号
//定义邻接矩阵表示的图类型Graph:
typedef struct
{
VType v[MAXVNUM]; //顶点序列(顶点编号从0开始)
EType w[MAXVNUM][MAXVNUM]; //邻接矩阵
int vn, en; //顶点数,边数
int kind; //图的种类：=DIGRAPH表示有向图(网)，=UNDIGRAPH表示无向图(网)
}Graph;
int visited[MAXVNUM]; //访问标志数组(=1已访问，=0未访问)。遍历时用到的全局量。
/* 创建图G
参数Vex是存放顶点序列的数组
参数VVW是整数数组，以的形式依次存放各边的起止点序号(Vi,Vj)和权(Wij)，-1是数据结束标志
参数kind=DIGRAPH表示有向图(网)，=UNDIGRAPH表示无向图(网)
*/
void CreateGraph(Graph &G, VType *Vex, int VVW[], int kind)
{
int i, j, p, n, w;
n = strlen(Vex);
G.vn = n; //顶点数
G.kind = kind; //图的种类
//置顶点序列:
for (i = 0; i < n; i++)
G.v[i] = Vex[i];
//初始化邻接矩阵:
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
G.w[i][j] = INVALID;
//构造邻接矩阵:
p = 0; //VVW数组元素“指针”
n = 0; //边计数器
while (VVW[p] != -1)
{//只要p未到结束位置便继续:
i = VVW[p]; //边的起点序号
j = VVW[p + 1]; //边的终点序号
w = VVW[p + 2]; //边的权
G.w[i][j] = w; //置邻接矩阵的(i,j)位置元素
if (G.kind == UNDIGRAPH) //若是无向图(网),
G.w[j][i] = G.w[i][j]; //则置(i,j)的对称位置(j,i)
n++; //边计数器加1
p += 3; //p指向下一组(Vi,Vj,Wij)
}//end while
G.en = n; //边数
}//CreateGraph
/* 返回G中顶点i的一个未曾访问过的邻接点(序号) */
int NextAdjVex(Graph &G, int i)
{
int j, a;
a = EMPTY; //邻接点序号初始为"空"
//在邻接矩阵的第v行找有效元素：
for (j = 0; j < G.vn; j++)
{
if (G.w[i][j] == INVALID) //若当前元素是无效元素,
continue; //则继续找。
if (!visited[j])
{//若当前有效元素未曾访问过,则作为邻接点a:
a = j;
break;
}//end if
}//end for
return a;
}//NextAdjVex
/* 访问顶点i */
void visit(Graph &G, int i)
{
printf("%c", G.v[i]);
}//visit
/* 从第i个顶点出发深度优先遍历连通图G */
/* 调用DFS前可能需初始化数组visited[] */
void DFS(Graph &G, int i)
{int a;
visit(G, i); //访问i顶点
visited[i] = 1; //标注i顶点已访问
a = NextAdjVex(G, i); //找出一个i的邻接点a
while (a != EMPTY)
{//只要a存在便继续:
if (visited[a] == 0) //若a未曾访问,
DFS(G, a); //则从a出发继续进行深度优先遍历。
a = NextAdjVex(G, i); //找出i的下一个邻接点a
}//end while
}//DFS
/* 从第i个顶点出发深度优先遍历图G */
void DFSTrav(Graph &G, int i)
{int k;
//初始化各顶点的访问标志为0(未曾访问):
for (k = 0; k < G.vn; k++)
visited[k] = 0;
DFS(G, i); //从i出发遍历
//若G非连通图，执行一次DFS无法遍历所有顶点，还需用如下for对尚未访问的顶点DFS。
//若G是连通图，执行一次DFS就已遍历所有顶点，此时如下for什么也不做，因所有visited=1。
for (k = 0; k < G.vn; k++)
if (!visited[k]) DFS(G, k); //对尚未访问的顶点DFS
}//DFSTrav
//显示图的邻接矩阵
void ShowM(Graph &G)
{
int row, col, n;
n = G.vn; //顶点数
//以表格形式输出数组：
//输出表头：
printf(" ");
for(col = 0; col < n; col++)
printf("%3d",col);
printf("\n");
printf("---+");
for(col = 0; col < n; col++)
printf("---");
printf("\n");
//输出表体(矩阵元素)：
for(row = 0; row < n; row++)
{
printf("%3d|", row);
for(col = 0; col < n; col++)
{
if (G.w[row][col] == INVALID)
printf("%3c", '*');
else
printf("%3d", G.w[row][col]);
}//end for col
printf("\n");
}//end for row
printf("\n");
}//ShowM
你的串号我已经记下，采纳后我会帮你制作
6. 用邻接矩阵的 输出 矩阵 弧
如下，c语言写的~~
#define MAXNUM 30
#define INFINITY 10000
#define FALSE 0
#define TRUE 1
#define BACK -1
#include "stdio.h"
#include <stdio.h>
#include "malloc.h"
//定义图的构造体
typedef struct{
char vexs[MAXNUM];
int edges[MAXNUM][MAXNUM];
int n,e;
}Mgraph;
//图的输入方法
void CreateGraph(Mgraph *g){
int i,j,k,w;
char ch;
printf("请输入结点数与弧数，如：3,2：");
scanf("%d,%d",&(g->n),&(g->e));
//初始化权值
for(i=0;i<g->n;i++){
for(j=0;j<g->n;j++){
if(i==j){
g->edges[i][j]=0;
}else{
g->edges[i][j]=INFINITY;
}
}
}
//获取权值
printf("\n为方便演示，结点内容默认为结点序号，无需输入。\n\n下面请输入弧及权值，例如：若点0到1有弧可达，且权值为10，则输入:0,1,10。注意：输入时不区分弧的顺序。\n");
for(k=0;k<g->e;k++){
printf("\t请输入第%d个弧及权值：",k+1);
scanf("%d,%d,%d",&i,&j,&w);
g->edges[i][j]=w;
}
//输出邻接矩阵
printf("\n邻接矩阵：\n",k);
for(i=0;i<g->n;i++){
printf("\t");
for(j=0;j<g->n;j++){
if(g->edges[i][j]>=INFINITY){
printf("∞\t");
}else{
printf("%d\t",g->edges[i][j]);
}
}
printf("\n");
}
}
void ShortPath(Mgraph *g,int v0){
/*定义多个变量与数组，其中R数组为记录路径的数组，iterator为游标，
D为距离数组，final数组记录是否已取到最短路径
*/
int i,j,v,w,min;
int R[MAXNUM][MAXNUM];
int iterator[MAXNUM];
int D[MAXNUM];
int final[MAXNUM];
//初始化游标为零
for(i=0;i<MAXNUM;i++){
iterator[i]=0;
}
//初始化final为FALSE，D为弧的权值
for(v = 0;v < g->n; ++v){
final[v] = FALSE;
D[v] = g->edges[v0][v];
}
//初始化v0的路径距离为零，设置已获取最短路径
D[v0] = 0;
final[v0] = TRUE;
//主循环，获取其他的最短路径
for(i = 1;i < g->n; ++i){
min = INFINITY;
//寻找最小的D[w]
for(w = 0;w < g->n; ++w){
if(final[w] != TRUE){
if(D[w]<min){
v=w;
min=D[w];
}
}
}
//将找到的v设置已获取最短路径
final[v]=TRUE;
//打印输出该路径
if(min!=INFINITY){
printf("\t点%d到点%d的最小路径值为：%d\t",v0,v,D[v]);
printf("路径为：%d->",v0,v,v0);
for(j=0;j<iterator[v];j++){
printf("%d->",R[v][j]);
}
printf("%d\n",v);
}
//更新D[w]
for(w = 0;w < g->n; ++w){
if((final[w] != TRUE) && (min+g->edges[v][w] < D[w])){
//更新路径
iterator[w]=iterator[v];
for(j=0;j<iterator[v];j++){
R[w][j]=R[v][j];
}
R[w][iterator[w]]=v;iterator[w]++;
D[w] = min + g->edges[v][w];
}
}
}
//若final始终为FALSE，则不可达
for(w = 0;w<g->n; ++w){
if(final[w] != TRUE){
printf("\t点%d到点%d不可达\n",v0,w);
}
}
}
//主方法
void main(){
Mgraph * g;
int i=0;
g=(Mgraph *)malloc(sizeof(Mgraph));
printf("该程序实现了Dijkstra算法，支持路径显示，请按提示输入数据：\n\n");
CreateGraph(g);
printf("\n最小路径判断(以0点为起点)：\n");
ShortPath(g,0);
getch();
}
7. 用邻接矩阵表示一个图时 1、 输出一个图的边数，以及两端顶点 2、 增加、删除一条边（输出新图对应的邻接
/*用邻接矩阵实现图*/
#include <stdio.h>
#include<stdlib.h>
#define WItem int
typedef struct graph *Graph;
struct graph
{
WItem NoEdge; /*无边标记*/
int n; /*顶点数*/
int e; /*边数*/
WItem **a; /*邻接矩阵*/
}AWDgraph;
Graph Graphinit(int n,WItem noEdge) /*创建图*/
{
int i,j;
Graph G=(struct graph *)malloc(sizeof (*G));
G->n=n;
G->e=0;
G->NoEdge=noEdge;
a=(WItem**)malloc(sizeof(WItem)*n*n);
for(i=0;i<G->n+1;i++)
{
for (j=0;j<G->n+1;j++)
G->a[i][j]=G->NoEdge;
}
return G;
}
int GraphEdges(Graph(G)) /*输出边数*/
{return G->e;}
int GraphVertices(Graph(G)) /*输出顶点数*/
{return G->n;}
int GraphExist(int i,int j,Graph G) /*判断边是否存在*/
{
if(i<1||j<1||i>G->n||G->a[i][j]==G->NoEdge) return 0;
return 1;
}
void GraphAdd(int i,int j,WItem w,Graph G) /*加入一条边*/
{
if(i<1||j<1||i>G->n||G->n||i==j||G->a[i][j]!=G->NoEdge)
printf("Bad input");
G->a[i][j]=w;
G->e++;
}
void GraphDelete(int i,int j,Graph G) /*删除一条边*/
{
if(i<1||j<1||i>G->n||j>G->n||G->a[i][j]==G->NoEdge)
printf("Bad input");
G->a[i][j]=G->NoEdge;
G->e--;
}
int OutDegree(int i,Graph G) /*计算出度*/
{
int j,sum=0;
if(i<1||i>G->n) printf("Bad input");
for(j=1;j<=G->n;j++)
if(G->a[i][j]!=G->NoEdge) sum++;
return sum;
}
int InDegree(int i,Graph G) /*计算入度*/
{
int j,sum=0;
if(i<1||i>G->n) printf("Bad input");
for(j=1;j<=G->n;j++)
if(G->a[i][j]!=G->NoEdge) sum++;
return sum;
}
/*输出表*/
void GraphOut(Graph G)
{
int i,j;
for(i=1;i<=G->n;i++)
{
for(j=1;j<=G->n;j++)
{printf("%d",G->a[i][j]);
printf("\n");}
}
}
void main() /*测试该图类型数据结构算法*/
{
int p,q,n,e,i,j,w,noEdge;
Graph G;
noEdge=0;
printf("几个结点\n");
scanf("%d",&n);
Graph Graphinit(int n,WItem noEdge);
printf("加入几条边\n");
scanf("%d",&e);
for(p=0;p<e;p++)
{
printf("边的权值为多少？");
scanf("%d",&w);
printf("在哪加边？");
scanf("%d,%d",&i,&j);
void GraphAdd(int i,int j, int w,Graph G);
}
for(i=1;i<=G->n;i++)
{
for(j=1;j<=G->n;j++)
printf("%d",G->a[i][j]);
}
}
8. 怎么写 如果1个图采用邻接矩阵表示，则实现求图边或弧个数的算法
gi jerr
9. 把邻接矩阵转换成邻接表的算法
#include <stdio.h>
#include <malloc.h>
#define INF 32767 //INF表示∞
typedef int InfoType;
typedef int Vertex;
//--------------邻接矩阵存储表示------------
#define MAXV 20 //最大顶点个数
#define INF 32767 //INF表示∞
//以下定义邻接矩阵类型
typedef struct{
int nunber; //顶点编号
InfoType info; //顶点其他信息
} VertexType; //顶点类型
typedef struct { //图的定义
int edges[MAXV][MAXV]; //邻接矩阵
int n,e; //顶点数，弧数
VertexType vexs[MAXV]; //存放顶点信息
} MGraph; //图的邻接矩阵类型
//-------------------邻接表存储表示----------
//以下定义邻接表类型
typedef struct ANode{ //弧的结点结构类型
int adjvex; //该弧的终点位置
InfoType info; //该弧的相关信息,这里用于存放权值
struct ANode *nextarc; //指向下一条弧的指针
} ArcNode;
typedef struct Vnode { //邻接表头结点的类型
Vertex data; //顶点信息
int count; //存放顶点入度,只在拓扑排序中用
ArcNode *firstarc; //指向第一条弧
} VNode;
typedef VNode AdjList[MAXV]; //AdjList是邻接表类型
typedef struct{
AdjList adjlist; //邻接表
int n,e; //图中顶点数n和边数e
} ALGraph; //图的邻接表类型
//将邻接矩阵g转换成邻接表G
void MatToList(MGraph g,ALGraph *&G)
{
int i,j,n=g.n; //n为顶点数
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
// 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 (g.edges[i][j]!=0) //邻接矩阵的当前元素不为0
{
p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点*p
p->adjvex=j;
p->info=g.edges[i][j];
p->nextarc=G->adjlist[i].firstarc; //将*p链到链表后
G->adjlist[i].firstarc=p;
}
G->n=n;G->e=g.e;
}
void ListToMat(ALGraph *G,MGraph &g)
//将邻接表G转换成邻接矩阵g
{
int i,n=G->n;
ArcNode *p;
for (i=0;i<n;i++)
{
p=G->adjlist[i].firstarc;
while (p!=NULL)
{
g.edges[i][p->adjvex]=p->info;
p=p->nextarc;
}
}
g.n=n;g.e=G->e;
}
void DispMat(MGraph g)
//输出邻接矩阵g
{
int i,j;
for (i=0;i<g.n;i++)
{
for (j=0;j<g.n;j++)
if (g.edges[i][j]==INF)
printf("%3s","∞");
else
printf("%3d",g.edges[i][j]);
printf("\n");
}
}
void DispAdj(ALGraph *G)
//输出邻接表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",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}
//以下主函数用作调试
void main()
{
int i,j;
MGraph g,g1;
ALGraph *G;
int A[6][6]={
{0,5,0,7,0,0},
{0,0,4,0,0,0},
{8,0,0,0,0,9},
{0,0,5,0,0,6},
{0,0,0,5,0,0},
{3,0,0,0,1,0}};
g.n=6;g.e=10;
for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
g.edges[i][j]=A[i][j];
printf("\n");
printf(" 有向图G的邻接矩阵:\n");
DispMat(g);
G=(ALGraph *)malloc(sizeof(ALGraph));
printf(" 图G的邻接矩阵转换成邻接表:\n");
MatToList(g,G);
DispAdj(G);
printf(" 图G的邻接表转换成邻接邻阵:\n");
for (i=0;i<g.n;i++)
for (j=0;j<g.n;j++)
g1.edges[i][j]=0;
ListToMat(G,g1);
DispMat(g1);
printf("\n");
}
10. 有向图G的邻接矩阵为A，如果<Vi,Vj>是图中的一条弧，则A[i][j]的值为_______。
带权图：边<Vi，Vj>的权
无权图：1